Wo finde ich eine standardmäßige Trie-basierte Kartenimplementierung in Java? [geschlossen]

76

Ich habe ein Java-Programm, das viele Zuordnungen von Strings zu verschiedenen Objekten speichert.

Im Moment kann ich mich entweder auf Hashing (über HashMap) oder auf binäre Suchen (über TreeMap) verlassen. Ich frage mich, ob es eine effiziente und standardmäßige trie-basierte Kartenimplementierung in einer beliebten und hochwertigen Sammlungsbibliothek gibt.

Ich habe in der Vergangenheit meine eigenen geschrieben, aber ich würde lieber etwas Standardisches verwenden, falls verfügbar.

Schnelle Klarstellung: Während meine Frage allgemein ist, beschäftige ich mich im aktuellen Projekt mit vielen Daten, die durch einen vollqualifizierten Klassennamen oder eine Methodensignatur indiziert sind. Daher gibt es viele gemeinsame Präfixe.

Uri
quelle
Sind die Saiten im Voraus bekannt? Müssen sie nur über eine Zeichenfolge aufgerufen werden?
sfossen

Antworten:

32

Vielleicht möchten Sie sich die Trie-Implementierung ansehen , die Limewire zur Google Guava beiträgt .

David Schlosnagle
quelle
8
Es sieht so aus, als ob Google-Collections von Guava code.google.com/p/guava-libraries abgelöst wurde , und leider kann ich dort nirgendwo eine Trie-Klasse sehen. Die Patricia Trie scheint jetzt eine eigene Projektseite zu haben: code.google.com/p/patricia-trie
Dan J
1
Die Limewire / Google-Links sind jetzt auch ein bisschen chaotisch. Während ich habe es geschaffen , zu finden code.google.com/archive/p/google-collections/issues/5 mit den tatsächlichen Dateien, beachten Sie, dass Apache Commons Sammlungen kommen mit einer Anzahl von Versuchen (einschließlich einer patricia trie). Das würde ich jetzt empfehlen.
Jason C
Auch die Apache Commons-Implementierung scheint vom selben Ort zu stammen wie der Limewire-Beitrag, da die zusammenfassenden Kommentare in den Commons-Dokumenten für PatriciaTrie mit den zusammenfassenden Kommentaren in der von Limewire bereitgestellten Implementierung identisch sind.
Jason C
10

In den Java-Kernbibliotheken gibt es keine Datenstruktur.

Dies kann daran liegen, dass Versuche normalerweise zum Speichern von Zeichenfolgen konzipiert sind, während Java-Datenstrukturen allgemeiner sind und normalerweise alle enthalten Object(Definieren von Gleichheit und einer Hash-Operation), obwohl sie manchmal auf ComparableObjekte beschränkt sind (Definieren einer Reihenfolge). Es gibt keine gemeinsame Abstraktion für "eine Folge von Symbolen", obwohl CharSequencesie für Zeichenketten geeignet ist, und ich nehme an, Sie könnten etwas Iterablefür andere Arten von Symbolen tun .

Hier ist ein weiterer zu berücksichtigender Punkt: Wenn Sie versuchen, einen herkömmlichen Versuch in Java zu implementieren, werden Sie schnell mit der Tatsache konfrontiert, dass Java Unicode unterstützt. Um Platz zu sparen, müssen Sie die Zeichenfolgen in Ihrem Versuch auf eine Teilmenge von Symbolen beschränken oder den herkömmlichen Ansatz zum Speichern von untergeordneten Knoten in einem durch Symbole indizierten Array aufgeben. Dies könnte ein weiterer Grund sein, warum Versuche nicht als allgemein genug für die Aufnahme in die Kernbibliothek angesehen werden und etwas, auf das Sie achten sollten, wenn Sie Ihre eigene Bibliothek implementieren oder eine Bibliothek eines Drittanbieters verwenden.

erickson
quelle
Bei dieser Antwort wird davon ausgegangen, dass ich einen Versuch für Zeichenfolgen implementieren möchte. Ein Trie ist eine allgemeine Datenstruktur, die beliebige Sequenzen enthalten und schnelle Präfixsuchen ermöglichen kann.
Paul Draper
1
@PaulDraper Diese Antwort setzt nichts über das voraus, was Sie wollen, da Sie Jahre nach der Frage aufgetaucht sind. Und da es bei der Frage speziell um Zeichenketten geht, steht dies im Mittelpunkt dieser Antwort. Obwohl ich viel Zeit damit verbringe, darauf hinzuweisen, dass ein Java-Trie auf jede Art von verallgemeinert werden müsste Comparable.
Erickson
7

