Python - 在嵌套字典中查找特定值的父键

Question

我很难处理嵌套字典,并且当嵌套字典中的Value可能存在多次时,返回嵌套的父键,用于特定的值.例如:

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

你会注意到'value1'在上面的字典中出现了两次,我想创建一个函数,它返回一个列表或一系列列表,用于标识不同的父键,在本例中为'key1 '和''key4','key4a',key4ac).

这个类型的问题在本网站的其他地方得到了处理,当Value one只寻找出现一次时,可以通过以下递归函数轻松处理:

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').

如果你在字典上运行上面的代码,我只得到一个父键的答案.任何帮助将不胜感激,谢谢!

Answer 1

除非你只是进行一次搜索(或者你的内存受到了极大的限制,但有时间需要刻录......),你需要构建一个反向查找字典,然后就可以使用它了.

为了使这更容易,我将分两步完成.首先,将嵌套字典转换为键路径字典:

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

list(keypaths(example_dict))如果不明显这是什么,请打印出来.

现在,您如何创建反向字典？对于一对一映射,您可以这样做:

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

但是对于像你这样的多对一映射,反之亦然是一对多,所以我们需要将每个值映射到一个键列表.所以:

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

现在你不需要任何花哨的东西; 只需执行正常的dict查找reverse_dict:

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

如果你更喜欢最后一个返回[]而不是提高a KeyError,你可以使用a defaultdict(list)而不是plain dict,然后你不需要setdefault.

无论如何,构建这种反向映射所花费的时间只比通过强力进行单次搜索所花费的时间稍长一些,所以如果你进行100次搜索,那么这种搜索速度将快近100倍,更简单.

Answer 2

这是一个解决方案:

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

结果:

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