python - 匹配子字符串是否存在于 python 字典的键中的最佳方法

Question

我有一个 Python 字典，其示例结构如下(摘录):

items = {
    "Google": "Mountain View",
    "Johnson & Johnson": "New Brunswick",
    "Apple": "Cupertino",
}

现在我得到的是一个字符串，即str1。我想要做的是查看字典 items 中的任何键是否存在于字符串 str1 中，例如，如果我有一个字符串 Where is Google based出？。最初我写了这个伪代码:

for str_word in str1.split():
    if str_word in items:
       print("Key found. Value is = ".format(items[str_word]))

现在这很好，因为字典键被索引/散列。所以 in 运算符运行时是不变的，但正如您所注意到的，这适用于 Google 或 Apple 之类的词，但不适用于 Johnson & Johnson(如果我的字符串是Where is Jonhnson & Johnson based of?)。

我能想到的另一种方法是首先从字典中提取所有键，然后逐个迭代每个键，看看它是否存在于 str1 中(与第一种方法)。这会增加运行时间，因为我的字典很大，有成百上千个键。

我想知道是否有一种方法可以修改我的第一种计数方法，以便能够将子字符串与可能包含多个单词的字典的键匹配，例如 Johnson & Johnson ？

Answer 1

如果您的字典没有改变，而您的输入字符串却改变了(您希望在其中找到键作为子字符串的那个)，最快的方法之一是使用 Aho-Corasick algorithm .

算法的第一步是对字典中的字符串进行预处理，这与输入字符串无关，仅在 O(m) 时间和空间内完成一次，其中 m 是字典中键的长度之和。

然后，该算法将在 O(n + m + k) 中找到输入字符串中的所有出现，其中 n 是输入字符串的长度，k 是任何键作为输入字符串的子字符串出现的总次数。

您可以搜索 Aho-Corasick 算法的 Python 实现，这样您只需将其集成到您的代码中，而无需重写。