将任意长度字典项扁平化为Python中的路径列表

Question

我看过不少关于在Python中递归扁平化字典的帖子，但没有一个（除了一个）能满足我的需求。首先，给大家举个例子，说明我想要实现的目标：

这是一个包含混合条目的示例字典：（字典的键和值总是会有不同的类型）

{'a': [{'b': {'c': 'd', 'e': 'f', 'g': 'h',
              'i': {'j': {'k': ['l'], 'm': 'n'}},
              'o': {'p': {'q': ['r', 's' ], 't': 'u'}}
              }
       }]
}

我想要的输出结果是：

{'a/b/c/d',
 'a/b/e/f',
 'a/b/g/h',
 'a/b/i/j/k/l',
 'a/b/i/j/m/n',
 'a/b/o/p/q/r',
 'a/b/o/p/q/s',
 'a/b/o/p/t/u'}

这个函数理论上也应该能在列表上工作。

简单说一下我在做什么，我正在尝试搜索一个Mac的plist文件，之前通过键或值进行搜索的效果都不太好。为了弥补这个问题，我想尝试一种不同的方法。把字典转换成一个“路径”的列表，然后只搜索这些路径。

我自己尝试过（部分成功），然后找到了一个更好的解决方案，如下所示：

def flatten(structure, key="", path="", flattened=None):
    if flattened is None:
        flattened = {}
    if type(structure) not in(dict, list):
        flattened[((path + "/") if path else "") + key] = structure
    elif isinstance(structure, list):
        for i, item in enumerate(structure):
            flatten(item, "", "/".join(filter(None,[path,key])), flattened)
    else:
        for new_key, value in structure.items():
            flatten(value, new_key, "/".join(filter(None,[path,key])), flattened)
    return flattened

这个方法效果不错，但也有一些不太理想的地方。首先，输出结果如下：

{'a/b/c'     : 'd',
 'a/b/e'     : 'f',
 'a/b/g'     : 'h',
 'a/b/i/j/k/': 'l',
 'a/b/i/j/m' : 'n',
 'a/b/o/p/q/': 's',
 'a/b/o/p/t' : 'u'}

这返回的是一个键值对的字典。我更希望得到的是一个字符串路径的列表。其次，更重要的是，你会注意到，脚本在处理值为列表的情况时，只保留了列表中的最后一个项。

'a/b/o/p/q/': 's' # there should be another entry with 'r' as the value.

我花了不少时间在调整输出上，试图完全理解这个问题，但都没有成功。可能是我对Python的理解还不够，但我想要的输出应该是可以实现的。

我尽量不问问题，除非我真的没有其他选择，而现在我就是这样。请不要标记为重复问题，因为其他问题并没有完全解决我想要实现的目标。

感谢你的时间和帮助/指导。

Answer 1

这是我在Python 3.3及以上版本中会这样做：

def flatten(exp):
    def sub(exp, res):
        if type(exp) == dict:
            for k, v in exp.items():
                yield from sub(v, res+[k])
        elif type(exp) == list:
            for v in exp:
                yield from sub(v, res)
        else:
            yield "/".join(res+[exp])
    yield from sub(exp, [])

测试：

l={'a': [{'b': {'c': 'd', 'e': 'f', 'g': 'h',
              'i': {'j': {'k': ['l'], 'm': 'n'}},
              'o': {'p': {'q': ['r', 's' ], 't': 'u'}}
              }
       }]
}

for i in sorted(flatten(l)):
    print(i)

结果是

a/b/c/d
a/b/e/f
a/b/g/h
a/b/i/j/k/l
a/b/i/j/m/n
a/b/o/p/q/r
a/b/o/p/q/s
a/b/o/p/t/u

编辑 转换到Python 2是非常简单的：

def flatten(exp):
    def sub(exp, res):
        if type(exp) == dict:
            for k, v in exp.items():
                for r in sub(v, res+[k]):
                    yield r
        elif type(exp) == list:
            for v in exp:
                for r in sub(v, res):
                    yield r
        else:
            yield "/".join(res+[exp])
    for r in sub(exp, []):
        yield r

然后

>>> for i in sorted(flatten(l)):
...     print i
...
a/b/c/d
a/b/e/f
a/b/g/h
a/b/i/j/k/l
a/b/i/j/m/n
a/b/o/p/q/r
a/b/o/p/q/s
a/b/o/p/t/u

Answer 2

Python 2.7:

def flatten(structure):
    if isinstance(structure, basestring):
        return [structure]
    ret = []
    if isinstance(structure, list):
        for v in structure:
            ret.extend(flatten(v))
    elif isinstance(structure, dict):
        for k, v in structure.items():
            ret.extend(k + '/' + f for f in flatten(v))
    return ret

print sorted(flatten(structure))

输出结果:

['a/b/c/d', 'a/b/e/f', 'a/b/g/h', 'a/b/i/j/k/l', 'a/b/i/j/m/n', 'a/b/o/p/q/r', 'a/b/o/p/q/s', 'a/b/o/p/t/u']

或者，如果你不在乎顺序的话，你可以直接用 print flatten(structure) 来打印。