Python: búsqueda de claves principales para un valor específico en un diccionario nested

Estoy luchando para procesar un diccionario nested, y devolver las Claves principales anidadas, para un Valor específico, cuando el Valor puede existir más de una vez en el diccionario nested. Por ejemplo:

example_dict = { 'key1' : 'value1', 'key2' : 'value2', 'key3' : { 'key3a': 'value3a' }, 'key4' : { 'key4a': { 'key4aa': 'value4aa', 'key4ab': 'value4ab', 'key4ac': 'value1'}, 'key4b': 'value4b'} } 

Notará que ‘value1’ aparece dos veces en el diccionario anterior, y me gustaría crear una función que devuelva una sola lista o una serie de listas que identifiquen las diferentes Claves principales, que en este caso sería ‘key1 ‘y (‘ key4 ‘,’ key4a ‘, key4ac).

Este tipo de problema se trató en otra parte de este sitio, cuando el valor que buscaba solo apareció una vez, y fue manejado fácilmente por la siguiente función recursiva:

 def find_key(d,key): for k,v in d.items(): if isinstance(v,dict): p = find_key(v,key) if p: return [k] + p elif v == key: return [k] print find_key(example_dict,'value4ac'). 

Si ejecuta el código anterior en el diccionario, solo obtengo una respuesta para las claves principales. Cualquier ayuda sería muy apreciada, gracias!

A menos que solo esté haciendo una sola búsqueda (o que esté increíblemente limitado en la memoria pero tenga tiempo de CPU para grabar …), querrá crear un diccionario de búsqueda inversa, y luego puede usarlo.


Para hacerlo más fácil, lo voy a hacer en dos pasos. Primero, convierta un diccionario nested en un diccionario de ruta de acceso clave:

 def keypaths(nested): for key, value in nested.iteritems(): if isinstance(value, collections.Mapping): for subkey, subvalue in keypaths(value): yield [key] + subkey, subvalue else: yield [key], value 

Imprima la list(keypaths(example_dict)) si no es obvio lo que esto hace.


Ahora, ¿cómo creas un diccionario inverso? Para un mapeo uno a uno, puedes hacer esto:

 reverse_dict = {value: keypath for keypath, value in keypaths(example_dict)} 

Pero para una asignación de muchos a uno como la suya, lo contrario es uno a muchos, por lo que necesitamos asignar cada valor a una lista de claves. Asi que:

 reverse_dict = {} for keypath, value in keypaths(example_dict): reverse_dict.setdefault(value, []).append(keypath) 

Y ahora no necesitas nada lujoso; simplemente haga una búsqueda normal de reverse_dict en reverse_dict :

 >>> reverse_dict['value2'] [('key2',)] >>> reverse_dict['value1'] [('key1',), ('key4', 'key4a', 'key4ac')] >>> reverse_dict['value3'] KeyError: 'value3' 

Si prefiere que el último devuelva [] lugar de generar un KeyError , puede usar un valor defaultdict(list) lugar de un dict simple, y entonces no necesita setdefault .


En cualquier caso, el tiempo necesario para construir este mapeo inverso es solo un poco más largo que el tiempo necesario para realizar una única búsqueda por fuerza bruta, por lo que si realiza 100 búsquedas, será casi 100 veces más rápido de esta manera, ya que así como más sencillo.

Aquí hay una solución:

 from copy import copy example_dict = { 'key1' : 'value1', 'key2' : 'value2', 'key3' : { 'key3a': 'value3a' }, 'key4' : { 'key4a': { 'key4aa': 'value4aa', 'key4ab': 'value4ab', 'key4ac': 'value1'}, 'key4b': 'value4b'} } result = [] path = [] def get_keys(d, target): for k, v in d.iteritems(): path.append(k) if isinstance(v, dict): get_keys(v, target) if v == target: result.append(copy(path)) path.pop() 

Resultado:

 >>> get_keys(example_dict, 'value1') >>> result [['key1'], ['key4', 'key4a', 'key4ac']]