使用树快速检查字符串是否包含大型列表中的元素

Question

我有一大堆短字符串（单词），我想检查它们是否出现在另一个字符串（句子）中。请注意，我不关心实际的 words/spaces/punctuation/etc.

这是python中的典型解决方案：

def contains_one_of(sentence, words):
    for word in words:
        if word in sentence:
            return word
    return None

我见过一些 python 单行代码做同样的事情，但从算法上讲，我能找到的所有内容似乎基本上都是为所有元素调用一个 contains 函数。我假设 contains 函数使用一种滑动 window 方法。

我估计的复杂度大约是 O(nmo)

其中 n = 列表长度，m = 句子长度，o = 列表中单词的平均长度

对我来说，我认为这可以用树来改进，但我找不到任何关于这种算法的参考。 我基本上设想单词数组变成一棵树，其中一个节点是一个字母，它的所有子节点都是该单词的下一个字母。只要单词短而且有合理的重叠我认为这样会更有效率。

我已经在 python 中实现了这个版本，但我更愿意使用一个利用 C 来比较所有这些字符的包。 如果您知道此算法的名称或执行此操作的程序包，我很想知道。

这是我的版本，我相信很多地方都可以优化，但我想知道我是否对这里有所了解。

sentence = "hello there cat, welcome home"
words = ["cat", "car", "cam", "arm", "ace", "arc"]

# build a dict tree per letter
def build_tree(patterns):
    root = dict()
    for p in patterns:
        r = root
        for i, c in enumerate(p):
            if c not in r:
                if i >= len(p) - 1: # last element
                    r[c] = p
                else: # any other element
                    r[c] = dict()
            r = r[c]
    return root
            
# Check if the substring starts with a path through the tree
def starts_with_tree(sub, tree):
    level = tree
    for c in sub:
        if c not in level: # nowhere left to go
            return None
        elif isinstance(level[c], str): # if we found a string we are at the end
            return level[c]
        else:
            level = level[c] # go deeper
            

# Check if s contains any path through the tree
def contains_which(s, root):
    for i in range(len(s)):
        sub = s[i:] # A substring missing the first i characters
        result = starts_with_tree(sub, root) 
        if result:
            return result
    return None
        

# build the tree
tree_root = build_tree(words)
print(tree_root)
# search within tree
found = contains_which(sentence, tree_root)
print("Found:", found)

Answer 1

您可以使用 aho-corasick 算法。

它使用 trie 结构（一种树），时间复杂度只是 O(m + o*n)（根据您的定义）（线性时间复杂度与长度和所有字符串）

如果你不熟悉这个算法，这个算法的实现是相当复杂的。所以你可以使用 python 库来获得 aho-corasick pyahocorasick

更多详情

Wikipedia

python aho-corasick library

使用树快速检查字符串是否包含大型列表中的元素

Check if a string contains an elemewnt in a large list quickly using a tree

python

algorithm

tree

contains

您可以使用 aho-corasick 算法。