python - JSONオブジェクトを階層に並べ替える

Question

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が正しくないことです。folder1/ folder2 / folder3/はこれでは機能しません。再帰関数が必要です。この構造の変更も含める必要があります。フォルダを含むフォルダと、フォルダ/フォルダを含むファイルの任意の組み合わせにすることができます。

Answer 1

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'
                            }
                        ] 
                    }
                ]
            }
        ]
    }
]

Answer 2

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"}]'
'''

Answer 3

この場合の私の解決策は次のようなものです：

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]

Answer 4

ここにあるのは、parentキーで表されるノード間の接続を含むグラフ（おそらく単なるツリー）です。これは隣接リストとして知られています。

children他のノードのリストであるキーを介して他のノードへのリンクを持つツリー構造を作成したいとします。

隣接リストをツリーに変換するには、最初にIDでノードを取得する方法が必要です。したがって、最初のステップは、idでキー設定されたすべてのノードのdictを作成することです。

次に、リストをもう一度確認して、子供を親に追加する必要があります。

最後に、親のないノード（ルートノード）のリストを作成します。

再帰的アルゴリズムはまったく必要ないことに注意してください。

これらの手順のいくつかを組み合わせて、リストを何度も通過することを回避できます。以下のコード：

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