2

我有一个 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 小时。不是一天之内，但现在肯定要快得多。感谢您的建议。

4

3 回答 3

3

您描述的问题看起来更像是所选算法的问题，而不是所选技术的问题。在 4 天内对 20GB 进行 20000 次完整扫描听起来并不太合理，但您的目标应该是单次扫描 20GB，再单次扫描 20K 字。

您是否考虑过查看一些字符串匹配算法？Aho-Corasick 浮现在脑海中。

于 2013-05-03T14:22:34.393 回答
3

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

hand, has, have, foot, file

生成的树看起来像这样： 由搜索词列表生成的树

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

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

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

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

编辑

上面描述的算法当然是合理的（它不会给出误报）但并不完整（它可能会错过一些结果）。但是，假设我们没有像go和got这样的具有共同词根的搜索词，则可以通过一些小的调整来完成它。以下是算法完整版的伪代码

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))

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

于 2013-05-03T14:40:39.633 回答
0

与其分别为每个字符串搜索 20,000 次，不如尝试对输入进行标记化并在要查找的std::set字符串中进行查找，这样会快得多。这是假设您的字符串是简单的标识符，但是对于作为句子的字符串可以实现类似的东西。在这种情况下，您将在每个句子中保留一组第一个单词，并在成功匹配后验证它确实是整个句子的开头string::find。

于 2013-05-03T14:29:35.463 回答