Générer une structure arborescente à partir de CSV

Question

Je me suis creusé la tête sur ce problème depuis un moment maintenant. Essentiellement, j'essaie de générer une arborescence à partir d'un ensemble de données CSV. Les données CSV ne sont pas nécessairement ordonnées. Cela ressemble à quelque chose comme suit:

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 

J'essaie de rendre le regroupement le plus flexible possible. Le plus simple pour de regroupement serait de le faire pour Record1 et Record2 avec le Valeur1 et Valeur2 stockés sous Record2 afin que nous obtenons le résultat suivant:

Record1 
    Record2 
     Value1 Value2 

qui serait:

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

je stocke mes paramètres de groupe dans une liste à l'heure actuelle - que je ne sais pas si cela entrave mes pensées. Cette liste contient une hiérarchie des groupes, par exemple:

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

Le code pour cela ressemble comme suit:

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 
} 

Je stuggling produire un algorithme pour cela, en essayant de penser à la structure sous-jacente utiliser. À l'heure actuelle, je suis l'analyse syntaxique du haut en bas CSV, en utilisant ma propre classe d'emballage:

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

Je suis juste en train de faire démarrer mon cerveau de codage.

Des pensées?

Answer 1

Sur la base de la façon dont ce problème se pose, je ferais ce qui suit:

1. Définir ce que votre structure de données finale ressembleront contenir l'arbre .
2. définir une représentation pour chaque ligne dans votre texte original (peut-être une liste chaînée de flexibilité)
3. Ecrivez une méthode qui prend la ligne représentée et l'insère dans la structure de données d'arbre. Pour chaque branche non existante, créez-la; Parcourez-le pour chaque branche existante, au fur et à mesure que vous parcourez la structure de votre liste de liens «rangée».
4. Commencez avec un arbre vide.
5. lire chaque ligne du fichier dans la structure de votre élément de ligne et appeler la méthode définie à l'étape 3.

Est-ce que l'aide?

Answer 2

L'idée de base est pas difficile: groupe par le premier enregistrement, puis par le second enregistrement, etc. jusqu'à ce que vous obtenez quelque chose comme ceci:

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

puis travailler à rebours pour construire les arbres. Cependant, il existe un composant récursif qui rend difficile de raisonner sur ce problème ou de l'afficher pas à pas. Il est donc plus facile d'écrire un pseudo-code. Je suppose que chaque ligne de votre csv est représentée comme un tuple. Chaque tuple a des "enregistrements" et des "valeurs", en utilisant les mêmes termes que vous utilisez dans votre question.Les "dossiers" sont les choses qui doivent être mises dans une structure hiérarchique. Les "valeurs" seront les feuilles de l'arbre. Je vais utiliser des citations lorsque j'utilise ces termes avec ces significations spécifiques.

Je suppose également que tous les "enregistrements" viennent avant toutes les "valeurs".

Sans plus tarder, le code:

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

Maintenant, vous auriez à réfléchir sur les structures de données spécifiques à utiliser, mais nous espérons que cela ne devrait pas être trop difficile si vous comprenez l'algorithme (comme vous mention, je pense que décider d'une structure de données tôt peut avoir empêché vos pensées).

Answer 3

Si vous savez que vous aurez seulement deux niveaux de Record s, je voudrais utiliser quelque chose comme

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

Quand vous lisez la nouvelle ligne, vous regardez dans la carte externe pour vérifier si cette valeur pour Record1 déjà existe et sinon, créez un nouveau Map intérieur vide pour cela.

Ensuite, vérifiez la carte interne si une valeur existe pour Record2. Sinon, créez un nouveau List.

Puis lisez les valeurs et ajoutez-les à la liste.

Answer 4

Voici la solution de travail de base sous la forme de junit (aucune affirmation cependant) simplifiée en utilisant google-guava collections. Le code est auto-explicatif et au lieu de fichier, vous utilisez des bibliothèques csv pour lire le csv. Cela devrait vous donner l'idée de base.

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

J'ai récemment eu besoin de faire à peu près la même chose et écrit tree-builder.com pour accomplir la tâche. La seule différence est que lorsque vous avez votre CSV, les deux derniers paramètres seront parents et enfants au lieu de pairs. De plus, ma version n'accepte pas une ligne d'en-tête.

Le code est tout en JavaScript; il utilise jstree pour construire l'arbre. Vous pouvez utiliser firebug ou juste voir la source sur la page pour voir comment c'est fait. Il serait probablement assez facile de le modifier pour échapper à la virgule dans votre CSV afin de garder les deux derniers paramètres est un seul enfant.

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