Javascript 如何将此数据编码为 JSON 中的父/子结构

how to encode this data to parent / children structure in JSON

提问by johowie

I am working with d3.js to visualise families of animals (organisms) (up to 4000 at a time) as a tree graph, though the data source could just as well be a directory listing, or list of namespaced objects. my data looks like:

我正在使用 d3.js 将动物家族（有机体）（一次最多 4000 个）可视化为树形图，尽管数据源也可以是目录列表或命名空间对象列表。我的数据看起来像：

json = {
    organisms:[
        {name: 'Hemiptera.Miridae.Kanakamiris'},
        {name: 'Hemiptera.Miridae.Neophloeobia.incisa'},
        {name: 'Lepidoptera.Nymphalidae.Ephinephile.rawnsleyi'},
        ... etc ...
    ]
}

my question is: I am trying to find the best way to convert the above data to the hierarchical parent / children data structure as is used by a number of the d3 visualisations such as treemap(for data example see flare.jsonin the d3/examples/data/ directory). Here is an example of the desired data structure:

我的问题是：我试图找到将上述数据转换为分层父/子数据结构的最佳方法，正如许多 d3 可视化所使用的那样，例如树状图（例如，数据请参见d3/示例/数据/目录）。以下是所需数​​据结构的示例：

{"name": "ROOT",
 "children": [
        {"name": "Hemiptera",
         "children": [
             {"name": "Miridae",
              "children": [
                  {"name": "Kanakamiris", "children":[]},
                  {"name": "Neophloeobia",
                   "children": [
                       {"name": "incisa", "children":[] }
                   ]}
              ]}
         ]},
        {"name": "Lepidoptera",
         "children": [
             {"name": "Nymphalidae",
              "children": [
                  {"name": "Ephinephile",
                   "children": [
                       {"name": "rawnsleyi", "children":[] }
                   ]}
              ]}
         ]}
    ]}
}

EDIT: enclosed all the original desired data structure inside a ROOTnode, so as to conform with the structure of the d3 examples, which have only one master parent node.

编辑：将所有原始所需的数据结构包含在一个ROOT节点内，以符合 d3 示例的结构，该示例只有一个主父节点。

I am looking to understand a general design pattern, and as a bonus I would love to see some solutions in either javascript, php, (or even python). javascript is my preference. In regards to php: the data I am actually using comes from a call to a database by a php script that encodes the results as json. database results in the php script is an ordered array (see below) if that is any use for php based answers.

我希望了解一般的设计模式，作为奖励，我很想在 javascript、php（甚至 python）中看到一些解决方案。javascript 是我的偏好。关于 php：我实际使用的数据来自 php 脚本对数据库的调用，该脚本将结果编码为 json。php 脚本中的数据库结果是一个有序数组（见下文），如果这对基于 php 的答案有任何用处。

