從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 

我試圖讓分組的執行方式儘可能靈活。對於分組的最簡單的將這樣做對記錄1和RECORD2與RECORD2下存儲的值1和值2，使我們得到如下輸出：

Record1 
    Record2 
     Value1 Value2 

具體做法是：

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

我存儲我目前在List中的組設置 - 我不知道這是否妨礙了我的想法。此列表中包含組例如層次：

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 
} 

我都有點吃力生產這種算法，冥思苦想的底層結構使用。目前我使用自己的包裝類從上到下解析CSV：

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

我只是試圖啓動我的編碼大腦。

有什麼想法？

Answer 1

基於這個問題是怎麼造成的，我會做到以下幾點：

1. 定義你的最終數據結構看起來像遏制 樹。
2. 定義您的原始文本中的每一行的表示 （可能是一個靈活的鏈表）
3. 編寫一個方法，它將表示的行插入到樹數據結構中。對於每個不存在的分支，創建它;對於每個現有分支，在遍歷「行」鏈接列表結構時遍歷它。
4. 從空樹開始。
5. 閱讀文件的每一行到您的行項目結構，並呼籲在步驟3

是否幫助定義的方法？

Answer 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 S，當你讀到新行我會使用類似

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

，你看看到外地圖，以檢查是否爲Record1已經是值如果不存在，則爲其創建新的空內部Map。

然後檢查內部圖是否存在該Record2的值。如果沒有，則創建新的List。

然後讀取值並將它們添加到列表中。

Answer 4

這裏是junit形式的基本工作解決方案（雖然沒有斷言）通過使用google-guava collections簡化。代碼是不言自明的，而不是文件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文件時，最後兩個參數將是父母和孩子，而不是同齡人。另外，我的版本不接受標題行。

代碼全部在JavaScript中;它使用jstree來構建樹。您可以使用螢火蟲或只查看網頁上的來源，看看它是如何完成的。調整它可能很容易，以避免您的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; 
}