python - 从大型(密码)列表中聚合和删除重复项的有效方法

Question

内容：


我试图将大量单独的密码列表文本文件合并为一个文件，以用于基于字典的密码破解。
每个文本文件都有行分隔符（每行一个密码），目前有82个单独的文件。大多数（66）文件的文件大小在1-100Mb范围内，其中12个文件在100-700Mb之间，3个文件在2Gb内，而1个（问题最多的）文件在11.2Gb内。
我估计总共需要处理17.5亿个非唯一密码。我估计其中约有4.5亿（％25）是重复项，最终需要丢弃。
我正在尝试在具有6GB以上可用RAM的设备上进行此操作（即8Gb已消耗2Gb）。


问题：

我需要一种方法来将a）所有这些密码汇总在一起，并b）在我的RAM内存限制内并在合理的时间内（〜7天，理想的要少得多）删除确切的重复项，但实际上我不在乎是否需要花费数周的时间，然后我再也不需要运行它了）时间窗口。

我是一名称职的Python程序员，因此已经多次破解。我最成功的尝试是使用sqlite3在磁盘进行过程中将已处理的密码存储在硬盘上。但是，这意味着通过散列每个完成的文件并在每次打开新文件时都进行维护/比较来单调乏味地跟踪各个处理实例之间已经完成了哪些文件（我取消并重新启动了几次以进行更改）。但是，对于非常大的文件，任何进度都将丢失。

我一次以大约10亿（最多）行的块为单位处理文本文件，以防止内存耗尽而长时间没有反馈。我知道我可以这样做，因为在24小时的运行时间中，数据库文件大小达到约4.5Gb时，我需要花很多时间来完全填充数据库，因此我估计剩下的时间最多要花4天才能完成所有工作，但是我不知道是否/如何最有效地对其进行读/写操作，也不知道如何解决删除重复项的任何好主意（在我填充数据库时还是做完之后做更多的遍……？在我不知道的数据库配置中，有没有一种更快的方法来查找唯一性？）。



我今天的要求是寻求有关编程和优化方法的建议/解决方案，以实现我庞大而独特的密码列表（理想情况下是使用Python）。如果我已经偏离标准，我完全愿意采取完全不同的方针。



有两个不错的选择：


一种在将来无需重新构建整个列表的情况下添加更多密码的方法；和
在所有这些操作的最后，数据库<20Gb，因此移动起来不是一个很大的麻烦。




解

基于CL的解决方案，该解决方案最终比我想的要优雅得多，因此我想出了一个稍微修改的方法。

按照CL的建议，我设置了一个sqlite3数据库，并将文本文件输入到Python脚本中，该脚本使用了它们，然后输出命令以将其插入数据库中。这项工作虽然直接进行，但是非常缓慢（不可行）。

我通过一些简单的数据库优化解决了这一问题，这些优化更容易实现，并且坦率地说更干净，可以从下面包含的基于CL框架代码的核心Python脚本中进行所有操作。原始代码产生了很多I / O操作，这一事实在我的（Win7）操作系统上引起了奇怪的事情，从而导致BSOD和数据丢失。我通过使整个密码文件的插入成为一个SQL事务加上几个编译指示更改来解决了这一问题。最终，该代码以大约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
)

总而言之，DB文件本身并没有增长太快，插入率足够，我可以一口气中断/恢复操作，精确地丢弃重复值，而当前的限制因素是DB不是CPU或磁盘空间。

Answer 1

将密码存储在SQL数据库中时，能够检测重复项需要索引。
这意味着密码在表和索引中存储两次。

但是，SQLite 3.8.2或更高版本支持WITHOUT ROWID tables（在其他数据库中称为“集群索引”或“索引组织表”），这避免了为主键使用单独的索引。

没有Python版本已包含SQLite 3.8.2。
如果不使用APSW，则仍可以使用Python创建SQL命令：


安装最新的sqlite3命令行外壳程序（download page）。
创建数据库表：

$ 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

创建一个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语句将不会插入行。）
通过将命令通过管道插入数据库外壳程序来插入密码：

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

无需拆分输入文件；更少的交易产生更少的开销。