Schauen Sie sich auch die gleichzeitigen Bäume an . Sie unterstützen sowohl Radix- als auch Suffix-Bäume und sind für Umgebungen mit hoher Parallelität konzipiert.

Alex Beardsley
quelle
3
Ab 2014 sollte dies die akzeptierte Antwort sein. Sieht nach einer gut gewarteten, gut getesteten und gleichzeitigen Implementierung von Versuchen aus.
Knub
5

Apache Commons Collections v4.0 unterstützt jetzt Trie-Strukturen.

Weitere Informationen finden Sie in den org.apache.commons.collections4.triePaketinformationen . Überprüfen Sie insbesondere die PatriciaTrieKlasse:

Implementierung eines PATRICIA-Versuchs (praktischer Algorithmus zum Abrufen von alphanumerisch codierten Informationen).

Ein PATRICIA Trie ist ein komprimierter Trie. Anstatt alle Daten an den Rändern des Trie zu speichern (und leere interne Knoten zu haben), speichert PATRICIA Daten in jedem Knoten. Dies ermöglicht sehr effiziente Operationen zum Durchlaufen, Einfügen, Löschen, Vorgänger, Nachfolger, Präfix, Bereich und Auswählen (Objekt). Alle Operationen werden im schlimmsten Fall in der O (K) -Zeit ausgeführt, wobei K die Anzahl der Bits im größten Element im Baum ist. In der Praxis benötigen Operationen tatsächlich O (A (K)) Zeit, wobei A (K) die durchschnittliche Anzahl von Bits aller Elemente im Baum ist.

Duncan Jones
quelle
3

Ich habe hier eine einfache und schnelle Implementierung geschrieben und veröffentlicht .

Melinda Green
quelle
Ich würde das gerne mögen, aber jeder Ihrer Knoten benötigt 1024 Bytes und repräsentiert nur ein Zeichen. Auch das Einfügen dauert jetzt O (n ^ 2), da Java die Semantik von substring () geändert hat. Diese Implementierung ist wirklich nicht sehr praktisch.
Stefan Reich
@Stefan Reich, Dieser Array-Raum ist nur für interne Knoten vorgesehen, der angesichts der Geschwindigkeit, mit der sich Trie-Bäume auffächern, verschwindend klein ist.
Melinda Green
Vielen Dank für Ihre Antwort, aber ich bin nicht überzeugt. Versuche verzweigen sich möglicherweise nicht immer schnell, tatsächlich werden sie es wahrscheinlich nicht mit echten Daten tun. Ihre Arrays suchen auch nur langsam nach Inhalten. Wir sollten Patricia Tries wirklich nutzen, um die Dinge kompakt und effizient zu gestalten. Ich habe meine eigene Implementierung gemacht, die ich wahrscheinlich in Kürze hier veröffentlichen werde. Keine harten Gefühle, nur um zu optimieren :) Viele Grüße
Stefan Reich
Meine Versuche können nur schnell auffächern, da Redundanzen herausgerechnet und im "Präfix" -Mitglied gespeichert werden. Es gibt Platz für viele verschiedene Implementierungen, je nachdem, was Sie optimieren möchten. In meinem Fall strebe ich einfach und doch praktisch an.
Melinda Green
1
Ah, ich habe diesen Teil des Codes falsch verstanden. Es gibt so viel "Objekt" und Casting, dass ich es nicht gesehen habe. Es ist also eine Patricia Trie. Mein Fehler.
Stefan Reich
1

Was Sie brauchen org.apache.commons.collections.FastTreeMap, denke ich.

andrii
quelle
Dies scheint keine Trie-Implementierung zu sein.
Duncan Jones
1

Sie können die Completely Java-Bibliothek ausprobieren, die eine PatriciaTrie- Implementierung enthält. Die API ist klein und einfach zu starten und im zentralen Maven-Repository verfügbar .

Filipe Miguel Fonseca
quelle
0

Sie können sich auch diesen TopCoder ansehen (Registrierung erforderlich ...).

