表データをツリー構造のjsonに変換したい

Question

列A	列B	列C
A-1	B-1	C-1
A-1	B-1	C-2
A-1	B-2	C-3
A-1	B-2	C-4
A-2	B-3	C-5
A-2	B-3	C-6
A-2	B-4	C-7
A-2	B-4	C-8
A-1	B-5	C-9
A-2	B-2	C-10

このような配列を

[ 
  [ '列A', '列B', '列C' ],
  [ 'A-1', 'B-1', 'C-1' ],
  [ 'A-1', 'B-1', 'C-2' ],
  〜〜〜〜
]

以下のようなツリー構造に変換したい

[
  {
    "列A": "A-1",
    "list": [
      {
        "列B": "B-1",
        "list": [
          "C-1",
          "C-2"
        ]
      },
      {
        "列B": "B-2",
        "list": [
          "C-3",
          "C-4"
        ]
      },
      {
        "列B": "B-5",
        "list": [
          "C-9"
        ]
      }
    ]
  },
  {
    "列A": "A-2",
    "list": [
      {
        "列B": "B-3",
        "list": [
          "C-5",
          "C-6"
        ]
      },
      {
        "列B": "B-4",
        "list": [
          "C-7",
          "C-8"
        ]
      },
      {
        "列B": "B-2",
        "list": [
          "C-10"
        ]
      }
    ]
  }
]

map とfilterを多数ネストしできなくもないですが、行列が変更になっても対応できるアルゴリズムが知りたいです。

解決案

const tableToTreeObjArr = (tableData, childListKey) => {

  // ヘッダー取得
  const header = tableData[0]

  // 行単位の処理
  const addRowToTree = (treeArray, row, header) => {

    let list = treeArray

    for (let i = 0; i < row.length; ++ i) {

      // 最終列以外 子配列を格納する親オブジェクトを生成
      if (i < row.length - 1) {

        // ヘッダーから列名取得
        const key = header[i]

        // 親オブジェクトがまだ存在しない場合は生成
        let obj = list.find(col => {
          return col[key] === row[i]
        })
        if (!obj) {
          obj = { [key]: row[i], [childListKey]: [] }
          list.push(obj)
        }

        // list変数の参照先を子配列に変更
        list = obj[childListKey]

      // 最終列 子配列への格納のみ行う
      } else {
        list.push(row[i])
      } 
    }

    return treeArray
  }

  // ヘッダー以降の行を配列に畳み込み
  return tableData.slice(1).reduce((treeArray, row) => {
    return addRowToTree(treeArray, row, header)
  }, [])
}

Comments

[think49]

とりあえず、表の1行目に "list" があると破綻する構造です。

[Ecaroh]

ご確認いただきありがとうございます。
確かにキーが重複してしまいますね。。。
実用的にする為にこの点もハンドリングすることを後ほど検討してみます。

[think49]

Q1. アイデアは有りますが、知りたいのはコードではなく、アルゴリズムという事で良いのですね？

Q2. どのあたりまでご自身で考えられましたか。
あなたの考えの軌跡を質問文に追記すると、回答が寄せられやすくなると思います。

[Ecaroh]

>Q1. アイデアは有りますが、知りたいのはコードではなく、アルゴリズムという事で良いのですね？
はい。なぜ想定した結果を得ることができるのか、そのアルゴリズムを理解することが一番の目的です。

>Q2. どのあたりまでご自身で考えられましたか。
filterで1列目の重複を取り除き、1列目に属する行をmapで抽出し、また重複を取り除き、、、
とネストを繰り返し記述することで想定通りの結果を得ることはできたものの、行列の変更に耐えられる様に汎用化する上で、
ライブラリを探す？再帰的処理で検討する？関数型をもっと理解するべき？、、、と何から手をつけて良いか分からなくなり投稿させていただいた次第です。

[think49]

うーん…、目的の結果を得られたのであれば、そう難しい問題ではないように思えるのですが…。

