Buscar elementos del diccionario cuya clave coincida con una subcadena

Tengo un gran diccionario construido así:

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

¿Cómo puedo devolver todos los elementos de los programs cuya clave menciona “new york” (no distingue mayúsculas y minúsculas)? En el ejemplo anterior, me gustaría obtener los tres elementos.

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

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

Esto generalmente se denomina 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, que es óptima, y ​​el tiempo de búsqueda es lineal sobre la longitud de la subcadena que está buscando, que también es óptima.

He encontrado esta biblioteca en python que implementa esto.

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

Debes usar el método de fuerza bruta dado por mensi hasta que se demuestre que es demasiado lento.

Aquí hay algo que duplica los datos para dar una búsqueda más rápida. Solo funciona si su búsqueda es solo para palabras completas, es decir, nunca tendrá que coincidir en “Los mejores bagels de Nueva York” 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, “York New” no debe coincidir), puede aplicar el método de fuerza bruta a la lista corta de result_keys .

Un iteritems y una expresión generadora harán 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'] 

Podría generar todas las subcadenas antes de tiempo y asignarlas a sus claves respectivas.

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

Luego 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:

  • obtener claves por subcadena es tan rápido como acceder a un diccionario.

Contras:

  • La generación de substrings incurre en un costo de una sola vez al comienzo de su progtwig, tomando un tiempo proporcional al número de teclas en los programs .
  • substrings crecerán aproximadamente de forma lineal con la cantidad de claves en los programs , lo que boostá el uso de memoria de su script.
  • genSubstrings tiene un genSubstrings O (n ^ 2) en relación con el tamaño de su clave. Por ejemplo, “Port Authority of New York” genera 351 subcadenas.