Python中的高性能质量短字符串搜索

Question

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

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

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

但是当A包含~500,000或更多项目时,它会变得非常慢.

是否有适合此问题的库或算法？我尽力搜索但没有运气.

谢谢!

Answer 1

你的问题足够大,你可能需要用算法蝙蝠击中它.

看看Aho-Corasick算法.您的问题陈述是对该算法所解决的问题的解释.

另外,请看Nicholas Lehuen的PyTST软件包.

在相关的Stack Overflow消息中还提到了其他算法,如Rabin-Karp:线性模式匹配算法？