配列を前から順番に検索して、予め用意した空のオブジェクトのプロパティに代入するだけですよね？
どこが難しく感じるのでしょうか。
(私はライブラリを使用しなくても実装できると思います)

Answer 1

こんにちは

いろいろなやり方がありそうですが、一例を回答します。以下の二次元配列 tableData から目的のJSONを得るコードを挙げます。

const tableData = [
  [ '列A', '列B', '列C' ],
  [ 'A-1', 'B-1', 'C-1' ],
  [ 'A-1', 'B-1', 'C-2' ],
  [ 'A-1', 'B-2', 'C-3' ],
  [ 'A-1', 'B-2', 'C-4' ],
  [ 'A-2', 'B-3', 'C-5' ],
  [ 'A-2', 'B-3', 'C-6' ],
  [ 'A-2', 'B-4', 'C-7' ],
  [ 'A-2', 'B-4', 'C-8' ],
  [ 'A-1', 'B-5', 'C-9' ],
  [ 'A-2', 'B-2', 'C-10' ]
];

上記の配列tableDataから、階層構造を復元したオブジェクトを作ります。その際に lodash の _.set を使います。

const treeObj = tableData.slice(1).reduce((obj, path) => _(obj).set(path, null).value(), {});

上記によって、treeObj に下記のようなオブジェクトが得られます。

{
  "A-1": {
    "B-1": {
      "C-1": null,
      "C-2": null
    },
    "B-2": {
      "C-3": null,
      "C-4": null
    },
    "B-5": {
      "C-9": null
    }
  },
  "A-2": {
    "B-3": {
      "C-5": null,
      "C-6": null
    },
    "B-4": {
      "C-7": null,
      "C-8": null
    },
    "B-2": {
      "C-10": null
    }
  }
}

このtreeObj から、目的の配列を得るための再帰関数 treeObjToArray を作成します。

const treeObjToArray = obj => {
  const entries = Object.entries(obj).sort(([k1], [k2]) => k1.substring(2) - k2.substring(2));
  return entries.map(([k, v]) => ({
      [`列${k[0]}`]: k,
      list: Object.values(v)[0] ?
        treeObjToArray(v) : Object.keys(v).sort((k1, k2) => k1.substring(2) - k2.substring(2))
    })
  );
}

上記のtreeObjToArray に treeObj を与えて、目的の配列 treeArray を得ます。

const treeArray = treeObjToArray(treeObj);

console.log(JSON.stringify(treeArray, null, 2));

上記によって、以下が出力されます。

[
  {
    "列A": "A-1",
    "list": [
      {
        "列B": "B-1",
        "list": [
          "C-1",
          "C-2"
        ]
      },
      {
        "列B": "B-2",
        "list": [
          "C-3",
          "C-4"
        ]
      },
      {
        "列B": "B-5",
        "list": [
          "C-9"
        ]
      }
    ]
  },
  {
    "列A": "A-2",
    "list": [
      {
        "列B": "B-2",
        "list": [
          "C-10"
        ]
      },
      {
        "列B": "B-3",
        "list": [
          "C-5",
          "C-6"
        ]
      },
      {
        "列B": "B-4",
        "list": [
          "C-7",
          "C-8"
        ]
      }
    ]
  }
]

• 動作確認用CodePen: https://codepen.io/jun68ykt/pen/KKVaGXj?editors=0012

以上参考になれば幸いです。

追記1

別案を検討する際の参考情報です。一次元のオブジェクト配列から、オブジェクト間の階層構造を復元した配列に変換するコードの例は

• stackoverflow Build tree array from flat array in javascript

にいくつか出ています。ご質問にある表データの配列を加工して、上記に投稿されているいずれかの回答コードをベースにした階層化コードを作成する手もあるかもしれません。

追記2

オブジェクトを経由しない別案を作成しました。こちらは、どの階層においても、元のテーブルでの出現順にリストされます。

