mysql - 搜索非常大的彩虹表文件

Question

我正在寻找搜索非常大的彩虹表文件(13GB 文件)的最佳方法。它是一个 CSV 样式的文件，看起来像这样:

1f129c42de5e4f043cbd88ff6360486f; somestring
78f640ec8bf82c0f9264c277eb714bcf; anotherstring
4ed312643e945ec4a5a1a18a7ccd6a70; yetanotherstring

...你明白了 - 大约有 9 亿行，总是带有哈希、分号、明文字符串。

基本上，程序应该查看此文件中是否包含特定的哈希值。

最快的方法是什么？显然，我无法将整个文件读入内存，然后在其上放置 strstr() 。

那么最有效的方法是什么？

1. 逐行读取文件，始终读取到strstr()；
2. 读取较大的文件 block (例如 10,000 行)，执行 strstr()

或者将所有这些数据导入 MySQL 数据库，然后通过 SQL 查询搜索哈希会更有效吗？

感谢任何帮助

Answer 1

最好的方法是对其进行排序，然后使用 binary search类似的算法就可以了。排序后，大约需要 O(log n) 时间才能找到特定条目，其中 n 是您拥有的条目数。您的算法可能如下所示:

1. 保留起始偏移量和结束偏移量。将起始偏移量初始化为零，将结束偏移量初始化为文件大小。
2. 如果 start = end，则没有匹配项。
3. 从偏移量(开始 + 结束)/2 处读取一些数据。
4. 向前跳直到看到换行符。 (您可能需要阅读更多内容，但如果您在第 3 步中选择合适的大小(大于大多数记录)进行阅读，您可能无需再阅读更多内容。)
5. • 如果您当前使用的哈希就是您要查找的哈希，请继续执行第 6 步。
   • 否则，如果您所在的哈希值小于您要查找的哈希值，请将 start 设置为当前位置并转到第 2 步。
   • 如果您所在的哈希值大于您要查找的哈希值，请将 end 设置为当前位置并转到第 2 步。
6. 跳到分号和尾随空格。未哈希的数据将从当前位置到下一个换行符。

这可以轻松转换为带有中断的 while 循环。

使用适当的索引将其导入 MySQL，这样将使用类似(或更多，因为它可能包装得很好)的高效算法。