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

Question

当值可能在嵌套字典中存在不止一次时，我正在努力处理嵌套字典，并返回特定值的嵌套父键。 例如：

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

您会注意到“value1”在上面的字典中出现了两次，我想创建一个函数，该函数返回一个列表或一系列列表，用于标识不同的父键，在本例中为“key1”和（“key4”，“key4 a”，key4ac）。

这种类型的问题在这个站点的其他地方处理，当一个正在查找的值只出现一次，并且很容易被以下递归函数处理：

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

除非你只是在做一个搜索（或者你的内存非常有限，但是有足够的CPU时间来烧掉…），否则你需要建立一个反向查找字典，然后你就可以使用它了。

---

为了方便起见，我将分两步来做。首先，将嵌套字典转换为密钥路径字典：

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)

现在您不需要任何花哨的东西；只需对reverse_dict执行普通的dict查找：

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

---

如果您希望最后一个返回[]，而不是引发KeyError，那么可以使用defaultdict(list)，而不是普通的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']]