Bauen trie schneller

Mache ich eine mobile app, die die Bedürfnisse von tausenden von schnell-string-suchen und Präfix überprüft. Um diese Fahrt, machte ich einen Trie aus meiner word-Liste, die hat ungefähr 180.000 Wörter.

Alles Super, aber das einzige problem ist, dass der Bau dieser riesigen trie (es hat etwa 400.000 Knoten) dauert etwa 10 Sekunden derzeit auf meinem Handy, das ist wirklich langsam.

Hier ist der code, baut die Marina.

public SimpleTrie makeTrie(String file) throws Exception {
    String line;
    SimpleTrie trie = new SimpleTrie();

    BufferedReader br = new BufferedReader(new FileReader(file));
    while( (line = br.readLine()) != null) {
        trie.insert(line);
    }
    br.close();

    return trie;
}

Den insert Methode, die läuft auf O(length of key)

public void insert(String key) {
    TrieNode crawler = root;
    for(int level=0 ; level < key.length() ; level++) {
        int index = key.charAt(level) - 'A';
        if(crawler.children[index] == null) {
            crawler.children[index] = getNode();
        }
        crawler = crawler.children[index];
    }
    crawler.valid = true;
}

Ich bin auf der Suche nach intuitiven Methoden zu bauen, die versuche schneller. Vielleicht Baue ich die versuche einfach mal mein laptop, und speichern Sie es irgendwie an der Festplatte, und aus einer Datei laden in das Telefon? Aber ich weiß nicht, wie diese umzusetzen ist.

Oder gibt es irgendwelche anderen Präfix-Daten-Strukturen, die in weniger Zeit zu bauen, haben aber ähnliche lookup-Zeit-Komplexität?

Anregungen werden geschätzt. Vielen Dank im Voraus.

BEARBEITEN

Jemand schlug vor, mit Hilfe der Java-Serialisierung. Ich habe es versucht, aber es war sehr langsam mit diesem code:

