Trova oggetti del dizionario i cui incontri una stringa chiave

Question

Ho un dizionario di grandi dimensioni costruito in questo modo:

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

Come posso restituire tutte programs cui chiave menzioni "New York" (case insensitive) - che nell'esempio di cui sopra , restituirei tutti e tre gli articoli.

MODIFICA: Il dizionario è abbastanza grande e dovrebbe aumentare nel tempo.

Answer 1

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

Answer 2

Un iteritems e un'espressione generatore farà questo:

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

uscita:

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

Answer 3

Si potrebbe generare tutte le stringhe prima del tempo, e mapparli alle rispettive chiavi.

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

Poi si può ricerca substrings per ottenere le chiavi che contengono quella stringa:

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

Pro:

• ottenere le chiavi di stringa è veloce come l'accesso a un dizionario.

Contro:

• Generazione substrings incorre un costo una tantum all'inizio del vostro programma, prendendo tempo proporzionale al numero di chiavi in ​​programs.
• substrings crescerà approssimativamente in modo lineare con il numero di chiavi in ​​programs, aumentando l'utilizzo della memoria dello script.
• genSubstrings ha prestazioni O (n^2) in relazione alla dimensione della chiave. Ad esempio, "Port Authority of New York" genera 351 sottostringhe.

Answer 4

È necessario utilizzare il metodo forza bruta fornito da mensi finché non si rivela troppo lento.

Ecco qualcosa che duplica i dati per dare una rapida occhiata. Funziona solo se la tua ricerca è solo per parole intere, cioè non dovrai mai abbinare su "New Yorks Best Bagels" perché "york" e "yorks" sono parole diverse.

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] 

Se le parole devono essere in sequenza (vale a dire "New York" non deve corrispondere) è possibile applicare il metodo di forza bruta alla breve lista di result_keys.

Answer 5

Questo è solitamente chiamato un dizionario rilassato e può essere implementato in modo efficiente utilizzando un albero di suffisso.

La memoria utilizzata da questo approccio è lineare sui tasti, che è ottimale, e il tempo di ricerca è lineare sulla lunghezza della sottostringa che si sta cercando, che è anche ottimale.

Ho trovato questa libreria in python che implementa questo.

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

Esattamente