const addRowToTree = (treeArray, row) => {
  let list = treeArray;
  for (let i=0; i < row.length; ++ i) {
    if (i < row.length-1) {    
      const key = `列${row[i][0]}`;
      let obj = list.find(e => e[key] === row[i]);  
      if (!obj) {
        obj = { [key]: row[i], list: [] };
        list.push(obj);
      }    
      list = obj.list;
    } else {
      list.push(row[i]); 
    } 
  }
  return treeArray;
};

const treeArray = tableData.slice(1).reduce((tree, row) => addRowToTree(tree, row), []);

console.log(JSON.stringify(treeArray, null, 2));

• 動作確認用CodePen: https://codepen.io/jun68ykt/pen/oNbBaKE?editors=0012

追記3

先に書いた、追記1 で、stackoverflow　の投稿 Build tree array from flat array in javascript を挙げましたが、これの回答の中のベストアンサー の function list_to_tree(list) を使えそうか、ちょっとスパイクしてみましたが、問題があり簡単にはできそうもなかったです。その説明を以下、記載します。

元のテーブルのデータ配列は

[
  [ '列A', '列B', '列C' ],
  [ 'A-1', 'B-1', 'C-1' ],
  [ 'A-1', 'B-1', 'C-2' ],
  [ 'A-1', 'B-2', 'C-3' ],
  [ 'A-1', 'B-2', 'C-4' ],
  [ 'A-2', 'B-3', 'C-5' ],
  [ 'A-2', 'B-3', 'C-6' ],
  [ 'A-2', 'B-4', 'C-7' ],
  [ 'A-2', 'B-4', 'C-8' ],
  [ 'A-1', 'B-5', 'C-9' ],
  [ 'A-2', 'B-2', 'C-10' ]
]

というものですが、これのデータ行の３行目 [ 'A-1', 'B-2', 'C-3' ] を、ツリー末端の子（葉）のほうから親のほうへ向かうパスとして読むと

• C-3 の親は B-2 で、B-2 の親は A-1

と読めるのですが、そうすると、最後の行の [ 'A-2', 'B-2', 'C-10' ] は

• C-10 の親は B-2 で、B-2 の親は A-2

となってしまい、B-2　には、二つの親、A-1　と A-2 があることになってしまいます。ですが、先のstackoverflow の投稿では、各ノードの親は、木構造の定義に沿って、（最大で）一個であるようなノードの一次元配列を木構造化するコードでした。これを踏まえて、それでもベストアンサー の function list_to_tree(list) を使おうとすると、id として A-1やB-2だったりの文字列はそのまま使えず、「A-1 が親のB-1 と、A-2が親のB-2とは、別物である」という考え方を採り入れて、それらに異なる id を設ける必要があり、これはけっこう煩雑な作業となりそうです。

追記4

上記の追記3で書いた、function list_to_tree(list) を使うための

「A-1 が親のB-1 と、A-2が親のB-2とは、別物である」という考え方を採り入れて、それらに異なる id

を実装したコード例を挙げておきます。以下になります。（※ list_to_tree(list) は、そのままコピペしてきたもので、手を加えていません）

• 動作確認用CodePen: https://codepen.io/jun68ykt/pen/zYrNQzv?editors=0012

具体的には、たとえば、[ 'A-2', 'B-2', 'C-10' ] の C-10 から、以下のようなノードオブジェクトを作成します。

{ id: 'A-2/B-2/C-10', parentId: 'A-2/B-2', label: 'C-10' }

また、トップレベルの A-2 からは、 parentId に文字列の "0" を入れた、以下のオブジェクトを作成します。

{ id: 'A-2', parentId: '0', label: 'A-2' }

上記のようなオブジェクトを要素とする一次元配列を、元のテーブルデータから作成すると、その配列を function list_to_tree(list) に渡すことができて、木構造化した配列を返してくれますので、それをさらに望ましい形にフォーマットして結果を得ています。

Comments

[jun68ykt]