TofuBeer
quelle
Ich habe mich registriert, aber diese Komponente ist jetzt nicht verfügbar.
Deepak
0

Wenn Sie eine sortierte Karte benötigen, lohnen sich Versuche. Wenn Sie dies nicht tun, ist eine Hashmap besser. Hashmap mit String-Schlüsseln kann gegenüber der Standard-Java-Implementierung verbessert werden: Array-Hash-Map

RokL
quelle
0

Unten finden Sie eine grundlegende HashMap-Implementierung eines Trie. Einige Leute finden das vielleicht nützlich ...

class Trie {

    HashMap<Character, HashMap> root;

    public Trie() {
        root = new HashMap<Character, HashMap>();
    }

    public void addWord(String word) {
        HashMap<Character, HashMap> node = root;
        for (int i = 0; i < word.length(); i++) {
            Character currentLetter = word.charAt(i);
            if (node.containsKey(currentLetter) == false) {
                node.put(currentLetter, new HashMap<Character, HashMap>());
            }
            node = node.get(currentLetter);
        }
    }

    public boolean containsPrefix(String word) {
        HashMap<Character, HashMap> node = root;
        for (int i = 0; i < word.length(); i++) {
            Character currentLetter = word.charAt(i);
            if (node.containsKey(currentLetter)) {
                node = node.get(currentLetter);
            } else {
                return false;
            }
        }
        return true;
    }
}
Martynas
quelle
0

Hier ist meine Implementierung, genießen Sie es über: GitHub - MyTrie.java

/* usage:
    MyTrie trie = new MyTrie();
    trie.insert("abcde");
    trie.insert("abc");
    trie.insert("sadas");
    trie.insert("abc");
    trie.insert("wqwqd");
    System.out.println(trie.contains("abc"));
    System.out.println(trie.contains("abcd"));
    System.out.println(trie.contains("abcdefg"));
    System.out.println(trie.contains("ab"));
    System.out.println(trie.getWordCount("abc"));
    System.out.println(trie.getAllDistinctWords());
*/

import java.util.*;

public class MyTrie {
  private class Node {
    public int[] next = new int[26];
    public int wordCount;
    public Node() {
      for(int i=0;i<26;i++) {
        next[i] = NULL;
      }
      wordCount = 0;
    }
  }

  private int curr;
  private Node[] nodes;
  private List<String> allDistinctWords;
  public final static int NULL = -1;

  public MyTrie() {
    nodes = new Node[100000];
    nodes[0] = new Node();
    curr = 1;
  }

  private int getIndex(char c) {
    return (int)(c - 'a');
  }

  private void depthSearchWord(int x, String currWord) {
    for(int i=0;i<26;i++) {
      int p = nodes[x].next[i];
      if(p != NULL) {
        String word = currWord + (char)(i + 'a');
        if(nodes[p].wordCount > 0) {
          allDistinctWords.add(word);
        }
        depthSearchWord(p, word);
      }
    }
  }

  public List<String> getAllDistinctWords() {
    allDistinctWords = new ArrayList<String>();
    depthSearchWord(0, "");
    return allDistinctWords;
  }

  public int getWordCount(String str) {
    int len = str.length();
    int p = 0;
    for(int i=0;i<len;i++) {
      int j = getIndex(str.charAt(i));
      if(nodes[p].next[j] == NULL) {
        return 0;
      }
      p = nodes[p].next[j];
    }
    return nodes[p].wordCount;
  }

  public boolean contains(String str) {
    int len = str.length();
    int p = 0;
    for(int i=0;i<len;i++) {
      int j = getIndex(str.charAt(i));
      if(nodes[p].next[j] == NULL) {
        return false;
      }
      p = nodes[p].next[j];
    }
    return nodes[p].wordCount > 0;
  }

  public void insert(String str) {
    int len = str.length();
    int p = 0;
    for(int i=0;i<len;i++) {
      int j = getIndex(str.charAt(i));
      if(nodes[p].next[j] == NULL) {
        nodes[curr] = new Node();
        nodes[p].next[j] = curr;
        curr++;
      }
      p = nodes[p].next[j];
    }
    nodes[p].wordCount++;
  }
}
coderz
quelle
0

