Trie (Prefixbaum) in Python

Question

Ich weiß nicht, ob dies der richtige Ort ist, um nach Algorithmen zu fragen. Mal sehen, ob ich Antworten bekomme ... :)

Wenn etwas unklar ist, erkläre ich gerne die Dinge.

Ich habe gerade einen Trie in Python implementiert. Allerdings schien ein Teil etwas komplizierter zu sein als er sollte (als jemand, der Einfachheit liebt). Vielleicht hatte jemand ein ähnliches Problem?

Mein Ziel war es, die Anzahl der Knoten zu minimieren, indem ich das größte gemeinsame Präfix eines Unter-Tries in seiner Wurzel speichere. Zum Beispiel, wenn wir die Wörter stackoverflow, stackbase und stackbased hatten, würde der Baum ungefähr so aussehen:

              [s]tack
[o]verflow ______/ \_______ [b]ase
                                  \___ [d]

Beachten Sie, dass man immer noch davon ausgehen kann, dass die Kanten ein Zeichen haben (das erste Zeichen des Kindknotens).

Find-Abfrage ist einfach zu implementieren. Einfügen ist nicht schwer, aber etwas komplexer als ich möchte.. :(

Meine Idee war es, die Schlüssel nacheinander ein zu fügen (ausgehend von einem leeren Trie), indem ich zuerst nach dem einzufügenden Schlüssel k suchte (Find(k)), und dann die Knoten lokal an der Stelle umgruppierte/aufteilte, an der das Suchverfahren endet. Es ergeben sich 4 Fälle: (Nehmen Sie k als den Schlüssel, den wir einfügen möchten, und k' als den Schlüssel des Knotens, an dem die Suche endete)

1. k ist identisch mit k'
2. k ist ein "richtiges" Präfix von k'
3. k' ist ein "richtiges" Präfix von k
4. k und k' haben ein gemeinsames Präfix, aber keiner der Fälle (1), (2) oder (3) tritt auf.

Es scheint, dass jeder der Fälle einzigartig ist und daher unterschiedliche Modifikationen des Tries impliziert. ABER: Ist es wirklich so komplex? Fehlt mir etwas? Gibt es einen besseren Ansatz?

Danke :)

Answer 1

Auf den ersten Blick klingt es so, als hätten Sie eine Patricia Trie implementiert. Dieser Ansatz wird in einigen der Literatur auch als Pfadkompression bezeichnet. Es sollten Kopien dieses Papers vorhanden sein, die nicht hinter der ACM-Paywall liegen und einen Einfügealgorithmus enthalten.

Es gibt auch eine andere Kompressionsmethode, die Sie sich ansehen sollten: Level-Kompression. Die Idee hinter der Pfadkompression besteht darin, Zeichenfolgen von einzelnen Kindknoten durch einen einzelnen Superknoten mit einer "Überspringen"-Zählung zu ersetzen. Die Idee hinter der Level-Kompression besteht darin, volle oder nahezu volle Teilbäume durch einen Superknoten mit einer "Grad"-Zählung zu ersetzen, die angibt, wie viele Stellen des Schlüssels der Knoten entschlüsselt. Es gibt auch einen 3. Ansatz namens Breitenkompression, aber ich befürchte, dass mein Gedächtnis mich im Stich lässt und ich keine Beschreibung davon mit einer schnellen Google-Suche finden konnte.

Die Level-Kompression kann den durchschnittlichen Pfad erheblich verkürzen, aber die Einfüge- und Entfernalgorithm...

Answer 2

Ich sehe nichts Falsches an Ihrem Ansatz. Wenn Sie nach einer Spike-Lösung suchen, ist es vielleicht tatsächlich möglich, die Aktion, die im Fall 4 durchgeführt wurde, auch für die ersten drei Fälle durchzuführen, also den gemeinsamen Präfix von k und k' zu finden und den Knoten entsprechend neu aufzubauen. Wenn es sich herausstellt, dass die Schlüssel Präfixe voneinander waren, wird der resultierende Trie immer noch korrekt sein, nur die Implementierung hat etwas mehr Arbeit geleistet, als sie wirklich musste. Aber dann wiederum, ohne jeglichen Code zu haben, ist es schwer zu sagen, ob dies in Ihrem Fall funktioniert.

Answer 3

Ein wenig abseits, aber wenn Sie sich sehr um die Anzahl der Knoten in Ihrem Trie sorgen, können Sie auch Ihre Wortendungen zusammenfügen. Ich würde mir die DAWG (Directed Acyclic Word Graph) Idee ansehen: http://en.wikipedia.org/wiki/Directed_acyclic_word_graph

Der Nachteil dabei ist, dass sie nicht sehr dynamisch sind und ihre Erstellung schwierig sein kann. Aber wenn Ihr Wörterbuch statisch ist, können sie super kompakt sein.

Answer 4

Ich habe eine Frage zu Ihrer Umsetzung. Mit welcher Granularität entscheiden Sie sich, Ihre Zeichenfolgen zu teilen, um den Präfixbaum zu erstellen? Sie könnten "stack" als s,t,a,c,k oder st,ta,ac,ck und viele andere N-Gramme davon aufteilen. Die meisten Präfixbaum-Implementierungen berücksichtigen ein Alphabet für die Sprache, basierend auf diesem Alphabet erfolgt die Aufteilung.

Wenn Sie eine Präfixbaum-Implementierung für Python erstellen würden, wären Ihre Alphabete Dinge wie def, :, if, else... usw.

Die richtige Wahl des Alphabets macht einen großen Unterschied beim Bau effizienter Präfixbäume. Für Antworten könnten Sie nach PERL-Paketen auf CPAN suchen, die die Berechnung des längsten gemeinsamen Teilstrings mit Hilfe von Tries durchführen. Dort haben Sie möglicherweise Glück, da die meisten Implementierungen dort ziemlich robust sind.

Answer 5

Schauen Sie sich an: Judy-Arrays und die Python-Schnittstelle unter http://www.dalkescientific.com/Python/PyJudy.html