代码之家 › 专栏 › 技术社区 › user2966197

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

lookup dictionary string python

user2966197 · 技术社区 · 7 年前

我有一本Python字典,其示例结构如下(节选):

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

现在我有一根绳子 str1 .我想做的是看看字典里的任何一个键 items 以字符串形式出现 str1 ,例如,如果我有一个字符串 Where is Google based out of? .最初我写了这个伪代码:

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

现在这很好,因为字典键被索引/哈希。所以 in operator runtime是常量,但正如您所注意到的,它适用于诸如 Google 或 Apple 但这对我来说是行不通的 Johnson & Johnson (如果我的绳子 Where is Jonhnson & Johnson based out of? ).

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

我想知道是否有一种方法可以修改我的第一种计数方法,以便能够将子字符串与可能包含多个单词的字典的键相匹配,例如 强生公司;约翰逊 ?

4 回复 | 直到 7 年前

Nisba 7 年前

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

算法的第一步是对字典中的字符串进行预处理,这一步只进行一次,与输入字符串无关 O(m) 时间和空间,在哪里 m 是字典中键的长度之和。

然后,该算法将在 O(n + m + k) 哪里 n 是输入字符串的长度,并且 k 是任何键作为输入字符串的子字符串出现的总数。

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

cap 7 年前

如果你的字符串总是相同的/有一个结构,你可以使用正则表达式来匹配你要找的键。

import re

string = 'Where is Johnson and Johnson based out of?'
match = re.search(r'Where is (.*) based out of?',string)
key = match.group(1)

当然,你应该修改它以符合你的需要。

否则,我想我会使用您的方法,迭代dict键,看看它们是否与字符串匹配。分裂 str1 例如,如果您有多把钥匙,可能会给您带来麻烦 & .

abc 7 年前

一种方法可以是:

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

words = "Where is Johnson & Johnson based out of?".rstrip("?").split()

#find the max number of words in a key
len_max = max([len(s.split()) for s in items])

#split the sentence in consecutive words according to the maximum number of words in a key, i.e., in consecutive groups of size 1,2,...,len_max_words_in_key
to_check = [" ".join(words[i:i+j]) for j in range(1,len_max + 1) for i in range(0,len(words)+1-j)]


#check for the key
for el in to_check:
     if el in items:
        print("Key found. Value is = {}".format(items[el]))

由于句子很短,需要检查的数量很少。
例如,对于 20 单词和一个由最多 5 你的话 90 = (20 + 19 + 18 + 17 + 16) 查字典。

Mohammad Mahdi Hatami 7 年前

对于字典中的多模式匹配,推荐的解决方案是 Aho-Corasick , 用于静态和动态模式匹配的aho-corasick算法

还有,你可以用这个 solution 基于后缀树的动态模式匹配