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

Question

我有一个很大的 RDF 文件，其中包含大约 600,000 条维基数据分类记录。从这个文件中，我只对 subclassOf 关系（谓词）感兴趣，因此，我忽略所有其他只保留 "subclassOf" 语句的语句。语句是这样的： a is a subclassOf b, b is a subclassOf c 就像 c 是 b 的 parent 而 b 是 a 的 parent。并且任何 parent 可以有许多 children。我想使用此分类法构建分层树。我检查了这个线程，它几乎解决了我的问题。但是，有了这个，我在字典中得到了树，我想将其转换为树 data-structure。以下是我尝试过的：

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']) 时，它应该给我节点 y 即

q
├── p
    └── y

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

Answer 1

如果您不介意额外的 O(N) space，您可以保留一个 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']

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

Creating hierarchical tree from nested dictionary in python

python

tree

dictionary

rdf

taxonomy