高效地确定字符串的一部分是否在列表/字典键中？

Question

我有一个包含很多（>100,000）小写字符串的列表，其中一个子集可能如下所示：

str_list = ["hello i am from denmark", "that was in the united states", "nothing here"]

我进一步有这样一个字典（实际上它将具有约1000的长度）：

dict_x = {"denmark" : "dk", "germany" : "ger", "norway" : "no", "united states" : "us"}

对于列表中包含字典键的所有字符串，我希望用相应的字典值替换整个字符串。因此，预期结果应为：

str_list = ["dk", "us", "nothing here"]

考虑到字符串数量和字典长度，最有效的方法是什么？

额外信息：一个字符串中从不会有超过一个字典键。

- Emjora

---

你是真的为每个字符串都有一个变量，还是它们在列表或其他什么东西中？ - Ma0

它们在一个列表中，抱歉。 - Emjora

请提供一个完整的示例来说明你的意思——包括所有数据和相关代码、预期输出和实际输出。参考 如何创建一个最小、完整且可验证的示例。 - Rory Daulton

我认为所需的行为很清晰。问题是：“最有效的方法是什么？” - jferard

由于我无法详细回答，这里是我的想法：您需要一种多字符串搜索算法。Aho-Corasick或Rabin-Karp是更常见的算法。您可以轻松地找到相关库。 - jferard

Answer 1

这似乎是一种不错的方法：

input_strings = ["hello i am from denmark",
                 "that was in the united states",
                 "nothing here"]
dict_x = {"denmark" : "dk", "germany" : "ger", "norway" : "no", "united states" : "us"}

output_strings = []

for string in input_strings:
    for key, value in dict_x.items():
        if key in string:
            output_strings.append(value)
            break
    else:
        output_strings.append(string)
print(output_strings)

- mrCarnivore

---

很好地在for循环中使用了else，并且采用了坚实的基础方法。+1 - Ma0

小细节：如果不考虑空格或单词边界，使用“in”会产生误报：例如，键“france”将匹配“hello my name is francesca”。 - jez

@jez：你说得没错。对此的解决方案取决于实际的输入数据和它所具有的限制条件。 - mrCarnivore

你可以说 if key in string.split()，但是这样会有性能损失。 - jez

@jez 如果你使用 split，你会失去 "united states"。 - Ma0

Answer 2

像这样的代码可以运行。注意，这将把字符串转换为符合条件的第一个键。如果有多个键符合条件，则可能需要根据您的特定情况修改逻辑。

strings = [str1, str2, str3]
converted = []
for string in strings:
    updated_string = string
    for key, value in dict_x.items()
        if key in string:
            updated_string = value
            break
    converted.append(updated_string)
print(converted)

- Mark Beilfuss

Answer 3

尝试

str_list = ["hello i am from denmark", "that was in the united states", "nothing here"]

dict_x = {"denmark" : "dk", "germany" : "ger", "norway" : "no", "united states" : "us"}

for k, v in dict_x.items():
    for i in range(len(str_list)):
        if k in str_list[i]:
            str_list[i] = v

print(str_list)

这会遍历你的字典中的键值对，并查看该键是否在字符串中。如果是，则用对应的值替换字符串。

- Superspork

Answer 4

假设：

lst = ["hello i am from denmark", "that was in the united states", "nothing here"]
dict_x = {"denmark" : "dk", "germany" : "ger", "norway" : "no", "united states" : "us"}

您可以做：

res = [dict_x.get(next((k for k in dict_x if k in my_str), None), my_str) for my_str in lst]

它返回：

print(res)  # -> ['dk', 'us', 'nothing here']

这个东西的酷处（除了它是 Python 忍者最喜欢的武器之一，即列表推导式）在于使用默认值为 my_str 的 get 和带有 None 值的 StopIteration 的 next，会触发上述默认值。

- Ma0

---

应该更快（不使用get）：[next((v for k,v in dict_x.items() if k in my_str), my_str) for my_str in lst] - jferard

@jferard，我认为遍历字典不会比使用“get”更快。 - Ma0

@Ev.Kounis 我不知道Python字典实现的细节，但通常哈希表是一组指向成对（键，值）的链表的引用数组（每个列表的键具有相同的哈希值）。如果您遍历键，则需要获取数组的每个单元格，然后探索每个列表。检索值是一个无成本操作。在您的内部列表推导中，您遍历键。然后，您取第一个键，哈希它，转到单元格并再次探索列表以查找值。我只是遍历（键，值）对并取第一对。 - jferard

使用 dis 模块进行确认会更好... - jferard

@Ev.Kounis 对不起：你是正确的。请参见https://dev59.com/Rqrka4cB1Zd3GeqPa0FB - jferard

Answer 5

你可以创建 dict 的子类并使用列表推导式。

就性能而言，我建议您尝试几种不同的方法，看看哪种方法效果最好。

class dict_contains(dict):
    def __getitem__(self, value):
        key = next((k for k in self.keys() if k in value), None)
        return self.get(key)

str1 = "hello i am from denmark"
str2 = "that was in the united states"
str3 = "nothing here"

lst = [str1, str2, str3]

dict_x = dict_contains({"denmark" : "dk", "germany" : "ger", "norway" : "no", "united states" : "us"})

res = [dict_x[i] or i for i in lst]

# ['dk', 'us', "nothing here"]

- jpp