Ich habe gerade meine eigene Concurrent TRIE-Implementierung ausprobiert, die jedoch nicht auf Zeichen basiert, sondern auf HashCode. Trotzdem können wir diese Karte mit Karte für jeden CHAR-Hascode verwenden.
Sie können dies mit dem Code @ https://github.com/skanagavelu/TrieHashMap/blob/master/src/TrieMapPerformanceTest.java https://github.com/skanagavelu/TrieHashMap/blob/master/src/TrieMapValidationTest.java testen

import java.util.concurrent.atomic.AtomicReferenceArray;

public class TrieMap {
    public static int SIZEOFEDGE = 4; 
    public static int OSIZE = 5000;
}

abstract class Node {
    public Node getLink(String key, int hash, int level){
        throw new UnsupportedOperationException();
    }
    public Node createLink(int hash, int level, String key, String val) {
        throw new UnsupportedOperationException();
    }
    public Node removeLink(String key, int hash, int level){
        throw new UnsupportedOperationException();
    }
}

class Vertex extends Node {
    String key;
    volatile String val;
    volatile Vertex next;

    public Vertex(String key, String val) {
        this.key = key;
        this.val = val;
    }

    @Override
    public boolean equals(Object obj) {
        Vertex v = (Vertex) obj;
        return this.key.equals(v.key);
    }

    @Override
    public int hashCode() {
        return key.hashCode();
    }

    @Override
    public String toString() {
        return key +"@"+key.hashCode();
    }
}


class Edge extends Node {
    volatile AtomicReferenceArray<Node> array; //This is needed to ensure array elements are volatile

    public Edge(int size) {
        array = new AtomicReferenceArray<Node>(8);
    }


    @Override
    public Node getLink(String key, int hash, int level){
        int index = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level);
        Node returnVal = array.get(index);
        for(;;) {
            if(returnVal == null) {
                return null;
            }
            else if((returnVal instanceof Vertex)) {
                Vertex node = (Vertex) returnVal;
                for(;node != null; node = node.next) {
                    if(node.key.equals(key)) {  
                        return node; 
                    }
                } 
                return null;
            } else { //instanceof Edge
                level = level + 1;
                index = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level);
                Edge e = (Edge) returnVal;
                returnVal = e.array.get(index);
            }
        }
    }

    @Override
    public Node createLink(int hash, int level, String key, String val) { //Remove size
        for(;;) { //Repeat the work on the current node, since some other thread modified this node
            int index =  Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level);
            Node nodeAtIndex = array.get(index);
            if ( nodeAtIndex == null) {  
                Vertex newV = new Vertex(key, val);
                boolean result = array.compareAndSet(index, null, newV);
                if(result == Boolean.TRUE) {
                    return newV;
                }
                //continue; since new node is inserted by other thread, hence repeat it.
            } 
            else if(nodeAtIndex instanceof Vertex) {
                Vertex vrtexAtIndex = (Vertex) nodeAtIndex;
                int newIndex = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, vrtexAtIndex.hashCode(), level+1);
                int newIndex1 = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level+1);
                Edge edge = new Edge(Base10ToBaseX.Base.BASE8.getLevelZeroMask()+1);
                if(newIndex != newIndex1) {
                    Vertex newV = new Vertex(key, val);
                    edge.array.set(newIndex, vrtexAtIndex);
                    edge.array.set(newIndex1, newV);
                    boolean result = array.compareAndSet(index, vrtexAtIndex, edge); //REPLACE vertex to edge
                    if(result == Boolean.TRUE) {
                        return newV;
                    }
                   //continue; since vrtexAtIndex may be removed or changed to Edge already.
                } else if(vrtexAtIndex.key.hashCode() == hash) {//vrtex.hash == hash) {       HERE newIndex == newIndex1
                    synchronized (vrtexAtIndex) {   
                        boolean result = array.compareAndSet(index, vrtexAtIndex, vrtexAtIndex); //Double check this vertex is not removed.
                        if(result == Boolean.TRUE) {
                            Vertex prevV = vrtexAtIndex;
                            for(;vrtexAtIndex != null; vrtexAtIndex = vrtexAtIndex.next) {
                                prevV = vrtexAtIndex; // prevV is used to handle when vrtexAtIndex reached NULL
                                if(vrtexAtIndex.key.equals(key)){
                                    vrtexAtIndex.val = val;
                                    return vrtexAtIndex;
                                }
                            } 
                            Vertex newV = new Vertex(key, val);
                            prevV.next = newV; // Within SYNCHRONIZATION since prevV.next may be added with some other.
                            return newV;
                        }
                        //Continue; vrtexAtIndex got changed
                    }
                } else {   //HERE newIndex == newIndex1  BUT vrtex.hash != hash
                    edge.array.set(newIndex, vrtexAtIndex);
                    boolean result = array.compareAndSet(index, vrtexAtIndex, edge); //REPLACE vertex to edge
                    if(result == Boolean.TRUE) {
                        return edge.createLink(hash, (level + 1), key, val);
                    }
                }
            }               
            else {  //instanceof Edge
                return nodeAtIndex.createLink(hash, (level + 1), key, val);
            }
        }
    }




    @Override
    public Node removeLink(String key, int hash, int level){
        for(;;) {
            int index = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level);
            Node returnVal = array.get(index);
            if(returnVal == null) {
                return null;
            }
            else if((returnVal instanceof Vertex)) {
                synchronized (returnVal) {
                    Vertex node = (Vertex) returnVal;
                    if(node.next == null) {
                        if(node.key.equals(key)) {
                            boolean result = array.compareAndSet(index, node, null); 
                            if(result == Boolean.TRUE) {
                                return node;
                            }
                            continue; //Vertex may be changed to Edge
                        }
                        return null;  //Nothing found; This is not the same vertex we are looking for. Here hashcode is same but key is different. 
                    } else {
                        if(node.key.equals(key)) { //Removing the first node in the link
                            boolean result = array.compareAndSet(index, node, node.next);
                            if(result == Boolean.TRUE) {
                                return node;
                            }
                            continue; //Vertex(node) may be changed to Edge, so try again.
                        }
                        Vertex prevV = node; // prevV is used to handle when vrtexAtIndex is found and to be removed from its previous
                        node = node.next;
                        for(;node != null; prevV = node, node = node.next) {
                            if(node.key.equals(key)) {
                                prevV.next = node.next; //Removing other than first node in the link
                                return node; 
                            }
                        } 
                        return null;  //Nothing found in the linked list.
                    }
                }
            } else { //instanceof Edge
                return returnVal.removeLink(key, hash, (level + 1));
            }
        }
    }

}



