Python - 在嵌套字典中查找特定值的父键 [英] Python--Finding Parent Keys for a specific value in a nested dictionary

问题描述

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

I am struggling to process a nested dictionary, and return the nested Parent Keys, for a specific Value, when the Value may exist more than once in the nested dictionary. For example:

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

您会注意到，'value1'在上述字典中出现两次，我想创建一个返回单个列表或一系列列表的函数，识别不同的父键，在这种情况下，这将是'key1'和（'key4'，'key4a'，key4ac）。

You will notice that 'value1' appears twice in the above dictionary, and I would like to create a function that returns either a single list, or a series of lists, that identify the different Parent Keys, which in this case would be 'key1' and ('key4', 'key4a', key4ac).

这种类型的问题被处理在这个网站的其他地方，当价值一个寻找只出现一次，并且被t很容易处理他遵循递归函数：

This type of problem was dealt with elsewhere on this site, when the Value one was looking for only appeared once, and was readily handled by the following recursive function:

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

如果您在字典上运行上述代码，我只能得到一个父键的答案。
任何帮助将不胜感激，
谢谢！

If you run the above code on the dictionary, I only get one answer for the parent keys. Any help would be much appreciated, Thanks!

推荐答案

除非你只是做一个搜索（或者你非常难于记忆，但要花费CPU时间刻录...），您将需要构建一个反向查找字典，然后才可以使用。

Unless you're just doing a single search (or you're incredibly constrained on memory but have CPU time to burn…), you'll want to build a reverse-lookup dictionary, and then you can just use that.

为了使这更容易，我将分两步进行。首先，将嵌套字典转换为密钥路径字典：

To make that easier, I'm going to do it in two steps. First, convert a nested dictionary to a key-path dictionary:

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））如果不明显这样做。

Print out list(keypaths(example_dict)) if it isn't obvious what this does.

现在，你如何创建一个反向字典？对于一对一映射，您可以这样做：

Now, how do you create a reverse dictionary? For a one-to-one-mapping, you can just do this:

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

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

But for a many-to-one mapping like yours, the reverse is one-to-many, so we need to map each value to a list of keys. So:

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

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

And now you don't need anything fancy; just do a normal dict lookup on reverse_dict:

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

---

如果您希望最后一个返回 [] 而不是提起 KeyError ，那么可以使用 defaultdict（list）而不是一个简单的 dict ，然后你不需要 setdefault 。

---

If you'd prefer the last one to return [] instead of raising a KeyError, you can use a defaultdict(list) instead of a plain dict, and then you don't need setdefault.

无论如何，构建此反向映射所用的时间是只需要比通过暴力进行单次搜索所花费的时间更长一点，所以如果你做了100次搜索，那么这个速度将会快一倍，而且还要简单一些。

At any rate, the time taken to construct this reverse mapping is only a little longer than the time taken to do a single search by brute force, so if you're doing 100 searches, it'll be nearly 100x faster this way, as well as simpler.

这篇关于Python - 在嵌套字典中查找特定值的父键的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！