python - 从python中的嵌套字典创建层次树

Question

我有一个很大的 RDF 文件，其中包含大约 600,000 条维基数据分类记录。从这个文件中，我只对 subclassOf 关系(谓词)感兴趣，因此，我忽略所有其他只保留“subclassOf”语句的语句。语句是这样的:a 是一个子类 b,b 是一个子类 c就像 c 是 b 的父级，b 是 a 的父级。任何 parent 都可以有很多 child 。我想使用此分类法构建分层树。 我检查了这个线程，它几乎解决了我的问题。 Recursively creating a tree hierarchy without using class/object但是，有了这个，我在字典中得到了树，我想将其转换为树数据结构。以下是我尝试过的:

data = [['a','x'], ['b','x'], ['c','x'], ['x','y'], ['t','y'], ['y','p'], ['p','q']]

roots = set()
mapping = {}
for child,parent in data:        
    childitem = mapping.get(child,None)
    if childitem is None:
        childitem =  {}
        mapping[child] = childitem
    else:
        roots.discard(child)
    parentitem = mapping.get(parent,None)
    if parentitem is None:
        mapping[parent] = {child:childitem}
        roots.add(parent)
    else:
        parentitem[child] = childitem

for root in roots:
    print(mapping[root])

tree = { id : mapping[id] for id in roots }
print(tree)

树的输出如下所示:

{'q': {'p': {'y': {'t': {}, 'x': {'c': {}, 'b': {}, 'a': {}}}}}}

我想把这本字典转换成树。所以例如当我说 print(mapping['y']) 时，它应该给我 Node y 即

q
├── p
    └── y

目前，如果我说 mapping['y']，它会给我以 y 为根的子树。我认为对此有一些简单的解决方案，但我无法理解。我也找到了这个链接https://gist.github.com/hrldcpr/2012250将字典转换为树，但不确定如何在我的案例中使用它。或者，如果有人知道直接从我上面给出的 RDF 数据构建树，那么将非常欢迎。可能 python 的 anytree API 会解决我的问题。

Answer 1

如果您不介意额外的 O(N) 空间，您可以保留一个 parents 字典，为每个关键子节点存储值 parent。并将其填充到主 for 循环中。

现在找到所有祖先非常容易。递归查找您父级的所有祖先并将当前节点附加到该结果。

data = [['a','x'], ['b','x'], ['c','x'], ['x','y'], ['t','y'], ['y','p'], ['p','q']]
parents = {} #to store parents
roots = set()
mapping = {}
for child,parent in data:
    parents[child] = parent #populate parents
    childitem = mapping.get(child,None)
    ................................

def ancestors(node): #the ancestor-finding function
    if not node: return []
    return ancestors(parents.get(node))+[node]

def first_k_ancestor(node,k=5):
    ances = ancestors(node)
    ances.reverse()
    return ances[:k]


print(ancestors('a'))

打印:

['q', 'p', 'y']