@Ecarohさん
上記の回答では、目的の配列にする際に、"A-1" などの文字列の末尾にある番号の昇順にソートしているので、元のテーブルのデータ配列とは、一部、順番が変わる可能性があります。たとえば、A-2 のＢ列の順番は、元のテーブルでの出現順では B-3, B-4, B-2 の順ですが、上記の回答だと、 出力されるJSONでは、B-2, B-3, B-4　と昇順にソートされます。これだとご質問の要件としてよろしくないようでしたら、お知らせください。

[jun68ykt]

上記コメントの問題を解消した別案を、回答のほうに追記2として挙げておきました。

[Ecaroh]

ご丁寧なご回答ありがとうございます。
まずは取り急ぎ御礼申し上げます。

現在、いただいたご回答内容を順に読み解いておりますが、最初の復元したオブジェクト生成する箇所について、差し支えなければ追加で質問させて下さい。
lodashについてはまだまだ勉強不足ですが`_(args)`という書き出しを今回初めてお見受けしました。
`_(args)`を単体で実行してみると`LodashWrapper`というオブジェクトが返ってくることは確認したのですが、
[公式](https://lodash.com/docs/4.17.15)に記述はなく、ググっても読み解ける情報を見つけることはできませんでした。
[setについて公式](https://lodash.com/docs/#set)を確認した上でreduceの戻り値を
`_.set(obj, path, null)`
に変更したところ同一の値を得ることが確認できたのですが、
`_(obj).set(path, null).value()`
とは同義になりますでしょうか。

[jun68ykt]

@Ecarohさん
コメントありがとうございます。

> `_(args)`という書き出し

は、Lodashのメソッドを、いわゆるメソッドチェーンで書けるようにするための書き方です。以下が参考になります。

Lodashのチェーン記法について (@kurararara さん）
https://qiita.com/kurararara/items/fb470ea71e59cd0371d4

上記の投稿の最後にもリンクがありますが、公式ドキュメントでの説明は以下です。
https://lodash.com/docs/4.17.15#prototype-chain

> `_(obj).set(path, null).value()`
とは同義になりますでしょうか。

はい。同義です。いま見返してみると、_.set の後に何らかlodashのメソッドを続けて書くつもりだったので、_(obj)から始める書き方にしていたようですが、特に他のメソッドは不要でしたので、ご変更頂いた、

> `_.set(obj, path, null)`

のほうで問題ありません。引き続きよろしくお願い致します。

[Ecaroh]

>Lodashのチェーン記法について (@kurararara さん）
こちらとてもわかりやすい記事でした。ありがとうございます。
引き続きlodash自体の仕様理解に努めたいところです。

>「A-1 が親のB-1 と、A-2が親のB-2とは、別物である」という考え方を採り入れて、それらに異なる id を設ける必要があり、これはけっこう煩雑な作業となりそうです。
こちらは「A-1 が親のB-2 と、A-2が親のB-2とは、別物である」ということですよね。
まさにそのとおりでして、列Cから見て列Bだけでなく列Aと列Bの組み合わせを意識する必要があります。

引き続きいただいた回答内容の確認を進めます。

[jun68ykt]

@Ecarohさん
コメントありがとうございます。

> まさにそのとおりでして、列Cから見て列Bだけでなく列Aと列Bの組み合わせを意識する必要があります。

その趣旨で、回答に挙げた、stackoverflow の投稿にあったコードを使った例を、回答のほうに追記4として書きました。各ノードのidを

> 列Cから見て列Bだけでなく列Aと列Bの組み合わせを意識した

ものに設定して、stackoverflowの回答コードを利用するものになります。参考になれば幸いです。

[Ecaroh]

ご連絡が遅くなりまして申し訳ございません。
ソートの件について返信できておりませんでしたが、今回はテーブル情報を得る時点で想定する並びになっている前提なので考慮していませんでした。
追記の通り、いただいた案を参考に一旦は解決できましたのでベストアンサーとさせていただきました。
ありがとうございました。

[jun68ykt]

どういたしまして????
> いただいた案を参考に一旦は解決できました
とのことでよかったです????

Answer 2

構造欠陥

オブジェクトの構造に問題があります。

[
  {
    "列A": "A-1",
    "list": [
      {
        "列B": "B-1",
        "list": [
          "C-1",
          "C-2"
        ]
      },
// 以下略

このオブジェクトを使っている状況で、下記表を取り込んだ場合、

list	list2	list3
A1	B1	C1

"list" のプロパティ名が衝突します。

[{
  "list":"A1",  // 列名の "list"
  "list":[]     // 子データ郡の "list"
}]

要件定義

一つのオブジェクトに格納すべきデータは3つあります。

• name (列名)
• value (セル値)
• children (子のセルデータ集合)

この3つを「どこに保存するか」が鍵となります。

アイデア1: new Map

列名を外に記憶して、データを2つに絞り込めば、new Map が使えます。

table.header; // ["列A", "列B", "列C"]
[...table.body.get('A1').get('B1').values()];  // ["C1", "C2"]

アイデア2: DOMノード

DOMがまさにツリー構造のモデルですので、次のDOMノードをDOM APIで作る実装もあります。

<div data-key="列A" data-value="A1"><div data-key="列B" data-value="B1"><div data-key="列C" data-value="C1"></div></div></div>

Selectors APIを使えば、目的のノードを見つけるのは容易です。

アイデア3: ユーザ定義class

3種のデータを格納するclassを定義し、new Mao と同じ要領で検索します。

class CellData {
  constructor (name, value, children) {
    this.name = name;         // 列名
    this.value = value;       // セル値
    this.children = children; // 子のセルデータ郡(new Map)
  }
  find (value) {
    return this.children.get(value);
  }
}

rootCell.find('A1').name;     // "列A"
rootCell.find('A1').value;    // "A1"

rootCell.find('A1').find('B1').find('C1').value;                    // "C1"
rootCell.find('A1').children.get('B1').children.get('C1').value;    // "C1"

rootCell とは1列目の手前にある、全ての列データ集合を含む「仮想的な列」です。
(全てを含むルートを定義しておくと、データ管理上都合が良い為)

Re: Ecaroh さん

Comments

[Ecaroh]

ご返答が遅くなりまして申し訳ございません。
追記の通り一旦解決とはしましたが、「そもそもjsonにすることが有用か？」という点も引き続き検討したいと思います。
ご提案いただいた中でも特にclassを定義する方法に興味を持ちました。
classのプロパティを複数持てば1セル内に複数情報を格納するといったより複雑なケースにも対応できるのではないかと考えました。
まずは本件同様に配列から変換するアルゴリズムを考えてみるところから始めてみます。
ご回答ありがとうございました。

Answer 3

冗長に

var a=[
  ['A-1','B-1','C-1'],
  ['A-1','B-1','C-2'],
  ['A-1','B-2','C-3'],
  ['A-1','B-2','C-4'],
  ['A-2','B-3','C-5'],
  ['A-2','B-3','C-6'],
  ['A-2','B-4','C-7'],
  ['A-2','B-4','C-8'],
  ['A-1','B-5','C-9'],
  ['A-2','B-2','C-10'],
  ];
var b={};
a.forEach(x=>{
  if(typeof b[x[0]]=="undefined"){
    b[x[0]]={};
  }
  if(typeof b[x[0]][x[1]]=="undefined"){
    b[x[0]][x[1]]=[];
  }
  b[x[0]][x[1]].push(x[2]);
});
console.log(b);
var c=Object.entries(b).map(x=>{
  return {"列A":x[0],list:Object.entries(x[1]).map(y=>{
    return {"列B":y[0],list:y[1]};
  })
  };
});
console.log(c);

Comments

[Ecaroh]

ご回答ありがとうございます。
現在、いただいたご回答内容を確認中ですが、まずは取り急ぎ御礼申し上げます。