Znajdź słownika elementy, których kluczem mecze podciąg

Question

Mam duży słownik skonstruowany tak:

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

Jak mogę zwrócić wszystkie programs którego klucz wymienia „New York” (wielkość liter) - który w powyższym przykładzie , zwróci wszystkie trzy elementy.

EDYCJA: Słownik jest dość duży i oczekuje się, że z czasem będzie większy.

Answer 1

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

Answer 2

iteritems i wyrażenie generator będzie to zrobić:

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())  

wyjściowa:

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

Answer 3

Można wygenerować wszystkie podciągi z wyprzedzeniem i mapować je do odpowiednich klawiszy.

#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) 

Następnie można wyszukać substrings dostać klucze zawierające że podciąg:

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

Zalety:

• coraz klucze według podciągu jest tak szybki jak dostęp do słownika.

Wady:

• Generowanie substrings ponosi koszt jednorazowej na początku programu, biorąc czas proporcjonalny do liczby kluczy w programs.
• substrings będzie rosnąć w przybliżeniu liniowo wraz z liczbą kluczy w numerze programs, zwiększając wykorzystanie pamięci skryptu.
• genSubstrings ma wydajność O (n^2) w stosunku do wielkości klucza. Na przykład "Port Authority of New York" generuje 351 podłańcuchów.

Answer 4

Powinieneś używać metody brute force podanej przez mensi, dopóki nie okaże się ona zbyt wolna.

Oto coś, co powiela dane, aby przyspieszyć wyszukiwanie. Działa tylko wtedy, gdy wyszukiwanie dotyczy tylko całych słów - tzn. Nigdy nie trzeba dopasowywać do "New Yorks Best Bagels", ponieważ "york" i "yorks" to różne słowa.

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] 

Jeśli słowa muszą być w kolejności (czyli „New York” nie powinien dopasowywać) można zastosować metodę brute-force na krótkiej liście result_keys.

Answer 5

Jest to zwykle nazywane rozluźnionym słownikiem i może być efektywnie zaimplementowane przy użyciu drzewa sufiksów.

Pamięć używana przez to podejście jest liniowa w stosunku do klawiszy, co jest optymalne, a czas wyszukiwania jest liniowy w stosunku do długości szukanego podłańcucha, co również jest optymalne.

Znalazłem tę bibliotekę w python, który implementuje to.

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