Encontrar los elementos del diccionario cuyos partidos una subcadena clave

Question

un gran diccionario que han construido de esta manera:

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

¿Cómo puedo devolver todo programs cuya clave menciones de "Nueva York" (mayúsculas y minúsculas) - que en el ejemplo anterior , devolvería los tres elementos.

EDITAR: El diccionario es bastante grande y se espera que aumente con el tiempo.

Answer 1

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

Answer 2

Un iteritems y una expresión generadora va a hacer esto:

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

Salida:

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

Answer 3

Se podría generar todas las subcadenas de antemano, y asignarlos a sus respectivas llaves.

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

A continuación, puede consultar substrings para obtener las claves que contienen esa subcadena:

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

Pros:

• conseguir llaves por subcadena es tan rápido como el acceso a un diccionario.

Contras:

• Generación substrings incurre en un costo de una sola vez al comienzo de su programa, teniendo un tiempo proporcional al número de llaves en programs.
• substrings crecerá aproximadamente de forma lineal con el número de teclas en programs, aumentando el uso de la memoria de su secuencia de comandos.
• genSubstrings tiene un rendimiento O (n^2) en relación con el tamaño de su clave. Por ejemplo, "Autoridad Portuaria de Nueva York" genera 351 subcadenas.

Answer 4

Debe utilizar el método de fuerza bruta proporcionado por mensi hasta que demuestre que es demasiado lento.

Aquí hay algo que duplica los datos para obtener una búsqueda más rápida. Solo funciona si su búsqueda es solo para palabras enteras, es decir, nunca tendrá que coincidir con "New Yorks Best Bagels" porque "york" y "yorks" son palabras diferentes.

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] 

Si las palabras tienen que estar en secuencia (es decir, "Nueva York" no debe coincidir) se puede aplicar el método de fuerza bruta a la lista corta de result_keys.

Answer 5

Esto se suele llamar un diccionario relajado y se puede implementar de manera eficiente utilizando un árbol de sufijos.

La memoria utilizada por este enfoque es lineal sobre las teclas, lo que es óptimo, y el tiempo de búsqueda es lineal sobre la longitud de la subcadena que está buscando, lo que también es óptimo.

He encontrado esta biblioteca en python que implementa esto.

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