搜索大型文本文件中的数千个字符串

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块，并使用string :: find搜索字符串（通过读取另一个128MB块重新开始）。 这个方法可以工作并在大约4天内完成。 我不担心读取边界可能会破坏我正在搜索的字符串。 如果发生这种情况，没关系。

我想让它更快。 在1天内完成搜索是理想的，但任何显着的性能改进都很好。 我喜欢使用标准C ++和Boost（如果必要），同时避免其他库。

所以我有两个问题：

1.考虑到我正在使用的工具和任务，4天时间是否合理？

2.使其更快的最佳方法是什么？

谢谢。

编辑：使用Trie解决方案，我能够将运行时间缩短到27小时。虽然没有在一天之内完成，但现在速度快多了。 感谢您的建议。

- user1356386

---

这些字符串看起来像是单词或标识符，而不是整个句子，用空格分隔等吗？ - piokuc

你尝试过对你的代码进行性能分析吗？它是在搜索还是从输入文件中读取数据时花费更多时间？ - OGH

读取20GB的数据不可能需要4天时间... - piokuc

他说他正在读取128MB的块，并在移动到下一个块之前在一个块中执行20k次搜索，这就是我理解的方式。 - piokuc

@piokuc 是的，但我不确定他是否在整个块中检查单个字符串，例如 bufferedData.find(searchStrings[i])，这仍然涉及搜索大量数据，因为它将搜索每个块20,000次。 - SlxS

Answer 1

从算法上来看，我认为解决这个问题最好的方法是使用树来存储每一行需要逐个字符搜索的模式。例如，如果您要查找以下模式：

hand, has, have, foot, file

生成的树看起来像这样： 生成树的最坏情况时间复杂度为O(n)，并且通常具有次线性内存占用。

使用此结构，您可以通过从大文件中逐个字符读取并遍历树来开始处理您的文件。

• 如果到达叶子节点（显示为红色的节点），则表示找到了匹配项，可以将其存储。
• 如果没有与您读入的字母对应的子节点，则可以丢弃当前行，并从树的根部开始检查下一行。

使用此技术，匹配项和扫描20GB巨型文件的检查仅需要线性时间O(n)。

编辑

上述算法确实是正确的（不会产生假阳性），但不完整（可能会错过一些结果）。然而，通过进行一些微小的调整，它可以变得完整，假设我们没有具有共同词根（如“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))

请注意，每次需要检查的节点列表最多只有与之进行比较的最长单词的长度。因此，这不应增加太多复杂性。

- decden

---

+1 这可能比Nico的建议（Aho-Corasick）更容易实现，而且仍然可以比当前的方法大大提高速度。顺便说一句，解释得很好。 - syam

当然你可以一次读取一块数据，只需要逐个字符地检查每个块，这是在RAM中顺序完成的，因此不会对IO造成太大压力。 - decden

Answer 2

您所描述的问题更像是选择算法的问题，而不是技术选择的问题。4天内对20GB进行20000次完整扫描听起来并不过分，但您的目标应该是对20GB进行单次扫描以及对20K个单词进行单次扫描。

您考虑过查看一些字符串匹配算法吗？Aho-Corasick算法比较常用。

- Nico Brailovsky

Answer 3

与其分别搜索20000次每个字符串，你可以尝试对输入进行标记化，并在要查找的字符串组成的std::set中进行查找，这样会快得多。这是假设你的字符串是简单标识符的情况，但类似的方法也可用于句子字符串。在这种情况下，您将保留每个句子中的第一个单词的集合，并在成功匹配后验证它是否真正是整个句子的开头，使用string::find函数实现。

- piokuc