csvからツリー構造を生成

Question

私は今この問題に頭を悩ましています。私は基本的にCSVデータのセットからツリー階層を生成しようとしています。 CSVデータは必ずしも注文する必要はありません。これは次のようなものです：

Header: Record1,Record2,Value1,Value2 
Row: A,XX,22,33 
Row: A,XX,777,888 
Row: A,YY,33,11 
Row: B,XX,12,0 
Row: A,YY,13,23 
Row: B,YY,44,98 

できるだけ柔軟にグルーピングを実行しようとしています。だろう

Record1 
    Record2 
     Value1 Value2 

：

A 
    XX 
     22,33 
     777,888 
    YY 
     33,11 
     13,23 
B 
    XX 
     12,0 
    YY 
     44,98 

私が保管しています私たちは以下のような出力を得るように、グループ化のための最も簡単なものはvalue1と値2を持つレコード1とRECORD2のためにそれを行うには希望RECORD2下に保存しますリスト内の私のグループ設定 - 現在の私の考えを妨げているかどうかわかりません。このリストは、例えばグループの階層が含まれています

Record1 (SchemaGroup) 
    .column = Record1 
    .columns = null 
    .childGroups = 
     Record2 (SchemaGroup) 
      .column = Record1 
      .columns = Value1 (CSVColumnInformation), Value2 (CSVColumnInformation) 
      .childGroups = null 

次のように、このためのコードは次のようになります。

private class SchemaGroup { 
    private SchemaGroupType type = SchemaGroupType.StaticText; // default to text 
    private String text; 
    private CSVColumnInformation column = null; 
    private List<SchemaGroup> childGroups = new ArrayList<SchemaGroup>(); 
    private List<CSVColumnInformation> columns = new ArrayList<CSVColumnInformation>(); 
} 


private enum SchemaGroupType { 
    /** Allow fixed text groups to be added */ 
    StaticText, 
    /** Related to a column with common value */ 
    ColumnGroup 
} 

私は基本的な構造を考えるようにしようとし、このためのアルゴリズムを作成stugglingています使用する。現時点では私は私自身のラッパークラスを使用して、下にCSVトップを解析しています：

CSVParser csv = new CSVParser(content); 
String[] line; 
while((line = csv.readLine()) != null) { 
    ... 
} 

私はちょうど私のコーディングの脳をキックスタートしようとしています。

どのような考えですか？この問題が提起される方法に基づいて

が

Answer 1

、私は次の操作を行います：

1. 最終的なデータ構造は ツリーを含むようにどのように見えるかを定義します。
2. 元のテキストの各行の表現を定義する （柔軟性のためにおそらくリンクされたリスト）
3. 表現された行を取得し、それをツリーデータ構造に挿入するメソッドを記述します。存在しないブランチごとに作成します。既存のブランチごとに、「行」リンクリスト構造をステップ実行するときにそれをトラバースします。
4. 空のツリーから始めます。
5. あなたの行項目構造にファイルの各行を読み込み、ステップ3

で定義されたメソッドがその助けを呼んでい？

Answer 2

基本的な考え方は難しいことではありません。グループの最初のレコードによって、2番目のレコードで、などあなたがこのような何かを得るまで：

(A,XX,22,33) 
(A,XX,777,888) 
------------------------- 
(A,YY,33,11) 
(A,YY,13,23) 
============= 
(B,XX,12,0) 
------------------------- 
(B,YY,44,98) 

をして、木を構築するために逆方向に働きます。

ただし、再帰的なコンポーネントがあるため、この問題について何らかの理由で判断するのが難しくなり、段階的に表示されるため、実際に擬似コードを書く方が簡単です。

あなたのcsvの各行はタプルのように表現されていると仮定します。それぞれのタプルには、あなたの質問で使用するのと同じ用語を使用して、「レコード」と「値」があります。「レコード」は、階層構造に入れなければならないものです。 "値"は木の葉になります。これらの特定の意味でこれらの用語を使用するときは引用を使用します。

また、すべての「レコード」がすべての「値」の前にあるとします。さらに騒ぎがなければ

、コード：

