Trie (Präfix-Baum) in Python

StackOverflow https://stackoverflow.com/questions/960963

  •  12-09-2019
  •  | 
  •  

Frage

Ich weiß nicht, ob dies der richtige Ort ist, um Algorithmen zu fragen. Aber mal sehen, ob ich irgendwelche Antworten zu bekommen ...:)

Wenn etwas unklar ist, bin ich sehr glücklich, Dinge zu klären.

I implementiert nur ein Trie in Python. Allerdings schien eine etwas komplizierter als es sein (als jemand, Einfachheit liebt) zu sein. Vielleicht hat jemand ein ähnliches Problem gehabt?

Mein Ziel war die Anzahl der Knoten zu minimieren, indem den größten gemeinsamen Präfix eines Unter trie in seiner Wurzel zu speichern. Zum Beispiel, wenn wir die Worte Stackoverflow , stackbase und stackbased hatte, dann würde der Baum etwa wie folgt aussehen: 

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

Beachten Sie, dass man immer noch an den Kanten denken kann einen Charakter (die ersten der untergeordneten Knoten).

Suchen query ist einfach zu implementieren. Einfügen ist nicht schwer, aber etwas komplexer als ich will ..: (

war meine Idee, die Tasten nacheinander (ausgehend von einem leeren Trie) einzufügen, indem man zunächst für die Suche zu-eingefügten Schlüssel k ( Suchen (k)), und dann Umstellen / die Knoten lokal an der Stelle, wo Aufteilung der Fund-Prozedur stoppt. Es entpuppt 4 Fälle sein: (Es sei k den Schlüssel wir einfügen wollen, und k‘der Schlüssel des Knotens, wo die Suche beendet)

  1. k ist identisch mit k '
  2. k ist ein "richtiger" Präfix von k '
  3. k‘ist ein "richtiger" Präfix von k
  4. k und k‘teilen einigen gemeinsamen Präfix, aber keiner der Fälle (1), (2) oder (3) auftreten.

Es scheint, dass jeder der Fälle ist einzigartig und somit verschiedene Modifikationen der Trie bedeuten. ABER: ist es wirklich so kompliziert? Bin ich etwas fehlt? Gibt es einen besseren Ansatz?

Danke:)

War es hilfreich?

Lösung

Auf einen Blick, es klingt wie Sie eine Patricia Trie implementiert haben . Dieser Ansatz wird auch Pfad Kompression in einem Teil der Literatur genannt. Es sollte Kopien dieses Papier, das nicht hinter dem ACM paywall sind, die einen Einfügungsalgorithmus umfassen wird.

Es gibt auch eine andere Komprimierungsmethode, die Sie wollen, betrachten können: Komprimierung. Die Idee hinter Pfad Kompression ist Saiten einzelnen Kind-Knoten mit einem einzigen Superknoten zu ersetzen, die ein „überspringen“ count hat. Die Idee hinter Komprimierung ist voll oder fast voll Teilbäume mit einem Super-Knoten mit einem „Grad“ count zu ersetzen, sagt, wie viele Stellen des Schlüssels der Knoten decodiert. Es gibt auch einen dritten Ansatz Breite Kompression genannt, aber ich fürchte mich mein Gedächtnis nicht und ich konnte keine Beschreibung davon mit schnellen googeln finden.

Stufe Kompression kann den durchschnittlichen Pfad erheblich verkürzen, aber das Einsetzen und Entfernen Algorithmen bekommen ziemlich kompliziert, da sie den Trie-Knoten als ähnlich dynamische Arrays verwalten müssen. Für die richtigen Datensätze Ebene komprimiert Bäume können schnell sein . Von dem, was ich mich erinnere, sie der 2. schnellste Ansatz zur Speicherung von IP-Routing-Tabellen sind, die schnellste ist eine Art von Hash-trie.

Andere Tipps

Ich habe nichts falsch mit Ihrem Ansatz sehen. Wenn Sie sich für eine Spitze Lösung suchen, vielleicht die getroffenen Maßnahmen für den Fall 4 sind tatsächlich denkbar, dass die ersten drei Fälle, dh den gemeinsamen Präfix finden Sie den Knoten mit diesem Gedanken k und k' und wieder aufzubauen. Wenn es passiert, dass die Schlüssel Präfixe Miteinandersein waren, wird die resultierende trie noch richtig sein, nur, dass die Umsetzung ein bisschen mehr Arbeit als es mußte wirklich. aber dann wieder, ohne Code zu betrachten, es ist schwer zu sagen, ob dies in Ihrem Fall funktioniert.

Etwas von einer Tangente, aber wenn man super besorgt über die Anzahl der Knoten in Ihrem Trie ist, dass Sie das Wort zu verbinden Suffixe aussehen. Ich würde einen Blick auf die DAWG (Directed Azyklisches Wortgraph) Idee: http: //en.wikipedia .org / wiki / Directed_acyclic_word_graph

Der Nachteil davon ist, dass sie nicht sehr dynamisch sind und die Schaffung von ihnen kann schwierig sein. Aber, wenn Ihr Wörterbuch statisch ist, können sie extrem kompakte Bauform sein.

Ich habe eine Frage bezüglich Ihrer Implementierung. Was ist das Niveau der Granularität, die Sie sich entscheiden, Ihre Saiten auf aufzuspalten den Präfix-Baum zu machen. Sie könnten Stapel teilen entweder als s, t, a, c, k oder st, ta, ac, ck und viele andere ngrams davon. Die meisten Präfixbaums Implementierungen berücksichtigen ein Alphabet für die Sprache, auf der Grundlage dieses Alphabet, können Sie die Spaltung zu tun.

Wenn Sie wurden ein Präfix-Baum-Implementierung für Python bauen dann würde Ihre Alphabete Dinge wie def,:, wenn, sonst ... etc

das richtige Alphabets Wahl macht einen großen Unterschied bei der effizienten Präfix Bäume zu bauen. Wie für Ihre Antworten, könnten Sie für PERL-Pakete auf CPAN suchen, die längste gemeinsame Teilzeichen Berechnung tun trie der Verwendung. Sie können dort etwas Glück haben als die meisten ihrer Umsetzung ziemlich robust ist.

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

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top