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

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

现在我拥有的是一个字符串,即str1.我想要做的是查看字典项中的任何键是否存在于字符串str1中,例如,如果我有一个像Google这样的字符串的字符串？最初我写了这个伪代码：

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

现在这很好,因为字典键被索引/散列.所以in运算符运行时是不变的,但你可以注意到这适用于谷歌或苹果这样的词,但这对Johnson&约翰逊(如果我的字符串是Jonhnson& Johnson在哪里？).

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

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

解决方法:

如果你的字典没有改变,而你的输入字符串确实(你要在其中找到键作为子字符串),最快的方法之一就是使用Aho-Corasick algorithm.

算法的第一步是预处理字典中的字符串,这在O(m)时间和空间中只与输入字符串一起完成一次,其中m是字典中键的长度之和.

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

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