algorithm - 在大量文件中搜索固定字符串的静态列表

Question

我有大量固定字符串(约 500 万)，我想在很多文件中搜索。

我看到使用有限模式集进行字符串搜索的两种最常用的算法是:Aho-Corasick 和 Commentz-Walter。

我的目标是找到一个完全匹配而不是模式(这意味着字符串列表不是正则表达式)。

经过一些研究，我发现很多文章指出 Commentz-Walter 在现实世界场景中往往比 Aho-Corasick 更快(Article1，Article2)，它也是 背后的算法GNU-grep.

我也尝试以并行方式使用 grep -F(取自 here ):

free=$(awk '/^((Swap)?Cached|MemFree|Buffers):/ { sum += $2 }
          END { print sum }' /proc/meminfo)
percpu=$((free / 200 / $(parallel --number-of-cores)))k
parallel --pipepart -a regexps.txt --block $percpu --compress \
grep -F -f - -n bigfile

看来问题太大了。我收到此错误:

grep: memory exhausted

1. 我考虑过尝试将模式列表拆分为多个文件并为同一个文件运行 grep 多次 - 但它看起来很笨拙。还有其他解决办法吗？或者我没有以正确的方式运行 grep？
2. 通过运行 Commentz-Walter 算法，grep 应该会做一些预处理工作。我假设在两个不同的文件上使用相同的模式文件运行 grep 将导致 grep 执行相同的预处理阶段两次。有没有办法在文件列表上运行 grep 并使其只运行一次模式预处理？
3. 在 c\c++ 中是否有 Commentz-Walter 的良好实现？我只在 python ( here ) 中找到代码？

---更新---

根据一些评论，我尝试测试不同的 Aho-Corasick c\c++ 实现(Komodia、Cjgdev、chasan)，但没有一个能够管理 500 万个模式集示例(全部有内存问题(段错误/堆栈溢出))——它们在小集合上工作。示例文件由以下代码生成:

with open(r"C:\very_large_pattern", 'w') as out:
for _ in range(0, 5000000):
    out.write(str(uuid.uuid4()) + '\n')

有人对可以处理这些数字的实现有什么建议吗？

Answer 1

这是一个应该很快的简单解决方案。

将要搜索的固定长度字符串逐行放入文件中，并对文件进行排序。将该文件称为 S。

对于您要搜索的每个文件，执行以下操作:

1. 如果要搜索的字符串的长度为 k，则将文件分成每个可能的长度为 k 的字符串。将该文件称为 B。例如，如果 k = 5，则要搜索的文件是:

   abcdefgh
   123
   123456
   

   损坏的字符串文件将是:

   abcde
   bcdef
   cdefg
   defgh
   12345
   23456
   

   现在，为了知道每个损坏的字符串在原始文件中的位置，将其行号和列号附加到文件 B 中。例如，

   abcde 1 1
   bcdef 1 2
   cdefg 1 3
   defgh 1 4
   12345 3 1
   23456 3 2
   

2. 对B进行排序，并将其与S合并。将生成的文件称为M。例如，如果S是:

   23456
   cdefg
   

   M 将是:

   12345 3 1
   23456
   23456 3 2
   abcde 1 1
   bcdef 1 2
   cdefg
   cdefg 1 3
   defgh 1 4
   

3. 从 M 中检索在文件中找到的所有出现的 S 的字符串。例如:

   23456
   23456 3 2
   cdefg
   cdefg 1 3
   

   如果一个字符串有多次出现，你可以得到所有的。

我不知道您使用的是什么操作系统，但上述步骤很可能可以使用 sort、awk、grep 等命令执行。