Вопрос по python – Найти элементы словаря, ключ которых соответствует подстроке

29

У меня есть большой словарь, построенный так:

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

Как я могу вернуть все элементыprograms чей ключ упоминает «Нью-Йорк»; (без учета регистра)? В приведенном выше примере я хотел бы получить все три элемента.

EDIT: Словарь довольно большой, и со временем ожидается его увеличение.

Ваш Ответ

5   ответов
58

[value for key, value in programs.items() if 'new york' in key.lower()]
Именно так. Просто не ожидайте, что он будет быстрым, если ваш словарь большой.
@MarkRansom Я собирался добавить, что мой словарь довольно большой и, как ожидается, станет больше. Это делалprograms.get('new york') до сих пор, который был очень быстрым. Abid A
@mensi. Благодарю. Я делаю изменение сейчас, чтобы увидеть, как оно работает. Я также рассмотрю другие структуры данных. Abid A
Этот ответ также может быть заключен в любое условие, чтобы получить логическое значение для того, содержит ли какой-либо ключ в dict предоставленную подстроку / условие:any([x for x in programs if 'new york' in x.lower()])
Если просмотр всех ключей в словаре слишком медленный для вашего приложения, вам нужно создать структуру данных, ориентированную на этот тип запроса. Вероятно, это будет какой-то словесный инвертированный индекс или суффиксное дерево.
3

iteritems и выражение генератора сделает это:

    '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

MENSI пока он не окажется слишком медленным.

Здесь что-то, что дублирует данные, чтобы ускорить поиск. Это работает только в том случае, если ваш поиск выполняется только по целым словам, т. Е. Вам никогда не понадобится совпадать с "Лучшими рогаликами Нью-Йорка" & quot; потому что "йорк" и "йорки" это разные слова.

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.

Очень классное предложение, Марк. Благодарю. Abid A
2

етствующими ключами.

#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 con,tain 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']

Плюсы:

getting keys by substring is as fast as accessing a dictionary.

Минусы:

Generating substrings incurs a one-time cost at the beginning of your program, taking time proportional to the number of keys in programs. substrings will grow approximately linearly with the number of keys in programs, increasing the memory usage of your script. genSubstrings has O(n^2) performance in relation to the size of your key. For example, "Port Authority of New York" generates 351 substrings.
Error: User Rate Limit Exceeded Abid A
8

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

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

Я нашел эту библиотеку в Python, который реализует это.

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededhashcollision.org/hkn/python/suffix_treesError: User Rate Limit Exceeded

Похожие вопросы