Array
(
    [0] => Array
        (
            ['Rank_Order'] => 'Hemiptera'
            ['Rank_Family'] => 'Miridae'
            ['Rank_Genus'] => 'Kanakamiris'
            ['Rank_Species'] => ''
        ) ........

where: 'Rank_Order'isParentOf 'Rank_Family'isParentOf 'Rank_Genus'isParentOf 'Rank_Species'

其中： 'Rank_Order'isParentOf 'Rank_Family'isParentOf 'Rank_Genus'isParentOf'Rank_Species'

I asked a similar question focussed on a php solution here, but the only answer is not working on my server, and I dont quite understand what is going on, so I want to ask this question from a design pattern perspective, and to include reference to my actual use which is in javascript and d3.js.

我在这里问了一个针对 php 解决方案的类似问题，但唯一的答案是在我的服务器上不起作用，我不太明白发生了什么，所以我想从设计模式的角度提出这个问题，并包括参考我在 javascript 和 d3.js 中的实际使用。

采纳答案by RobG

The following is specific to the structure you've provided, it could be made more generic fairly easily. I'm sure the addChildfunction can be simplified. Hopefully the comments are helpful.

以下特定于您提供的结构，它可以很容易地变得更通用。我确信可以简化addChild函数。希望评论有帮助。

function toHeirarchy(obj) {

  // Get the organisms array
  var orgName, orgNames = obj.organisms;

  // Make root object
  var root = {name:'ROOT', children:[]};

  // For each organism, get the name parts
  for (var i=0, iLen=orgNames.length; i<iLen; i++) {
    orgName = orgNames[i].name.split('.');

    // Start from root.children
    children = root.children;

    // For each part of name, get child if already have it
    // or add new object and child if not
    for (var j=0, jLen=orgName.length; j<jLen; j++) {
      children = addChild(children, orgName[j]);      
    }
  }
  return root;

  // Helper function, iterates over children looking for 
  // name. If found, returns its child array, otherwise adds a new
  // child object and child array and returns it.
  function addChild(children, name) {

    // Look for name in children
    for (var i=0, iLen=children.length; i<iLen; i++) {

      // If find name, return its child array
      if (children[i].name == name) {
        return children[i].children;        
      }
    }
    // If didn't find name, add a new object and 
    // return its child array
    children.push({'name': name, 'children':[]});
    return children[children.length - 1].children;
  }
}

回答by nnnnnn

Given your starting input I believe something like the following code will produce your desired output. I don't imagine this is the prettiest way to do it, but it's what came to mind at the time.

鉴于您的起始输入，我相信类似以下代码的内容将产生您想要的输出。我不认为这是最漂亮的方法，但这是当时想到的。

It seemed easiest to pre-process the data to first split up the initial array of strings into an array of arrays like this:

对数据进行预处理以首先将初始字符串数组拆分为这样的数组数组似乎是最简单的：

[
   ["Hemiptera","Miridae","Kanakamiris" ],
   ["Hemiptera","Miridae","Neophloeobia","incisa" ],
   //etc
]

...and then process that to get a working object in a form something like this:

...然后处理它以得到一个类似这样的形式的工作对象：

  working = {
       Hemiptera : {
           Miridae : {
              Kanakamiris : {},
              Neophloeobia : {
                  incisa : {}
              }
           }
       },
       Lepidoptera : {
           Nymphalidae : {
              Ephinephile : {
                  rawnsleyi : {}
              }
           }
       }
    }

...because working with objects rather than arrays makes it easier to test whether child items already exist. Having created the above structure I then process it one last time to get your final desired output. So:

...因为使用对象而不是数组可以更容易地测试子项是否已经存在。创建上述结构后，我最后一次处理它以获得最终所需的输出。所以：

// start by remapping the data to an array of arrays
var organisms = data.organisms.map(function(v) {
        return v.name.split(".");
    });

// this function recursively processes the above array of arrays
// to create an object whose properties are also objects
function addToHeirarchy(val, level, heirarchy) {
    if (val[level]) {
        if (!heirarchy.hasOwnProperty(val[level]))
            heirarchy[val[level]] = {};
        addToHeirarchy(val, level + 1, heirarchy[val[level]]);
    }
}
var working = {};    
for (var i = 0; i < organisms.length; i++)
    addToHeirarchy(organisms[i], 0, working);

// this function recursively processes the object created above
// to create the desired final structure
function remapHeirarchy(item) {
    var children = [];
    for (var k in item) {
        children.push({
            "name" : k,
            "children" : remapHeirarchy(item[k])
        });
    }
    return children;
}

var heirarchy = {
    "name" : "ROOT",
    "children" : remapHeirarchy(working)
};

Demo: http://jsfiddle.net/a669F/1/

演示：http: //jsfiddle.net/a669F/1/

回答by johowie

An alternative answer to my own question....In the past day I have learn't a great deal more about d3.js and in relation to this question d3.nest()with .key() and .entries() is my friend (all d3 functions). This answer involves changing the initial data, so it may not qualify as a good answer to the specific question i asked. However if someone has a similar question and can change things on the server then this is a pretty simple solution:

我自己的问题的另一种答案....在过去的一天中，我对 d3.js 的了解不多，而与此问题相关的d3.nest()与 .key() 和 .entries() 是我的朋友（所有 d3 功能）。这个答案涉及更改初始数据，因此它可能不符合我提出的特定问题的好答案。但是，如果有人有类似的问题并且可以更改服务器上的内容，那么这是一个非常简单的解决方案：

return the data from the database in this format:

以这种格式从数据库返回数据：

json = {'Organisms': [
    { 'Rank_Order': 'Hemiptera',
      'Rank_Family': 'Miridae',
      'Rank_Genus': 'Kanakamiris',
      'Rank_Species': '' },
    {}, ...
]}

Then using d3.nest()

然后使用d3.nest()

organismNest = d3.nest()
    .key(function(d){return d.Rank_Order;})
    .key(function(d){return d.Rank_Family;})
    .key(function(d){return d.Rank_Genus;})
    .key(function(d){return d.Rank_Species;})
    .entries(json.Organism);

this returns:

这将返回：

{
key: "Hemiptera"
  values: [
    {
      key: "Cicadidae"
      values: [
        {
          key: "Pauropsalta "
          values: [
            {
              key: "siccanus"
              values: [
                       Rank_Family: "Cicadidae"
                       Rank_Genus: "Pauropsalta "
                       Rank_Order: "Hemiptera"
                       Rank_Species: "siccanus"
                       AnotherOriginalDataKey: "original data value"

etc etc, nested and lovely

This returns something very much similar to they array that I described as my desired format above in the question, with a few differences. In particular, There is no all enclosing ROOT element and also whereas they keys I originally wanted were "name" and "children" .nest() returns keys as "key" and "values" respectively. These alternatives keys are easy enough to use in d3.js by just defining appropriate data accessor functions (basic d3 concept) ... but that is getting beyond the original scope of the question ... hope that helps someone too

这将返回与我在上面的问题中描述为我想要的格式的数组非常相似的东西，但有一些不同。特别是，没有所有封闭的 ROOT 元素，而且我最初想要的键是“name”和“children”。nest() 分别返回键作为“键”和“值”。这些替代键很容易在 d3.js 中使用，只需定义适当的数据访问器函数（基本 d3 概念）......但这超出了问题的原始范围......希望也能帮助别人