python - Python 中的高性能海量短字符串搜索

Question

问题:A 提供了一个大的静态字符串列表，B 提供了一个长字符串，A 中的字符串是都非常短(关键字列表)，我想检查 A 中的每个字符串是否都是 B 的子字符串并获取它们。

现在我使用一个简单的循环，例如:

result = []
for word in A:
    if word in B:
        result.append(word)

但是当 A 包含 ~500,000 或更多项时，它的速度非常慢。

是否有适合这个问题的库或算法？我已尽力搜索但没有成功。

谢谢!

Answer 1

您的问题足够大，您可能需要使用算法 bat 来解决它。

查看 Aho-Corasick算法。您的问题陈述是对该算法解决的问题的释义。

另外，看看 Nicholas Lehuen 和他的作品 PyTST包。

在相关的 Stack Overflow 消息中也有提到其他算法(如 Rabin-Karp)的引用:Algorithm for linear pattern matching?