Построение JSon структуры дерева из идентификаторов

Question

У меня есть файл с данными, который выглядит так:

ID attribute 
1 'text' 
101 'text' 
1011 'text' 
10111 'text' 
1011101 'text' 
1011102 'text' 
1011103 'text' 
1011104 'text' 
1011130 'text' 

Моя цель состоит в том, чтобы построить древовидную структуру JSon из этих данных:

{ 
    [ 
    ID : 1, 
    attribute : 'text', 
    children : [ 
     ID: 101, 
     attribute : 'text', 
     children : [ 
      ... 
    ID : 2, 
     ... 
    ] 
} 

В питона, я построил список dictionnaries так:

[ {'id': ID, 'attr' : text}, {...} ] 

Я думаю, я мог бы использовать тот факт, что лист ID содержать своих родителей id, но я не вижу способ построить структуру, которую хочу.

Я буду признателен за любую помощь, в псевдокоде или любом другом языке программирования.

Answer 1

Решение от thg435 работал с небольшими изменениями:

# open & read raw file 
f=open(args[0], 'r') 
text = f.read() 

# 
text = map(lambda s: s.split(" ", 1), text.strip().replace("'","").splitlines()) 
tree = [{'prefix': '', 'children':[]}] 
stack = [tree[0]] 

for id, attr in text: 
    while not id.startswith(stack[-1]['prefix']): 
     stack.pop() 
    node = {'prefix': id, 'attr': attr, 'children': []} 
    stack[-1]['children'].append(node) 
    stack.append(node) 

pprint.pprint(tree) 

print json.dumps(tree) 
f=open(args[1], 'w') 
f.write(json.dumps(tree, sort_keys=True, indent=1)) 

Спасибо!

Answer 2

я не совсем понимаю вашу идентификационную систему нумерации, так что вот код для простого префикса дерева:

ls = """ 
1 'text' 
101 'text' 
1011 'text' 
10111 'text' 
1011101 'text' 
2 two 
2111 'text' 
21114 'text' 
25 'text' 
2567 'text' 
""" 
ls = map(str.split, ls.strip().splitlines()) 


tree = [{'prefix': '', 'children':[]}] 
stack = [tree[0]] 

for id, attr in ls: 
    while not id.startswith(stack[-1]['prefix']): 
     stack.pop() 
    node = {'prefix': id, 'attr': attr, 'children': []} 
    stack[-1]['children'].append(node) 
    stack.append(node) 

import pprint 
pprint.pprint(tree)