查找其键与子字符串匹配的词典项

Question

我有一本大字典，结构如下：

programs['New York'] = 'some values...' 
programs['Port Authority of New York'] = 'some values...' 
programs['New York City'] = 'some values...'
...

如何返回键提到“new york”（不区分大小写）的programs的所有元素？在上面的例子中，我想得到这三个项目。

编辑：字典很大，预计随着时间的推移会变大。

Answer 1

您应该使用mensi给出的蛮力方法，直到证明它太慢为止。

这里有一些重复的数据，以提供一个更快的查找。只有当你只搜索整个单词时，它才起作用——也就是说，你永远不需要匹配“纽约最好的百吉饼”，因为“约克”和“约克”是不同的单词。

words = {}
for key in programs.keys():
    for w in key.split():
        w = w.lower()
        if w not in words:
            words[w] = set()
        words[w].add(key)


def lookup(search_string, words, programs):
    result_keys = None
    for w in search_string.split():
        w = w.lower()
        if w not in words:
            return []
        result_keys = words[w] if result_keys is None else result_keys.intersection(words[w])
    return [programs[k] for k in result_keys]

如果单词必须按顺序排列（即“York New”不应匹配），则可以将brute force方法应用于result_keys的短列表。

Answer 2

[value for key, value in programs.items() if 'new york' in key.lower()]

Answer 3

这通常被称为松弛字典，它可以使用后缀树有效地实现。

这种方法使用的内存在键上是线性的，这是最优的，搜索时间在您正在搜索的子串长度上是线性的，这也是最优的。

我在python中找到了实现这个功能的库。

https://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/