public void serializeTrie(SimpleTrie trie, String file) {
        try {
            ObjectOutput out = new ObjectOutputStream(new BufferedOutputStream(new FileOutputStream(file)));
            out.writeObject(trie);
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public SimpleTrie deserializeTrie(String file) {
        try {
            ObjectInput in = new ObjectInputStream(new BufferedInputStream(new FileInputStream(file)));
            SimpleTrie trie = (SimpleTrie)in.readObject();
            in.close();
            return trie;
        } catch (IOException | ClassNotFoundException e) {
            e.printStackTrace();
            return null;
        }
    }

Kann dieser obige code schneller gemacht werden?

Meine versuche: http://pastebin.com/QkFisi09

Wort-Liste: http://www.isc.ro/lists/twl06.zip

Android-IDE zum ausführen von code: http://play.google.com/store/apps/details?id=com.jimmychen.app.sand

  • Ich kann nicht installieren Sie die ide auf einem android gingerbread?
  • Ich würde vorschlagen, zu Beginn von profiling. Zumindest Messung von dem Teil verbracht, für (1) beim Lesen der Datei, (2) Suche nach Ort in trie-und (3) eine neue Verknüpfung zu erstellen
  • Hast du schon versucht die binary search Methode? Ich sah, wie gute Ergebnisse mit es.
  • Ja habe ich versuche es, aber es schien nicht zu schnell. Ich brauche nur zwei Fragen: ob ein Präfix vorhanden ist, und ob ein Wort existiert. Ich brauche nicht alle strings, die aus einem Präfix. Btw, ich zählte die Anzahl der Präfix-Existenz sucht, war es etwa 10.000.. also die binary search Methode wurde langsamer, denn mit dem Kumpel, der ganze Algorithmus beendet in ~60 ms.
  • OK, gut dass du eine Lösung gefunden. Ich fand nie ein Präfix Abfragen, die langsamer war als 1 Millisekunde und der gleichen für die Existenz einer einzigen Zeichenkette, aber vielleicht habe ich eine schnellere Telefon.
  • Performance-Vergleich DAFSA Speicher verbraucht: 16020976 DAFSA (ms) : [100] 0 DAFSA (ms) : [10000] 5 DAFSA (ms) : [1000000] 28 --------------- trie Speicher verbraucht: 12946984 trie (ms) : [100] 0 trie (ms) : [10000] 6 trie (ms) : [1000000] 131 --------------- Liste belegter Speicher: 1761728 Liste (ms) : [100] 23 Liste (ms) : [10000] 696 Liste (ms) : [1000000] 71752 --------------- Set memory verbraucht: 2341616 Set (ms) : [100] 0 (ms) : [10000] 1 Satz (ms) : [1000000] 22

InformationsquelleAutor Bruce | 2013-09-23
  1. 24

    Doppel-Array versucht sind sehr schnell zu laden/speichern, da alle Daten gespeichert in lineare arrays. Sie sind auch sehr schnell nachschlagen kann, aber die Insertionen können teuer werden. Ich Wette, es gibt eine Java-Implementierung irgendwo.

    Auch, wenn die Daten statisch sind (D. H. Sie nicht, aktualisieren Sie es auf dem Telefon) zu prüfen, DAFSA für Ihre Aufgabe. Es ist eine der effizientesten Daten-Strukturen für die Speicherung der Worte (besser sein muss als "standard" versucht und radix versucht, sowohl für Größe und Geschwindigkeit, besser als prägnante versucht für Geschwindigkeit, oft besser als prägnante versucht, für die Größe). Es ist ein gutes C++ - Implementierung: dawgdic - Sie können es verwenden, um zu bauen DAFSA von der Kommandozeile aus und verwenden Sie dann eine Java-reader für die resultierende Datenstruktur (Beispiel-Implementierung ist hier).

    • Hi. Nach viel Kopf schlug, habe ich erfolgreich erstellen können, DAWG und Lesen Sie es von Java. Es ist klein (537K) und rasend schnell. Es gibt jedoch ein problem, das mich daran hindert, schließen sich diese Frage permanent auf der Github-code kann nur überprüfen, ob ein string ein Präfix eines Wortes im Wörterbuch, kann es nicht überprüfen, ob der string ein ganzes Wort. Ich habe verschwendet meine ganze Zeit versucht, herauszufinden, diese. Meine app kann nicht funktionieren, ohne dass. Kannst du bitte einen Blick drauf werfen?
    • Man könnte anfügen, einige nicht verwendete symbol (z.B. '$') am Ende jedes Wort aus dem Wörterbuch. Dann einfach mal nach 'word' für ein Präfix und 'Wort$' für ein ganzes Wort.
    • Ja, ich könnte das tun - aber ich denke wirklich, dass diese Funktionalität gibt es in dem code - ich kann es nicht finden. Warten auf Michail Antwort. Btw, hier einige Codes zum testen der DAWG: dl.dropboxusercontent.com/u/19729481/DawgTest.7z funktioniert Nicht wie erwartet.
    • Hi @Bruce, es ist eine Prüfung fehlt im 'enthält' - Methode - es sollte True zurückgeben, nur wenn es einen Wert mit einem index verknüpft (return hasValue(index) statt return true sollte funktionieren). Habe ich noch nicht getestet/verwendet verknüpfte Java-Implementierung selbst; es kann gut funktionieren, für das die software geschrieben wurde, aber nicht als eine Allgemeine Java-Implementierung. Tut mir Leid, Ihre Zeit verschwenden. Dieses Python-Implementierung ist stark getestet und ich bin mir ziemlich sicher, dass es ordnungsgemäß funktioniert: github.com/kmike/DAWG-Python/blob/... - konsultieren, wenn im Zweifel.
    • ah, und es gibt den "canonical" - C++ - Quellcode, natürlich: code.google.com/p/dawgdic/source/browse/trunk/src/dawgdic/...
    • Ich versuche zu Lesen, der Kumpel von dawg_python, um zu überprüfen, Indizes, die zurückgegeben werden, gegen die Java one. Warum ist dieser code der Rückgabe eines leeren Arrays? print dawg_python.DAWG().load('dawg.bin').prefixes(u'MAX')
    • Ich habe versucht return hasValue(index), hat nicht funktioniert. Ich überprüft mit C++ und Python-code. Können Sie bitte schauen Sie auf der Java-code einmal, wenn Sie Zeit haben? Sie sind wahrscheinlich die bekannteste person, mit der Umsetzung! Wenn dem nicht so ist, wo kann ich lernen, die internen Datei-Struktur der dawg, so dass ich Debuggen kann es mich?
    • Für Ihre Bequemlichkeit.. Hier ist ein link zu einem Eclipse-Projekt zum testen der Java-Implementierung der dawg, so dass Sie nicht haben, es selbst zu machen - dl.dropboxusercontent.com/u/19729481/DawgTest.7z
    • Ich denke, dass es 2 mögliche Probleme. 1) es scheint, dass Sie verwendet haben, machen-dawg Befehlszeilen-Dienstprogramm, das erfordert LF-Zeilenenden, und TWL06.txt Datei verwendet CRLF Zeilenenden. 'HELLO\r'in dawg_python.DAWG().load('dawg.bin') gibt True zurück. 2) das Zweite Problem ist, dass Sie nicht verwendet haben '-g' - option, so DAWG entstand ohne Anleitung und schnell Schlüssel Abschluss (D. H. finden Sie alle Schlüssel, die mit einem gegebenen Präfix) nicht funktioniert. Bitte beachten Sie, dass d....Präfixe(u'MAX') findet alle Wörter, die das sind Präfixe von u'MAX' (leer, weil der '\r' - Problem), nicht alle Wörter, beginnt mit u-'MAX'.
    • JA. Das war es dann. Die CRLF-Zeilenenden und die hasValue(index) zusammen wreaked das ganze Unheil. Ich kann nicht in Worten Ausdrücken, wie dankbar ich bin für all Eure Hilfe. Danke, dass Sie freundlich genug, um mir zu helfen, durch diese. Sie sind eine wunderbare person. Ich werde jetzt sendet einen pull-request auf, dass Java-repo, und von ganzem Herzen akzeptieren Sie diese wunderbare Antwort. Genießen Sie Ihren 5k! 🙂
    • Haben Sie das auch irgendwo gehostet auf github oder sonstwo, kann ich schauen ? Ich tun etwas ähnliches in c# und wäre eine große Hilfe, wenn ich einige Beispiel-code zu durchsuchen. Dank

    InformationsquelleAutor Mikhail Korobov
  2. 3

    Könnten Sie speichern Sie Ihre versuche, wie ein array von Knoten, die mit Referenzen auf die untergeordneten Knoten ersetzt, mit array-Indizes. Ihr root-Knoten wäre das erste element. So könnte man auf einfache Weise speichern/laden Sie Ihre versuche vom einfachen Binär-oder text-format.

    public class SimpleTrie {
    public class TrieNode {
        boolean valid;
        int[] children;
    }
    private TrieNode[] nodes;
    private int numberOfNodes;

    private TrieNode getNode() {
        TrieNode t = nodes[++numberOnNodes];
        return t;
    }
}
    • Ich dachte darüber nach, konnte es aber nicht vorwärts gehen mit ihm. Wie kann ich für die rekursive Struktur des trie? Wie werden die Eltern-und Kind-Indizes in dem array zu tun? Wie kann sichergestellt werden, dass es erzeugt genau die gleiche versuchten, und nicht einen anderen trie, die die gleiche byte-Darstellung?
    • Ich sehe nicht das problem. Die rekursive Struktur des Baums definiert ist, durch diese index-Werte, die man serialisieren und mit allem anderen. Die Eltern-und Kind-Indizes bezogen sind, in das child-index gespeichert ist, in die übergeordneten Knoten, ersetzt das Kind die Referenz. Sie serialisieren durch Iteration durch das gesamte array, das ignorieren der Trie-Struktur. Ein index ist ein index, ob eine Datei oder ein array sein. Sie nicht zu tun haben, die binäre Serialisierung (aber können, wenn Sie wollen) - wenn Sie serialisieren einem Knoten pro Textzeile (z.B. eine CSV-Datei) die Knoten-Nummern werden auch Zeilennummern.
    • Oh tut mir Leid habe ich völlig falsch gelesen, dass gestern, zu müde, denke ich. Jetzt bekomme ich es, so einfach. Werde versuchen, und lassen Sie wissen.
    InformationsquelleAutor el.pescado
  3. 3

    Bauen Sie gerade einen großen String[] und es Sortieren. Dann können Sie verwenden, binäre Suche, um die Position einer Zeichenfolge. Sie können auch eine Abfrage basierend auf Präfixen ohne viel Arbeit.

    Präfix look-up-Beispiel:

    Vergleichen Methode:

    private static int compare(String string, String prefix) {
    if (prefix.length()>string.length()) return Integer.MIN_VALUE;

    for (int i=0; i<prefix.length(); i++) {
        char s = string.charAt(i);
        char p = prefix.charAt(i);
        if (s!=p) {
            if (p<s) {
                //prefix is before string
                return -1;
            }
            //prefix is after string
            return 1;
        }
    }
    return 0;
}

    Findet ein vorkommen des Präfix im array und gibt es zurück Ort (MIN oder MAX sind meine nicht gefunden)

    private static int recursiveFind(String[] strings, String prefix, int start, int end) {
    if (start == end) {
        String lastValue = strings[start]; //start==end
        if (compare(lastValue,prefix)==0)
            return start; //start==end
        return Integer.MAX_VALUE;
    }

    int low = start;
    int high = end + 1; //zero indexed, so add one.
    int middle = low + ((high - low) /2);

    String middleValue = strings[middle];
    int comp = compare(middleValue,prefix);
    if (comp == Integer.MIN_VALUE) return comp;
    if (comp==0)
        return middle;
    if (comp>0)
        return recursiveFind(strings, prefix, middle + 1, end);
    return recursiveFind(strings, prefix, start, middle - 1);
}

    Bekommt ein String-array und Präfix, druckt vorkommen des Präfix im array

    private static boolean testPrefix(String[] strings, String prefix) {
    int i = recursiveFind(strings, prefix, 0, strings.length-1);
    if (i==Integer.MAX_VALUE || i==Integer.MIN_VALUE) {
        //not found
        return false;
    }
    //Found an occurrence, now search up and down for other occurrences
    int up = i+1;
    int down = i;
    while (down>=0) {
        String string = strings[down];
        if (compare(string,prefix)==0) {
            System.out.println(string);
        } else {
            break;
        }
        down--;
    }
    while (up<strings.length) {
        String string = strings[up];
        if (compare(string,prefix)==0) {
            System.out.println(string);
        } else {
            break;
        }
        up++;
    }
    return true;
}
    • Wörter aus dem Lexikon. Vertrauen Sie mir, ich brauche, um herauszufinden, ob ein Schlüssel ist Präfix eines Wortes in das Wörterbuch in O(Länge) Zeit. Etwas anderes gibt riesige Strafen. Mit einem array, wie finde ich heraus, dass ein Schlüssel ist Präfix eines Wortes?
    • Mit binären suchen, sollten Sie in der Lage sein zu finden Präfixe in O(log N), wobei N die Anzahl der Wörter im Wörterbuch. Ich ' ll fügen Sie einige code auf meine Antwort um ein Beispiel zu geben.
    • Mit dem oben angegebenen Algorithmus, dauerte es weniger als 1 Millisekunde auf meinem Handy zu finden, das die Existenz eines 3-Buchstaben-Präfix in einer 200000 Element string array.
    • Es fand auch über 1000 Strings, die mit einem 3-Zeichen-Präfix in ~5 Millisekunden.
    • Ironischerweise, auf meinem Handy ist dieser Ansatz als auch die Durchführung eines Trie Durchführung einer Präfix-look-up und schlägt (durch eine gute Marge) einen Trie über die Rückgabe von allen Saiten, die enthalten das Präfix.
    InformationsquelleAutor Justin
  4. 1

    Hier von einem halbwegs kompakten format, für die Speicherung eines trie auf der Festplatte. Ich werde angeben, die ihm durch seine (Wirk -) Deserialisierung Algorithmus. Initialisieren Sie einen Stapel, dessen erste Inhalte sind die root-node der trie. Lesen Sie die Zeichen nacheinander ein und interpretiert Sie wie folgt vor. Die Bedeutung der Buchstaben " A-Z "zuweisen eines neuen Knoten, machen es zu einem Kind des aktuellen top-of-stack, und drücken Sie die neu zugewiesene Knoten auf dem stack". Der Buchstabe gibt an, welche position das Kind sich befindet. Die Bedeutung von Raum "legen Sie das gültig-flag des Knotens auf der Oberseite des Stapels auf "true". Die Bedeutung von einem backspace (\b) ist "pop stack".

    Beispielsweise die Eingabe

    TREE \b\bIE \b\b\bOO \b\b\b

    gibt das Wort Liste

    TREE
