高效地聚合并去重超大（密码）列表的方法

Question

背景：

• 我正在尝试将大量分开的密码列表文本文件合并成一个文件，以便用于基于字典的密码破解。

• 每个文本文件都是按行分隔的（每行一个密码），目前有82个独立的文件。大多数（66个）文件的大小在1-100Mb之间，12个在100-700Mb之间，3个是2Gb，1个（最麻烦的）是11.2Gb。

• 总的来说，我估计需要处理17.5亿个非唯一密码；其中我估计大约有4.5亿个（25%）是重复的，最终需要被丢弃。

• 我正在尝试在一个有6Gb可用内存的设备上进行这个操作（也就是说，8Gb的设备中已经使用了2Gb）。

问题：

我需要一种方法来 a) 将所有这些密码聚合在一起，b) 在我的内存限制内去除完全重复的密码，并且在一个合理的时间范围内（大约7天，理想情况下更少，但如果需要几周我也不在乎，只要以后不需要再运行它）。

我是一名熟练的Python程序员，因此已经尝试了几次。我的一次成功尝试使用sqlite3将处理过的密码存储在硬盘上。然而，这意味着在处理过程中跟踪哪些文件已经完成是非常繁琐的，我需要对每个完成的文件进行哈希，并在每次打开新文件时进行维护和比较。对于非常大的文件来说，任何进度都会丢失。

我在处理文本文件时，每次处理大约10亿行，以防止内存耗尽，同时又不会长时间没有反馈。我知道，如果给我足够的时间，我可以完全填充我的数据库，因为我在24小时的运行时间内达到了大约4.5Gb的数据库文件大小，所以我估计如果让我继续运行，最多需要4天才能完成所有工作，但我不知道如何最有效地读写数据库，也没有好的想法来处理去重（是在填充数据库时去重，还是之后再进行额外的处理？有没有更快的方法来检查数据库中的唯一性？）。

---

我今天在这里请求的是关于如何实现我的巨大的唯一密码列表（理想情况下使用Python）的编程和优化方法的建议/解决方案。如果我已经偏离了方向，我完全开放接受不同的思路。

---

两个额外的需求是：

• 将来能够添加更多密码，而不必重建整个列表；

• 最终数据库大小小于20Gb，这样移动起来不会太麻烦。

---

解决方案

根据CL的解决方案，我想出了一个稍微修改的方法，这比我原来的想法要优雅得多。

按照CL的建议，我设置了一个sqlite3数据库，并将文本文件输入到一个Python脚本中，该脚本处理这些文件，然后输出一个命令将它们插入到数据库中。一开始这确实有效，但速度非常慢（几乎不可行）。

我通过一些简单的数据库优化解决了这个问题，这样做更容易实现，实际上也更干净，直接在下面包含的核心Python脚本中完成，这个脚本是基于CL的框架代码。原始代码生成了非常多的I/O操作，这在我的（Win7）操作系统上导致了一些奇怪的问题，甚至出现了蓝屏和数据丢失。我通过将整个密码文件的插入操作合并为一个SQL事务，并进行了一些pragma更改来解决这个问题。最终，代码的插入速度达到了每秒约30,000次插入，虽然不是最好，但对于我的目的来说是可以接受的。

对于最大的文件，这种方法可能仍然会失败，但如果发生这种情况，我会简单地将文件分成更小的1Gb部分，逐个处理。

import sys
import apsw

i = 0
con = apsw.Connection("passwords_test.db")
cur = con.cursor()

cur.execute("CREATE TABLE IF NOT EXISTS Passwords(password TEXT PRIMARY KEY) WITHOUT ROWID;")
cur.execute("PRAGMA journal_mode = MEMORY;")
cur.execute("PRAGMA synchronous = OFF;")

cur.execute("BEGIN TRANSACTION")
for line in sys.stdin:
    escaped = line.rstrip().replace("'", "''")
    cur.execute("INSERT OR IGNORE INTO Passwords VALUES(?);", (escaped,))
    i += 1
    if i % 100000 == 0: # Simple line counter to show how far through a file we are
        print i

cur.execute("COMMIT")
con.close(True)

然后从命令行运行这段代码：

insert_passwords.py < passwordfile1.txt

并通过以下方式自动化：

for %%f in (*.txt) do (
insert_passwords.py < %%f
)

总的来说，数据库文件的增长速度并不快，插入速度也足够，我可以随时中断/恢复操作，重复值被准确丢弃，目前的限制因素是数据库的查找速度，而不是CPU或磁盘空间。

Answer 1

在SQL数据库中存储密码时，如果想要检测重复的密码，就需要使用索引。这意味着密码会被存储两次，一次在表里，一次在索引里。

不过，从SQLite 3.8.2版本开始，支持一种叫做无行ID表的功能（在其他数据库中称为“聚集索引”或“索引组织表”），这样就可以避免为主键单独创建索引。

目前没有Python版本自带SQLite 3.8.2。如果你没有使用APSW，你仍然可以用Python来创建SQL命令：

1. 安装最新的sqlite3命令行工具（可以在下载页面找到）。

2. 创建一个数据库表：

   $ sqlite3 passwords.db
   SQLite version 3.8.5 2014-06-02 21:00:34
   Enter ".help" for usage hints.
   sqlite> CREATE TABLE MyTable(password TEXT PRIMARY KEY) WITHOUT ROWID;
   sqlite> .exit
   

3. 创建一个Python脚本来生成INSERT语句：

   import sys
   print "BEGIN;"
   for line in sys.stdin:
       escaped = line.rstrip().replace("'", "''")
       print "INSERT OR IGNORE INTO MyTable VALUES('%s');" % escaped
   print "COMMIT;"
   

   （INSERT OR IGNORE语句在遇到重复时不会插入新行，因为这会违反主键的唯一性约束。）

4. 通过将命令输入到数据库命令行中来插入密码：

   $ python insert_passwords.py < passwords.txt | sqlite3 passwords.db
   

不需要拆分输入文件；事务越少，开销就越小。