// builds tree and returns a list of root nodes 
// list_of_tuples: a list of tuples read from your csv 
// curr_position: used to keep track of recursive calls 
// number_of_records: assuming each csv row has n records and then m values, number_of_records equals n 
function build_tree(list_of_tuples, curr_position, number_of_records) { 
    // check if we have already reached the "values" (which shouldn't get converted into trees) 
    if (curr_position == number_of_records) { 
     return list of nodes, each containing a "value" (i.e. everything from position number_of_records on) 
    } 

    grouped = group tuples in list_of_tuples that have the same value in position curr_position, and store these groups indexed by such common value 
    unique_values = get unique values in curr_position 

    list_of_nodes = empty list 

    // create the nodes and (recursively) their children 
    for each val in unique_values { 
     the_node = create tree node containing val 
     the_children = build_tree(grouped[val], curr_position+1, number_of_records) 
     the_node.set_children(the_children) 

     list_of_nodes.append(the_node) 
    } 

    return list_of_nodes 
} 

// in your example, this returns a node with "A" and a node with "B" 
// third parameter is 2 because you have 2 "records" 
build_tree(list_parsed_from_csv, 0, 2) 

今あなたが使用する特定のデータ構造を考える必要があるだろうが、あなたは、アルゴリズムを理解すれば、うまくいけば、これはあなたのように（あまりにも難しいことではありません言い換えれば、データ構造を早期に決めることがあなたの考えを妨げているかもしれないと思う）。

Answer 3

あなたはRecord秒のちょうど2つのレベルがあります知っている場合、私はあなたが新しい行を読んだとき、あなたはすでにRecord1のためにその値かどうかを確認するために、外側マップに見

Map<string, Map<string, List<Values>>> 

のようなものを使用します存在しない場合は、新しい空の内部を作成します。Map

次に、Record2の値が存在するかどうかを内部マップで確認します。そうでない場合は、新しいListを作成します。

次に、値を読み取ってリストに追加します。

Answer 4

ここでは、google-guava collectionsを使用して簡素化されたjunit（アサーションはありません）の形式の基本的な作業ソリューションです。コードは自明で、ファイルioの代わりにcsvライブラリを使用してcsvを読み込みます。これはあなたに基本的な考えを与えるはずです。

import java.io.File; 
import java.io.IOException; 
import java.util.Collection; 
import java.util.Collections; 
import java.util.List; 
import java.util.Set; 

import org.junit.Test; 

import com.google.common.base.Charsets; 
import com.google.common.base.Splitter; 
import com.google.common.collect.ArrayListMultimap; 
import com.google.common.collect.Iterables; 
import com.google.common.collect.Multimap; 
import com.google.common.collect.Sets; 
import com.google.common.io.Files; 

public class MyTest 
{ 
    @Test 
    public void test1() 
    { 
     List<String> rows = getAllDataRows(); 

     Multimap<Records, Values> table = indexData(rows); 

     printTree(table); 

    } 

    private void printTree(Multimap<Records, Values> table) 
    { 
     Set<String> alreadyPrintedRecord1s = Sets.newHashSet(); 

     for (Records r : table.keySet()) 
     { 
      if (!alreadyPrintedRecord1s.contains(r.r1)) 
      { 
       System.err.println(r.r1); 
       alreadyPrintedRecord1s.add(r.r1); 
      } 

      System.err.println("\t" + r.r2); 

      Collection<Values> allValues = table.get(r); 

      for (Values v : allValues) 
      { 
       System.err.println("\t\t" + v.v1 + " , " + v.v2); 
      } 
     } 
    } 

    private Multimap<Records, Values> indexData(List<String> lines) 
    { 
     Multimap<Records, Values> table = ArrayListMultimap.create(); 

     for (String row : lines) 
     { 
      Iterable<String> split = Splitter.on(",").split(row); 
      String[] data = Iterables.toArray(split, String.class); 

      table.put(new Records(data[0], data[1]), new Values(data[2], data[3])); 
     } 
     return table; 
    } 

    private List<String> getAllDataRows() 
    { 
     List<String> lines = Collections.emptyList(); 

     try 
     { 
      lines = Files.readLines(new File("C:/test.csv"), Charsets.US_ASCII); 
     } 
     catch (IOException e) 
     { 
      e.printStackTrace(); 
     } 

     lines.remove(0);// remove header 

     return lines; 
    } 
} 



public class Records 
{ 
    public final String r1, r2; 

    public Records(final String r1, final String r2) 
    { 
     this.r1 = r1; 
     this.r2 = r2; 
    } 

    @Override 
    public int hashCode() 
    { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + ((r1 == null) ? 0 : r1.hashCode()); 
     result = prime * result + ((r2 == null) ? 0 : r2.hashCode()); 
     return result; 
    } 

