Generar estructura de árbol de csv

Question

Me he rascado la cabeza por este problema desde hace un tiempo. Básicamente estoy tratando de generar una jerarquía de árbol a partir de un conjunto de datos CSV. Los datos CSV no están necesariamente ordenados. Esto es algo así:

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 

Estoy tratando de hacer que la agrupación se realice lo más flexible posible. El más simple de la agrupación haría que lo haga por Registro1 y RECORD2 con el valor1 y valor2 almacenado bajo RECORD2 por lo que obtenemos el siguiente resultado:

Record1 
    Record2 
     Value1 Value2 

que serían:

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

estoy almacenando la configuración de mi grupo en una lista en este momento, que no sé si esto está entorpeciendo mis pensamientos. Esta lista contiene una jerarquía de los grupos, por ejemplo:

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

El código para esto parece como sigue:

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 
} 

estoy stuggling producir un algoritmo para esto, tratando de pensar en la estructura subyacente usar. En la actualidad estoy analizar el CSV arriba a abajo, usando mi propia clase de contenedor:

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

Estoy tratando de poner en marcha mi cerebro codificación.

¿Alguna idea?

Answer 1

En base a cómo se plantea este problema, yo haría lo siguiente:

1. Definir qué es la estructura de datos final se verá así para contener el árbol .
2. definir una representación para cada fila en su texto original (tal vez una lista enlazada de flexibilidad)
3. escribir un método que toma la fila representado y lo inserta en la estructura de datos de árbol. Para cada rama inexistente, créelo; para cada rama existente, recorrela, mientras avanzas por la estructura de la lista de enlaces de "fila".
4. Comience con un árbol vacío.
5. leer cada línea del archivo en su estructura de elemento de la fila y llamar al método definido en el paso 3.

¿Le ayuda?

Answer 2

La idea básica no es difícil: Grupo en el primer registro, y luego por el segundo registro, etc. hasta que llegue algo como esto:

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

y luego trabajar hacia atrás para construir los árboles.

Sin embargo, hay un componente recursivo que hace que sea un poco difícil razonar sobre este problema, o mostrarlo paso a paso, por lo que es realmente más fácil escribir un seudocódigo.

Supongo que cada fila en su csv se representa como una tupla. Cada tupla tiene "registros" y "valores", usando los mismos términos que usa en su pregunta."Registros" son las cosas que se deben poner en una estructura jerárquica. "Valores" serán las hojas del árbol. Usaré citas cuando use estos términos con estos significados específicos.

También asumo que todos los "registros" vienen antes de todos los "valores".

Sin más, el código:

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

Ahora que lo tienes que pensar en las estructuras de datos específicos a utilizar, pero espero que esto no debería ser demasiado difícil si se entiende el algoritmo (como se Mencione, creo que decidir sobre una estructura de datos desde el principio puede haber estado obstaculizando sus pensamientos).

Answer 3

Si sabe que va a tener sólo dos niveles de Record s, me gustaría utilizar algo así como

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

Al leer la nueva línea, se mira en el mapa exterior para comprobar si ese valor para Record1 ya existe y si no, crea un nuevo interior vacío Map para él.

Luego compruebe el mapa interno si existe un valor para ese Record2. Si no, cree un nuevo List.

Luego lea los valores y agréguelos a la lista.

Answer 4

Aquí está la solución de trabajo básica en forma de junit (sin aserciones) simplificada mediante el uso de google-guava collections. El código se explica por sí mismo y en lugar del archivo io usted usa bibliotecas csv para leer el csv. Esto debería darte la idea básica.

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

Recientemente he tenido la necesidad de hacer más o menos lo mismo y escribí tree-builder.com para realizar la tarea. La única diferencia es que a medida que tenga su CSV distribuido, los dos últimos parámetros serán padre e hijo en lugar de pares. Además, mi versión no acepta una fila de encabezado.

El código está todo en JavaScript; usa jstree para construir el árbol. Puede usar Firebug o simplemente ver la fuente en la página para ver cómo se hace. Probablemente sería bastante fácil ajustarlo para escapar de la coma en tu CSV para mantener los dos últimos parámetros en un solo hijo.

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