gpt4 book ai didi

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

转载 作者:搜寻专家 更新时间:2023-10-31 00:16:22 25 4
gpt4 key购买 nike

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

最佳答案

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

hand, has, have, foot, file

生成的树看起来像这样: Tree generated by the list of search terms

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

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

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

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

编辑

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

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

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

关于c++ - 在大型文本文件中搜索数千个字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16360872/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com