Skip to main content
 首页 » 编程设计

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

2025年01月19日12bhlsheji

我有一个很大的 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 会解决我的问题。

请您参考如下方法:

如果您不介意额外的 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']