0

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

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

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

所以基本上，程序应该看看这个文件中是否有一个特定的哈希。

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

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

  1. 逐行读取文件，总是到一个strstr()；
  2. 读取较大的文件块（例如 10.000 行），执行strstr()

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

任何帮助表示赞赏

4

3 回答 3

2

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

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

这可以很容易地转换为带中断的 while 循环。

使用适当的索引将其导入 MySQL 等将使用类似（或更多，因为它可能包装得很好）有效的算法。

于 2013-01-26T07:32:01.130 回答
0

我首先将单个大文件拆分为 65536 个较小的文件，这样如果哈希以0000它在文件中00/00data.txt开头，如果哈希以0001它在文件中开头00/01data.txt，等等。如果完整文件是 12 GiB，那么每个较小的文件（平均）为 208 KiB。

接下来，将哈希与字符串分开；这样您就有 65536 个“哈希文件”和 65536 个“字符串文件”。每个散列文件将包含散列的其余部分（仅最后 12 位，因为不再需要前 4 位）和相应字符串文件中字符串的偏移量。这意味着（而不是平均每个 208 KiB 的 65536 个文件）您将拥有 65536 个哈希文件，每个文件可能 120 KiB 和 65536 个字符串文件，每个文件可能 100 KiB。

接下来，哈希文件应该是二进制格式。12 个十六进制数字需要 48 位（不是 12*8=96 位）。仅此一项就会将哈希文件的大小减半。如果字符串在字符串文件中的 4 字节边界上对齐，那么 16 位“字符串偏移量 / 4”就可以了（只要字符串文件小于 256 KiB）。哈希文件中的条目应按顺序排序，对应的字符串文件应按相同顺序排列。

在所有这些变化之后；您将使用哈希的最高 16 位来找到正确的哈希文件，加载哈希文件并进行二进制搜索。然后（如果找到）您将从哈希文件中的条目中获取字符串开头的偏移量（在字符串文件中），并从哈希文件中的下一个条目中获取下一个字符串的偏移量。然后，您将从字符串文件中加载数据，从正确字符串的开头开始，到下一个字符串的开头结束。

最后，您将在内存中实现“哈希文件缓存”。如果您的应用程序可以分配 1.5 GiB 的 RAM，那么这足以缓存一半的哈希文件。在这种情况下（缓存了一半的哈希文件），您预计一半时间您需要从磁盘加载的唯一内容是字符串本身（例如可能小于 20 个字节），而另一半时间您需要需要先将哈希文件加载到缓存中（例如 60 KiB）；所以平均每次查找你会从磁盘加载大约 30 KiB。当然内存越多越好（越少越好）；如果您可以分配超过 3 GiB 的 RAM，您可以缓存所有哈希文件并开始考虑缓存一些字符串。

一种更快的方法是使用可逆编码，这样您就可以将字符串转换为整数，然后将整数转换回原始字符串，而无需进行任何类型的查找。举个例子；如果您的所有字符串都使用小写 ASCII 字母并且是最大值。13 个字符长，那么它们都可以转换为 64 位整数并返回（如 26^13 < 2^63）。这可能会导致一种不同的方法——例如，在可能的情况下使用可逆编码（整数/散列的第 64 位清除）；并且仅对无法以可逆方式编码的字符串使用某种查找（使用整数/哈希集的第 64 位）。只需一点知识（例如，为您的字符串仔细选择最佳可逆编码），这可以将您的 13 GiB 文件的大小缩减到“小到足以轻松放入 RAM”

于 2013-01-26T10:17:06.420 回答
0

当您将整个性能优化移至数据库时，您的最后一个解决方案可能是最容易实现的解决方案（通常它们为此进行了优化）。

strstr在这里没有用，因为它搜索字符串，但您知道特定格式并且可以跳转和比较更多面向目标的内容。关于strncmp, 和strchr。

读取单行的开销会非常高（文件 IO 经常出现这种情况）。所以我建议阅读更大的块并对该块执行搜索。我什至会考虑通过读取另一个线程中的下一个块来并行化搜索，并在那里进行比较。

您还可以考虑使用内存映射 IO 代替标准 C 文件 API。使用它，您可以将整个内容加载到操作系统，而不必关心自己的缓存。

当然，重组数据以加快访问速度也会对您有所帮助。例如插入填充字节，以便所有数据集都一样长。这将为您提供对数据流的“随机”访问，因为您可以轻松计算第 n 个条目的位置。

于 2013-01-26T07:34:52.983 回答