Сортировка объектов JSON в иерархию
Мне нужно отсортировать массив JSON в иерархию, здесь мой файл JSON, он никогда не упорядочен, а имеет следующую структуру:
{
"name":"Folder 2",
"id":"zRDg",
"parent":"OY00",
"type":"folder"
},
{
"name":"Folder 1",
"id":"OY00",
"type":"folder"
},
{
"name":"Folder 3",
"id":"ZDE1",
"type":"folder"
},
{
"name":"DX00025.jpg",
"id":"9Xdd",
"parent":"OY00",
"type":"jpeg"
}
В этот файл JSON структура выглядит следующим образом:
{
"name":"Folder 1",
"id":"OY00",
"type":"folder",
"children": [{
"name":"Folder 2",
"id":"zRDg",
"type":"folder"
},
{
"name":"DX00025.jpg",
"id":"9Xdd",
"type":"jpeg"
}]
},
{
"name":"Folder 3",
"id":"ZDE1",
"type":"folder"
}
Я не могу понять это, так как я новичок в Python, мой старт (неправильно):
for index,item in result:
if item['parent']:
for item2 in result:
if item2['id'] == item['parent']:
item['children'] = item2
brake
Это нормально, но проблема в том, что это неправильно Python, папка 1/ папка 2/ папка 3/ не будет работать для этого, мне нужна рекурсивная функция. Я должен также включить эту структуру изменений, это может быть папка с папкой и файлы с папкой / папками в любой комбинации.
4 ответа
Решение
myJson = [
{
"name":"Folder 2",
"id":"zRDg",
"parent":"OY00",
"type":"folder"
},
{
"name":"Folder 1",
"id":"OY00",
"type":"folder"
},
{
"name":"Folder 3",
"id":"ZDE1",
"type":"folder"
},
{
"name":"DX00025.jpg",
"id":"9Xdd",
"parent":"OY00",
"type":"jpeg"
}
]
#this creates a dictionary that maps id names to JSON items.
#ex. itemsKeyedById["9Xdd"] gives the jpg item with id "9Xdd"
itemsKeyedById = {i["id"]: i for i in myJson}
#iterate through each item in the `myJson` list.
for item in myJson:
#does the item have a parent?
if "parent" in item:
#get the parent item
parent = itemsKeyedById[item["parent"]]
#if the parent item doesn't have a "children" member,
#we must create one.
if "children" not in parent:
parent["children"] = []
#add the item to its parent's "children" list.
parent["children"].append(item)
#filter out any item that has a parent.
#They don't need to appear at the top level,
#since they will appear underneath another item elsewhere.
topLevelItems = [item for item in myJson if "parent" not in item]
print topLevelItems
Вывод (с добавленным мной отступом):
[
{
'name': 'Folder 1',
'id': 'OY00',
'type': 'folder',
'children': [
{
'name': 'Folder 2',
'id': 'zRDg',
'parent': 'OY00',
'type': 'folder'
},
{
'name': 'DX00025.jpg',
'id': '9Xdd',
'parent': 'OY00',
'type': 'jpeg'
}
]
},
{
'name': 'Folder 3',
'id': 'ZDE1',
'type': 'folder'
}
]
Он также работает с элементами, вложенными более чем в одну глубину. Пример ввода:
myJson = [
{
"name":"TopLevel folder",
"id":"0",
"type":"folder",
},
{
"name":"MidLevel folder",
"id":"1",
"type":"folder",
"parent":"0"
},
{
"name":"Bottom Level folder",
"id":"2",
"type":"folder",
"parent":"1"
},
{
"name":"Vacation Picture",
"id":"3",
"type":"jpg",
"parent":"2"
},
]
Выход:
[
{
'type': 'folder',
'name': 'TopLevel folder',
'id': '0',
'children': [
{
'type': 'folder',
'name': 'MidLevel folder',
'parent': '0',
'id': '1',
'children': [
{
'type': 'folder',
'name': 'Bottom Level folder',
'parent': '1',
'id': '2',
'children': [
{
'type': 'jpg',
'name': 'Vacation Picture',
'parent': '2',
'id': '3'
}
]
}
]
}
]
}
]
Как насчет использования чего-то вроде библиотеки Python networkx?
import json
#networkx is a library for working with networks and trees
import networkx as nx
#The json_graph routines print out JSONic representations of graphs and trees
#http://networkx.github.com/documentation/latest/reference/readwrite.json_graph.html
from networkx.readwrite import json_graph
dd='[{ "name":"Folder 2", "id":"zRDg", "parent":"OY00", "type":"folder"},{ "name":"Folder 1", "id":"OY00", "type":"folder"},{"name":"Folder 3", "id":"ZDE1", "type":"folder"},{ "name":"DX00025.jpg", "id":"9Xdd", "parent":"OY00", "type":"jpeg"}]'
d=json.loads(dd)
#A tree is a directed graph - create one with a dummy root
DG=nx.DiGraph()
DG.add_node('root')
#Construct the tree as a directed graph and annotate the nodes with attributes
#Edges go from parent to child
for e in d:
DG.add_node(e['id'],name=e['name'],type=e['type'])
#If there's a parent, use it...
if 'parent' in e: DG.add_edge(e['parent'],e['id'])
#else create a dummy parent from the dummy root
else: DG.add_edge('root',e['id'])
#Get the tree as JSON
data = json_graph.tree_data(DG,root='root')
#and dump the data from the dummy root's children down...
json.dumps(data['children'])
'''
'[{"children": [{"type": "folder", "name": "Folder 2", "id": "zRDg"}, {"type": "jpeg", "name": "DX00025.jpg", "id": "9Xdd"}], "type": "folder", "name": "Folder 1", "id": "OY00"}, {"type": "folder", "name": "Folder 3", "id": "ZDE1"}]'
'''
Здесь у вас есть график (вероятно, просто дерево) со связями между узлами, представленными parent ключ. Это известно как список смежности.
Вы хотите создать древовидную структуру со ссылками на другие узлы через children ключ, который является списком других узлов.
Чтобы преобразовать список смежности в дерево, сначала необходимо получить способ извлечения узла по его идентификатору, поэтому первым шагом является создание подсказки для каждого узла с ключом по идентификатору.
Затем вы должны снова просмотреть список и добавить детей к их родителям.
Наконец, составьте список узлов без родителей (корневых узлов).
Обратите внимание, что вам не нужен рекурсивный алгоритм вообще.
Мы можем объединить некоторые из этих шагов, чтобы избежать многократного просмотра списка. Код ниже:
def nest_list(L):
"""Modify list of associative dicts into a graph and return roots of graph
Association is via a 'parent' key indicating a corresponding 'id'.
Items in the list *will be modified*.
Children will be placed in a list for a 'children' key
Items without children will have no 'children' key
'parent' keys will be removed.
Returned list is the full list of items which are not children of
any other items.
"""
idx = {}
children = []
root = []
# first pass: index items by id
# if the item has no parents, put it in the 'root' list
# otherwise add it to the 'children' list which we will
# process in a second pass
for item in L:
idx[item['id']] = item
if 'parent' in item:
children.append(item)
else:
root.append(item)
# second pass: find the parents of our children
for child in children:
parent = idx[child['parent']]
del child['parent']
try:
# retrieve the list of children for this
# parent
childlist = parent['children']
except KeyError:
# this item has received no children so far
# so we need to make a 'children' key and list
# for it.
parent['children'] = childlist = []
# append this child to the parent's list of children
childlist.append(child)
#all done: return new root list
return root
Код в действии:
oldlist = [{
"name":"Folder 2",
"id":"zRDg",
"parent":"OY00",
"type":"folder"
},
{
"name":"Folder 1",
"id":"OY00",
"type":"folder"
},
{
"name":"Folder 3",
"id":"ZDE1",
"type":"folder"
},
{
"name":"DX00025.jpg",
"id":"9Xdd",
"parent":"OY00",
"type":"jpeg"
}]
expected = [{
"name":"Folder 1",
"id":"OY00",
"type":"folder",
"children": [{
"name":"Folder 2",
"id":"zRDg",
"type":"folder"
},
{
"name":"DX00025.jpg",
"id":"9Xdd",
"type":"jpeg"
}]
},
{
"name":"Folder 3",
"id":"ZDE1",
"type":"folder"
}]
from pprint import pprint
newlist = nest_list(oldlist)
pprint(newlist)
assert newlist == expected
Мое решение для этого случая что-то вроде этого:
data = INPUT_LIST
class Item:
def __init__(self, _id, name, type, parent):
self._id = _id
self.name = name
self.type = type
self.parent = parent
self.children = []
def get_dict(self):
return {
'id': self._id,
'name': self.name,
'type': self.type,
'children': [child.get_dict() for child in self.children]
}
lookup = dict((item['id'], Item(item['id'], item['name'], item['type'], item['parent'] if 'parent' in item else None)) for item in data)
root = []
for _id, item in lookup.items():
if not item.parent:
root.append(item)
else:
lookup[item.parent].children.append(item)
dict_result = [item.get_dict() for item in root]