class Base10ToBaseX {
    public static enum Base {
        /**
         * Integer is represented in 32 bit in 32 bit machine.
         * There we can split this integer no of bits into multiples of 1,2,4,8,16 bits
         */
        BASE2(1,1,32), BASE4(3,2,16), BASE8(7,3,11)/* OCTAL*/, /*BASE10(3,2),*/ 
        BASE16(15, 4, 8){       
            public String getFormattedValue(int val){
                switch(val) {
                case 10:
                    return "A";
                case 11:
                    return "B";
                case 12:
                    return "C";
                case 13:
                    return "D";
                case 14:
                    return "E";
                case 15:
                    return "F";
                default:
                    return "" + val;
                }

            }
        }, /*BASE32(31,5,1),*/ BASE256(255, 8, 4), /*BASE512(511,9),*/ Base65536(65535, 16, 2);

        private int LEVEL_0_MASK;
        private int LEVEL_1_ROTATION;
        private int MAX_ROTATION;

        Base(int levelZeroMask, int levelOneRotation, int maxPossibleRotation) {
            this.LEVEL_0_MASK = levelZeroMask;
            this.LEVEL_1_ROTATION = levelOneRotation;
            this.MAX_ROTATION = maxPossibleRotation;
        }

        int getLevelZeroMask(){
            return LEVEL_0_MASK;
        }
        int getLevelOneRotation(){
            return LEVEL_1_ROTATION;
        }
        int getMaxRotation(){
            return MAX_ROTATION;
        }
        String getFormattedValue(int val){
            return "" + val;
        }
    }

    public static int getBaseXValueOnAtLevel(Base base, int on, int level) {
        if(level > base.getMaxRotation() || level < 1) {
            return 0; //INVALID Input
        }
        int rotation = base.getLevelOneRotation();
        int mask = base.getLevelZeroMask();

        if(level > 1) {
            rotation = (level-1) * rotation;
            mask = mask << rotation;
        } else {
            rotation = 0;
        }
        return (on & mask) >>> rotation;
    }
}
Kanagavelu Sugumar
quelle