TRIE
TOO

    . Auf Ihrem desktop, erstellen die versuche, welche Methode und dann serialisieren, indem Sie die folgenden rekursiven Algorithmus (pseudocode).

    serialize(node):
    if node is valid: put(' ')
    for letter in A-Z:
        if node has a child under letter:
            put(letter)
            serialize(child)
            put('\b')
    InformationsquelleAutor David Eisenstat
  5. 1

    Dies ist nicht eine Magische Kugel, aber wahrscheinlich können Sie verringern Ihre Laufzeit leicht durch tun eine große Speicherreservierung anstelle einer Reihe von kleinen.

    Sah ich eine ~10% speedup im test Beispielcode (C++, Java nicht, sorry), wenn ich einen "Knoten-pool" anstatt auf einzelne Zuordnungen:

    #include <string>
#include <fstream>

#define USE_NODE_POOL

#ifdef USE_NODE_POOL
struct Node;
Node *node_pool;
int node_pool_idx = 0;
#endif

struct Node {
    void insert(const std::string &s) { insert_helper(s, 0); }
    void insert_helper(const std::string &s, int idx) {
        if (idx >= s.length()) return;
        int char_idx = s[idx] - 'A';
        if (children[char_idx] == nullptr) {
#ifdef USE_NODE_POOL
            children[char_idx] = &node_pool[node_pool_idx++];
#else
            children[char_idx] = new Node();
#endif
        }
        children[char_idx]->insert_helper(s, idx + 1);
    }
    Node *children[26] = {};
};

