c++ - 在大型文本文件中搜索数千个字符串

Question

我有一个 20 GB 的大文本文件。该文件包含相对较短的文本行(每行 40 到 60 个字符)。文件未排序。

我有一个包含 20,000 个唯一字符串的列表。我想知道每个字符串每次出现在文件中时的偏移量。目前，我的输出如下所示:

netloader.cc found at offset: 46350917
netloader.cc found at offset: 48138591
netloader.cc found at offset: 50012089
netloader.cc found at offset: 51622874
netloader.cc found at offset: 52588949
...
360doc.com found at offset: 26411474
360doc.com found at offset: 26411508
360doc.com found at offset: 26483662
360doc.com found at offset: 26582000

我将 20,000 个字符串加载到 std::set 中(以确保唯一性)，然后从文件中读取 128MB 的 block ，然后使用 string::find 搜索字符串(通过读取另一个 128MB 的 block 重新开始).这将在大约 4 天内工作并完成。我不担心读取边界可能会破坏我正在搜索的字符串。如果是这样，那没关系。

我想让它更快。在 1 天内完成搜索是最理想的，但任何显着的性能改进都会很好。我更喜欢将标准 C++ 与 Boost(如有必要)结合使用，同时避免使用其他库。

所以我有两个问题:

1. 考虑到我使用的工具和任务，4 天时间是否合理？
2. 加快速度的最佳方法是什么？

谢谢。

编辑:使用 Trie 解决方案，我能够将运行时间缩短到 27 小时。不是一天之内，但现在肯定快得多。感谢您的建议。

Answer 1

从算法上讲，我认为解决此问题的最佳方法是使用树来存储要一次搜索字符的行。例如，如果您有以下想要查找的模式:

hand, has, have, foot, file

生成的树看起来像这样:

树的生成是最坏情况下的 O(n)，并且通常具有亚线性内存占用。

使用这种结构，您可以通过从您的大文件中一次读入一个字符来开始处理您的文件，然后遍历树。

• 如果您到达叶节点(以红色显示的节点)，您就找到了一个匹配项，并且可以存储它。
• 如果没有子节点，对应你有红色的字母，你可以丢弃当前行，从树的根开始检查下一行

此技术将导致线性时间 O(n) 来检查匹配并仅扫描一次巨大的 20gb 文件。

编辑

上述算法肯定是合理的(它不会给出误报)但不是完整的(它可能会遗漏一些结果)。但是，假设我们没有具有共同词根(如 go 和 gone)的搜索词，通过一些小的调整就可以使它变得完整。以下为完整版算法的伪代码

tree = construct_tree(['hand', 'has', 'have', 'foot', 'file'])
# Keeps track of where I'm currently in the tree
nodes = []
for character in huge_file:
  foreach node in nodes:
    if node.has_child(character):
      node.follow_edge(character)
      if node.isLeaf():
        # You found a match!!
    else:
      nodes.delete(node)
  if tree.has_child(character):
    nodes.add(tree.get_child(character))

请注意，每次必须检查的节点列表最多是必须检查的最长单词的长度。因此，它不应增加太多复杂性。