Tạo cấu trúc cây từ csv

Question

Tôi đã gãi đầu về vấn đề này trong một thời gian. Về cơ bản, tôi cố gắng tạo ra một hệ thống phân cấp cây từ một tập hợp dữ liệu CSV. Dữ liệu CSV không nhất thiết phải được đặt hàng. Điều này giống như một cái gì đó như sau:

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 

Tôi đang cố gắng thực hiện cách nhóm được thực hiện linh hoạt nhất có thể. Cách đơn giản nhất cho các nhóm sẽ làm điều đó cho Record1 và Record2 với value1 và value2 được lưu trữ dưới Record2 để chúng ta có được kết quả như sau:

Record1 
    Record2 
     Value1 Value2 

nào sẽ là:

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

Tôi đang lưu trữ cài đặt nhóm của tôi trong Danh sách hiện tại - tôi không biết liệu điều này có gây trở ngại cho suy nghĩ của tôi hay không. Danh sách này chứa một hệ thống cấp bậc của các nhóm ví dụ:

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

Mã cho điều này có vẻ như như sau:

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 
} 

Tôi stuggling sản xuất một thuật toán cho điều này, cố gắng nghĩ về cấu trúc cơ bản để sử dụng. Hiện tại tôi đang phân tích cú pháp từ trên xuống dưới, sử dụng lớp trình bao bọc của riêng tôi:

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

Tôi chỉ đang cố bắt đầu bộ não mã hóa của mình.

Mọi suy nghĩ?

Answer 1

Dựa vào cách vấn đề này được đặt ra, tôi sẽ làm như sau:

1. Xác định những gì cấu trúc dữ liệu cuối cùng của bạn sẽ trông giống như để chứa các cây .
2. Xác định đại diện cho mỗi hàng trong văn bản gốc (có thể là danh sách được liên kết để linh hoạt)
3. Viết một phương thức lấy hàng được biểu diễn và chèn nó vào cấu trúc dữ liệu cây. Đối với mỗi nhánh không tồn tại, tạo nó; cho mỗi nhánh hiện có, duyệt qua nó, khi bạn đi qua cấu trúc danh sách liên kết "hàng" của bạn.
4. Bắt đầu bằng một cây trống.
5. đọc từng dòng của tập tin vào cấu trúc mục hàng của bạn và gọi phương thức quy định tại bước 3.

Điều đó giúp đỡ?

Answer 2

Ý tưởng cơ bản là không khó: nhóm bằng kỷ lục đầu tiên, sau đó bằng kỷ lục thứ hai, vv cho đến khi bạn nhận được một cái gì đó như thế này:

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

và sau đó làm việc ngược trở lại để xây dựng cây.

Tuy nhiên, có một thành phần đệ quy làm cho nó hơi khó để lý do về vấn đề này, hoặc hiển thị từng bước, vì vậy nó thực sự dễ dàng hơn để viết mã giả.

Tôi giả sử rằng mỗi hàng trong csv của bạn được biểu thị giống như một bộ dữ liệu. Mỗi tuple có "bản ghi" và "giá trị", sử dụng cùng các thuật ngữ bạn sử dụng trong câu hỏi của mình."Bản ghi" là những thứ phải được đưa vào cấu trúc phân cấp. "Giá trị" sẽ là lá của cây. Tôi sẽ sử dụng các trích dẫn khi tôi sử dụng các thuật ngữ này với các ý nghĩa cụ thể này.

Tôi cũng giả định rằng tất cả "bản ghi" đều xuất hiện trước tất cả "giá trị".

Nếu không có thêm ado, mã:

// 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) 

Bây giờ bạn sẽ phải suy nghĩ về cấu trúc dữ liệu cụ thể để sử dụng, nhưng hy vọng này không nên quá khó khăn nếu bạn hiểu được những thuật toán (như bạn đề cập đến, tôi nghĩ rằng quyết định về cấu trúc dữ liệu sớm có thể đã cản trở suy nghĩ của bạn).

Answer 3

Nếu bạn biết bạn sẽ phải chỉ hai mức Record s, tôi sẽ sử dụng một cái gì đó giống như

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

Khi bạn đọc dòng mới, bạn nhìn vào bản đồ bên ngoài để kiểm tra xem giá trị cho Record1 đã tồn tại và nếu không, hãy tạo một ô trống mới bên trong Map cho nó.

Sau đó kiểm tra bản đồ bên trong cho dù giá trị cho rằng có tồn tại Record2 hay không. Nếu không, hãy tạo mới List.

Sau đó đọc các giá trị và thêm chúng vào danh sách.

Answer 4

Đây là giải pháp làm việc cơ bản dưới dạng junit (không có xác nhận mặc dù) được đơn giản hóa bằng cách sử dụng google-guava collections. Mã này là tự giải thích và thay vì tệp io bạn sử dụng thư viện csv để đọc csv. Điều này sẽ cung cấp cho bạn ý tưởng cơ bản.

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

Gần đây tôi đã có nhu cầu làm khá nhiều điều tương tự và đã viết tree-builder.com để hoàn thành nhiệm vụ. Sự khác biệt duy nhất là khi bạn đã đặt CSV của mình, hai tham số cuối cùng sẽ là cha mẹ và con thay vì các đồng nghiệp. Ngoài ra, phiên bản của tôi không chấp nhận hàng tiêu đề.

Mã là tất cả trong JavaScript; nó sử dụng jstree để xây dựng cây. Bạn có thể sử dụng firebug hoặc chỉ xem nguồn trên trang để xem cách nó được thực hiện. Nó có lẽ sẽ khá dễ dàng để tinh chỉnh nó để thoát khỏi dấu phẩy trong CSV của bạn để giữ cho hai tham số cuối cùng là một đứa trẻ.

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; 
}