int main() {
#ifdef USE_NODE_POOL
    node_pool = new Node[400000];
#endif
    Node n;
    std::ifstream fin("TWL06.txt");
    std::string word;
    while (fin >> word) n.insert(word);
}
    InformationsquelleAutor Nate Kohl
  6. 1

    Versucht, die prealloate Raum alle möglichen Kinder (256), haben eine riesige Menge an Platz verschwendet. Machen Sie Ihren cache Weinen. Speichern Sie diese Zeiger, um die Kinder in eine veränderbare Datenstruktur.

    Einigen versucht wird zu optimieren, indem er einen Knoten zum darstellen einer langen Kette, und brechen Sie diese Zeichenfolge nur, wenn nötig.

    InformationsquelleAutor DanielV
  7. 0

    Statt einer einfachen Datei können Sie eine Datenbank wie sqlite und eine verschachtelte Gruppe oder celko Baum zum speichern des trie-und Sie können auch bauen ein schneller und kürzer (weniger Knoten) versuchten mit einem ternary search trie.

    InformationsquelleAutor Gigamegs
  8. 0

    Ich weiß nicht, wie die Idee der Adressierung von Knoten, die durch den index im array, aber nur, weil es erfordert noch eine Ergänzung (index-Zeiger). Aber mit array vorbelegt Knoten Sie vielleicht etwas Zeit sparen für die Zuweisung und Initialisierung. Und Sie können auch sparen eine Menge Platz reservieren ersten 26 Indizes für Blattknoten. So werden Sie nicht brauchen, um zu reservieren und initialisieren 180000 Blatt-Knoten.

    Auch mit Indizes Sie werden in der Lage sein, um Lesen Sie den vorbereiteten Knoten-array von der Festplatte im Binärformat. Dieser ist um ein Vielfaches schneller. Aber ich bin mir nicht sicher, wie dies zu tun auf Ihrer Sprache. Ist das Java?

    Wenn Sie überprüft haben, dass Ihre Quelle das Vokabular ist sortiert, Sie können auch Zeit sparen, durch den Vergleich einige Präfix des aktuellen Strings mit der vorherigen. E. g. ersten 4 Zeichen. Wenn Sie gleich sind, können Sie beginnen, Ihre

    for(int level=0 ; level < - Taste.length() ; Ebene++) {

    Schleife von der 5-th-Ebene.

    InformationsquelleAutor Mikhail M
  9. 0

    Ist es Raum ineffizient oder Zeit ineffizient? Wenn Sie Rollen eine Ebene versuchten dann Raum können Teil des Problems sein, wenn es mit einem mobil-Gerät. Überprüfen Sie heraus patricia/radix versucht, vor allem, wenn Sie es als Präfix look-up-tool.

    Trie:
    http://en.wikipedia.org/wiki/Trie

    Patricia/Radix trie:
    http://en.wikipedia.org/wiki/Radix_tree

    Du nicht erwähnt, dass eine Sprache, aber hier sind zwei Implementierungen von Präfix versucht in Java.

    Regelmäßigen versuche:
    http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/Trie.java

    Patricia/Radix (Raum-effiziente) trie:
    http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/PatriciaTrie.java

    • Nein, wie ich bereits in der Frage, die Zeit ist das problem nicht der Raum. Muss es sein, die rund 40MB, das ist machbar. Ich habe schon alles umgesetzt - ich bin gerade auf der Suche, um ihn zu beschleunigen. Bitte schauen Sie auf die bearbeitete Frage.
    • Ich finde es erstaunlich, dass es dauert 10 Sekunden, um zu bauen ein trie aus 180k Wörter. Zum Beispiel; den Aufbau eines trie von 200k auf meinem lokalen PC (2.0 GHz Prozessor mit 1 GB Arbeitsspeicher) dauert 471ms und verbraucht 34MBs, Gebäude ein komprimierter trie aus den gleichen Daten nimmt 541ms und verbraucht 22MBs. Ich würde versuchen, eine open-source-version und sehen, ob Sie bessere Ergebnisse erzielen.
    • "10 Sekunden auf meinem Handy"
    • Ich verstehe aber die Leistung Ihres trie ist so viel größer, es ist überraschend. Ich werde führen Sie den gleichen code auf meinem HTC und wieder Einchecken.
    • Danke! Btw, hier meine versuche: pastebin.com/QkFisi09 Word-Liste: isc.ro/lists/twl06.zip bei mir läuft es auf diese IDE: play.google.com/store/apps/...
    • Du wirst glücklich sein zu wissen, meine Versuche führt etwa die gleichen sind dir auf meinem Handy. Es dauerte etwa 7 Sekunden zu laden Versuche mit 200K Elemente.

    InformationsquelleAutor Justin
Schreibe einen Kommentar