    @Override 
    public boolean equals(final Object obj) 
    { 
     if (this == obj) 
     { 
      return true; 
     } 
     if (obj == null) 
     { 
      return false; 
     } 
     if (!(obj instanceof Records)) 
     { 
      return false; 
     } 
     Records other = (Records) obj; 
     if (r1 == null) 
     { 
      if (other.r1 != null) 
      { 
       return false; 
      } 
     } 
     else if (!r1.equals(other.r1)) 
     { 
      return false; 
     } 
     if (r2 == null) 
     { 
      if (other.r2 != null) 
      { 
       return false; 
      } 
     } 
     else if (!r2.equals(other.r2)) 
     { 
      return false; 
     } 
     return true; 
    } 

    @Override 
    public String toString() 
    { 
     StringBuilder builder = new StringBuilder(); 
     builder.append("Records1and2 [r1=").append(r1).append(", r2=").append(r2).append("]"); 
     return builder.toString(); 
    } 

} 


public class Values 
{ 
    public final String v1, v2; 

    public Values(final String v1, final String v2) 
    { 
     this.v1 = v1; 
     this.v2 = v2; 
    } 

    @Override 
    public int hashCode() 
    { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + ((v1 == null) ? 0 : v1.hashCode()); 
     result = prime * result + ((v2 == null) ? 0 : v2.hashCode()); 
     return result; 
    } 

    @Override 
    public boolean equals(final Object obj) 
    { 
     if (this == obj) 
     { 
      return true; 
     } 
     if (obj == null) 
     { 
      return false; 
     } 
     if (!(obj instanceof Values)) 
     { 
      return false; 
     } 
     Values other = (Values) obj; 
     if (v1 == null) 
     { 
      if (other.v1 != null) 
      { 
       return false; 
      } 
     } 
     else if (!v1.equals(other.v1)) 
     { 
      return false; 
     } 
     if (v2 == null) 
     { 
      if (other.v2 != null) 
      { 
       return false; 
      } 
     } 
     else if (!v2.equals(other.v2)) 
     { 
      return false; 
     } 
     return true; 
    } 

    @Override 
    public String toString() 
    { 
     StringBuilder builder = new StringBuilder(); 
     builder.append("Values1and2 [v1=").append(v1).append(", v2=").append(v2).append("]"); 
     return builder.toString(); 
    } 

} 

Answer 5

私は最近、ほとんど同じことを行う必要があったし、タスクを達成するためにtree-builder.comを書きました。唯一の違いは、CSVがレイアウトされているため、最後の2つのパラメータは、同僚の代わりに親と子になります。また、私のバージョンはヘッダー行を受け付けません。

コードはすべてJavaScriptで書かれています。それはjstreeを使用してツリーを構築します。火かき棒を使用するか、ページ上のソースを表示するだけで、それがどのように行われたかを見ることができます。最後の2つのパラメータを1つの子供に保つために、あなたのCSVでコンマをエスケープするためにそれを微調整するのはかなり簡単でしょう。

Answer 6

public static void main (String arg[]) throws Exception 
{ 
    ArrayList<String> arRows = new ArrayList<String>(); 
    arRows.add("A,XX,22,33"); 
    arRows.add("A,XX,777,888"); 
    arRows.add("A,YY,33,11"); 
    arRows.add("B,XX,12,0"); 
    arRows.add("A,YY,13,23"); 
    arRows.add("B,YY,44,98"); 
    for(String sTreeRow:createTree(arRows,",")) //or use //// or whatever applicable 
     System.out.println(sTreeRow); 
} 
    public static ArrayList<String> createTree (ArrayList<String> arRows, String sSeperator) throws Exception 
{ 
    ArrayList<String> arReturnNodes = new ArrayList<String>(); 
    Collections.sort(arRows); 
    String sLastPath = ""; 
    int iFolderLength = 0; 
    for(int iRow=0;iRow<arRows.size();iRow++) 
    { 
     String sRow = arRows.get(iRow); 
     String[] sFolders = sRow.split(sSeperator); 
     iFolderLength = sFolders.length; 
     String sTab = ""; 
     String[] sLastFolders = sLastPath.split(sSeperator); 
     for(int i=0;i<iFolderLength;i++) 
     { 
      if(i>0) 
       sTab = sTab+" "; 
      if(!sLastPath.equals(sRow)) 
      { 

       if(sLastFolders!=null && sLastFolders.length>i) 
       { 
        if(!sLastFolders[i].equals(sFolders[i])) 
        { 
         arReturnNodes.add(sTab+sFolders[i]+""); 
         sLastFolders = null; 
        } 
       } 
       else 
       { 
        arReturnNodes.add(sTab+sFolders[i]+""); 
       } 
      } 
     } 
     sLastPath = sRow; 
    } 
    return arReturnNodes; 
}