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

Question

我有一个像这样构造的大字典:

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

如何返回programs其键提到"纽约"(不区分大小写)的所有元素？在上面的例子中,我想要获得所有这三个项目.

编辑:字典非常大,预计会随着时间的推移而变大.

Answer 1

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

Answer 2

这通常称为宽松字典,可以使用后缀树有效地实现.

此方法使用的内存在键上是线性的,这是最佳的,并且搜索时间在您搜索的子字符串长度上是线性的,这也是最佳的.

我在python中找到了这个实现它的库.

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

Answer 3

和iteritems生成器表达式将执行此操作：

d={'New York':'some values',
    'Port Authority of New York':'some more values',
    'New York City':'lots more values'}

print list(v for k,v in d.iteritems() if 'new york' in k.lower())    

输出：

['lots more values', 'some more values', 'some values']

Answer 4

您可以提前生成所有子字符串，并将它们映射到各自的键。

#generates all substrings of s.
def genSubstrings(s):
    #yield all substrings that contain the first character of the string
    for i in range(1, len(s)+1):
        yield s[:i]
    #yield all substrings that don't contain the first character
    if len(s) > 1:
        for j in genSubstrings(s[1:]):
            yield j

keys = ["New York", "Port Authority of New York", "New York City"]
substrings = {}
for key in keys:
    for substring in genSubstrings(key):
        if substring not in substrings:
            substrings[substring] = []
        substrings[substring].append(key)

然后您可以查询substrings以获取包含该子字符串的键：

>>>substrings["New York"]
['New York', 'Port Authority of New York', 'New York City']
>>> substrings["of New York"]
['Port Authority of New York']

优点：

• 通过子字符串获取键与访问字典一样快。

缺点：

• 生成会substrings在程序开始时产生一次性成本，所需时间与 中的键数量成正比programs。
• substrings将随着 中的键数量近似线性增长programs，从而增加脚本的内存使用量。
• genSubstrings与密钥大小相关的性能为 O(n^2)。例如，“纽约港务局”生成 351 个子字符串。

Answer 5

你应该使用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"不匹配),您可以将蛮力方法应用于短名单result_keys.