Prefix Suche in einem Radixbaum / patricia Trie

Question

Ich bin die Umsetzung derzeit eine Radix-Baum / patricia trie (was auch immer Sie es nennen wollen). Ich möchte es in einem Wörterbuch auf ein stark untermotorisiert Stück Hardware für Präfix Suche verwenden. Es sollte mehr oder weniger wie die automatische Vervollständigung arbeiten, mich. e. eine Liste von Worten zeigt, dass der eingegebene Präfix übereinstimmt.

Meine Implementierung basiert zu diesem Artikel , aber der Code darin doesn ‚t Präfix sucht umfassen, obwohl der Autor sagt:

  

[...] Sagen Sie alle Knoten auflisten möchten, die Tasten mit einem gemeinsamen Präfix „AB“ haben. Sie können eine Tiefensuche durchführen zu dieser Wurzel Starten, Stoppen, wenn Sie Kanten stoßen zurück.

Aber ich sehe nicht, wie das funktionieren soll. Zum Beispiel, wenn ich einen Radix-Baum aus diesen Worten bauen:

  

Krankheit
  imaginärer
  Phantasie
  vorstellen
  Nachahmung
  sofort
  sofort
  immense
  in

Ich werde genau das gleiche „beste Übereinstimmung“ für die Präfixe „i“ und „in“ so erhalten, dass es mir schwer scheint nur alle passenden Wörter zu sammeln, indem Sie den Baum aus, die am besten durchquert.

Darüber hinaus gibt es eine radix Baum-Implementierung in Java , die über ein implementiertes Präfixsuche hat in RadixTreeImpl.java . Dieser Code explizit überprüft alle Knoten (von einem bestimmten Knoten ausgehend) für ein Prefix-Match -. Es Bytes tatsächlich vergleicht

Kann mich jemand auf eine detaillierte Beschreibung zeigt eine Präfixsuche auf radix Bäumen bei der Umsetzung? Ist der Algorithmus in der Java-Implementierung der einzige Weg, verwendet es zu tun?

Answer 1

Denken Sie darüber nach, was Ihre Trie kodiert. An jedem Knoten Sie den Pfad, die Sie zu diesem Knoten führen, so in Ihrem Beispiel, starten Sie bei Λ (das ist eine Hauptstadt Lambda, das griechische Schrift saugt Art) der Wurzelknoten auf einen leeren String entspricht. Λ hat Kinder für jeden Buchstaben verwendet, so in Ihrem Datensatz, können Sie einen Zweig haben, für „i“.

• Λ
• Λ → "i"

Auf dem „i“ Knoten gibt es zwei Kinder, ein für „m“ und ein für „n“. Der nächste Brief ist "n", so dass Sie das nehmen,

• Λ → "i" → "n"

und da das einzige Wort, das "i" beginnt, "n" in Ihrem Datensatz ist "in", es gibt keine Kinder von "n". Das ist ein Spiel.

Nun wollen wir den Datensatz sagen, sondern „in“ zu haben, hatte „infindibulum“. (Was SF ich Referenzierung als eine Übung gelassen wird.) Sie noch an den „n“ Knoten die gleiche Weise erhalten würde, aber dann, wenn der nächste Buchstabe bekommen ist „q“, wissen Sie das Wort nicht erscheint in Ihren Daten überhaupt gesetzt, weil es kein „q“ Zweig. An diesem Punkt sagen Sie „in Ordnung, kein Spiel.“ (Vielleicht haben Sie dann starten Sie das Wort geben, vielleicht auch nicht, je nach Anwendung).

Aber wenn der nächste Buchstabe „f“ ist, können Sie weitermachen. Sie können Kurzschluss, dass mit ein wenig Handwerk, aber: wenn Sie einen Knoten erreichen, die einen einzigartigen Weg darstellt, können Sie die ganze Reihe aus diesem Knoten hängen. Wenn Sie zu diesem Knoten erhalten, wissen Sie, dass der Rest der Zeichenfolge muss sein „findibulum“, so dass Sie das Präfix verwendet haben, die gesamte Zeichenfolge übereinstimmen, und es zurück.

Wie Sie Sie verwenden? in einer Menge von nicht-UNIX-Befehlsinterpreter, wie die alten VAX DCL Sie einen eindeutigen Präfix eines Befehls verwenden könnten. So, das äquivalent von ls (1) war DIRECTORY, aber kein anderer Befehl begann mit DIR, so dass Sie DIR geben können, und das war so gut wie das ganze Wort zu tun. Wenn Sie nicht den richtigen Befehl erinnern konnte, könnten Sie geben Sie einfach ‚D‘, und drücken Sie (glaube ich) ESC; die DCL CLI zurückkehren würden Sie alle die Befehle, die mit D gestartet, die es extrem schnell durchsuchen können.

Answer 2

Es stellt sich die GNU-Erweiterungen für die Standardausgabe c ++ lib enthält eine Patricia-Trie-Implementierung. Es ist unter der richtlinienbasierten Datenstrukturen Erweiterung gefunden. Siehe http://gcc.gnu.org/onlinedocs/libstdc++/ext /pb_ds/trie_based_containers.html

Answer 3

Ein alternativer Algorithmus: Keep It Simple Stupid

Nur eine sortierte Liste Ihrer Keywords machen. Wenn Sie einen Präfix haben, binäre Suche zu finden, wo das Präfix in der Liste befinden würde. Alle Ihrer möglichen Vervollständigungen werden zu diesem Start-Index zu finden, bereit, an Ort und Stelle abgerufen werden.

Dieser Algorithmus wird nur 5% des Codes einer Patricia Trie erfordert und wird leicht zu pflegen, zu verstehen und zu aktualisieren. Es ist so gut wie sicher diese einfache Liste Suche als auch effizienter sein wird.

Der einzige Nachteil ist, wenn Sie große Anzahl von langen Keywords mit ähnlichen Präfixen haben, kann ein Trie einige Speicher sparen, da es nicht den vollen Präfix für jeden Eintrag zu halten braucht. In der Praxis, wenn Sie weniger als ein paar Millionen Worte haben, ist dies keine Einsparung, weil der Zeiger Overhead des Baumes dominieren wird. Diese Einsparungen sind für Anwendungen wie Datenbanken von DNA-Strings mit Millionen von Zeichen suchen, nicht Text Schlüsselwörter.

Answer 4

Eine weitere Alternative algo ist ein ternären Suchbaum (mehr Speicher effizient) https://github.com/varunpant/TernaryTree/tree/master/TernaryTree