Найти словарные статьи, чей ключ соответствует подстроке

Ответ 1

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

Ответ 2

Обычно это называется расслабленным словарем, и его можно эффективно реализовать с помощью дерева суффиксов.

Память, используемая этим подходом, является линейной над ключами, которая является оптимальной, а время поиска является линейным по длине подстроки, которую вы ищете, что также является оптимальным.

Я нашел эту библиотеку в python, которая реализует это.

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

Ответ 3

Вы должны использовать метод грубой силы, указанный mensi, пока он не окажется слишком медленным.

Здесь что-то дублирует данные, чтобы ускорить поиск. Он работает только в том случае, если ваш поиск предназначен только для целых слов, т.е. Вам никогда не придется сопоставлять "New Yorks Best Bagels", потому что слова "york" и "york" - это разные слова.

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.

Ответ 4

An 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']

Ответ 5

Вы можете сгенерировать все подстроки раньше времени и сопоставить их с соответствующими ключами.

#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, увеличивая использование памяти вашего script.
• genSubstrings имеет производительность O (n ^ 2) по отношению к размеру вашего ключа. Например, "Port Authority of New York" генерирует 351 подстроки.