Eine unbegrenzte Menge von Hashes basierend auf begrenzten Mengen von Hashes basierend auf Pfaden

Question

Angenommen, es gibt einen Baum, um der Argumentation willen eine XML-Struktur. Und Sie möchten einen vollständigen Satz von Wurzel-zu-Knoten-Pfaden, jedoch möchten Sie diese Menge in Gruppen von i aufteilen, wobei i benutzerdefiniert ist.

So zum Beispiel eines HTML-Dokument:

/html 
/html/head 
/html/head/title  
/html/head/title/[text] 
/html/body 
/html/body/[text] 

wird zum Beispiel, wenn ich 3:

{3, 4} 

Mit einer vereinfachten Baumklasse:

{{1, 11, 111}, {1111, 12, 121}} 

dann zum Beispiel wird das kann nur den Knotennamen bekommen; eine ArrayList von Teilbäumen erhalten; und prüfen, ob es ein Blattknoten ist; Was ist der beste Weg, um diese Hashes zu erstellen?

EDIT: Siehe meine Beispiellösung Antwort unten, das ist weit nicht optimal, wie es sehr langsam ist und vielleicht nicht einmal der beste Ansatz.

Answer 1

Meine eigene Lösung ist wie folgt, obwohl ich unsicher bin, ob dies der effizienteste Weg ist, dies zu erreichen ... vielleicht könnten andere einen Einblick in die Feinheiten von Java geben.

public ArrayList<Integer> makePathList(AbstractTree<String> tree){ 
    StringBuilder buffer = new StringBuilder(); 
    ArrayList<Integer> pl = new ArrayList<Integer>(); 
    ArrayList<StringBuilder> paths = getPaths(tree, buffer); 
    for(StringBuilder sb : paths){ 
     pl.add(sb.toString().hashCode()); 
    } 

    return pl; 
} 

public ArrayList<StringBuilder> getPaths(AbstractTree<String> tree, StringBuilder parent){ 

    ArrayList<StringBuilder> list = new ArrayList<StringBuilder>(); 
    parent.append("/"); 
    parent.append(tree.getNodeName()); 
    list.add(new StringBuilder(parent)); 
    if (!tree.isLeaf()){ 

     int i = 0; 
     Iterator<AbstractTree<String>> child = tree.getChildren().iterator(); 
     while (i < tree.getChildren().size()){ 

      list.addAll(getPaths(child.next(), new StringBuilder(parent))); 
      i++; 
     } 
    } 
    return list; 
} 

public HashSet<Integer> createShingleSet(ArrayList<Integer> paths, int shingleLength){ 
    HashSet<Integer> shingleSet = new HashSet<Integer>(); 
    for(int i = 0; i < paths.size(); i += shingleLength){ 
     Multiset<Integer> set = new Multiset<Integer>(); 
     for(int j = 0; j < shingleLength; j++){ 
      if (i + j < paths.size()) 
       set.add(paths.get(i + j));  
     } 
     shingleSet.add(set.hashCode()); 
    } 
    return shingleSet; 
} 

EDIT: Übergabe eines StringBuilder ist besser für große Dateien.

EDIT: für den gleichen Weg die gleiche Hash-Code zu geben, scheint dies später

Answer 2

Wenn ich dies tun würde, wäre mein erster Gedanke eine MultiMap (es gibt severalimplementations da draußen, oder Sie könnten Ihre eigenen rollen). Der Schlüssel dieser Multimap ist der Teilpfad, der verwendet wird, um den Knoten zu erreichen. Das Wert-Array wäre die Liste (nicht gesetzt, außer die Reihenfolge ist nicht wichtig - und in XML ist es) von Knoten, die das teilen Teilpfad.