Ich habe einen Tri-Tree geschrieben, der für die Implementierung von Hochgeschwindigkeitswörterbüchern in D-Sprache und Python verwendet werden kann

Was ist ein Versuchsbaum?

Kennen Sie die Datenstruktur namens Trie-Baum? Tri-Tree ist eine Datenstruktur, mit der Hochgeschwindigkeitswörterbücher implementiert werden können. Die Implementierung mit einer Datenstruktur namens LOUDS hat den Vorteil, dass der Baum mit sehr wenig Speicher dargestellt werden kann. Tri-Tree wird verwendet, um das japanische Wörterbuch im Speicher zu halten, beispielsweise bei der Kana-Kanji-Konvertierung (japanische Google-Eingabe usw.).

Der Tri-Tree hat eine solche Form. (Die Abbildung stammt aus Wikipedia)

Was es von anderen Bäumen unterscheidet, ist, dass die "Zweige" des Baumes beschriftet sind.

Wie kann ich das als Wörterbuch verwenden? Lassen Sie uns nach "in" suchen. Es ist einfach. Alles was Sie tun müssen, ist i-> n zu folgen. Sie können "5" als Suchergebnis abrufen. Lassen Sie uns nach "Gasthaus" suchen. Alles was Sie tun müssen, ist von der aktuellen "5" Position nach unten zu gehen. Als Ergebnis kann "9" abgerufen werden.

Merkmale des Tri-Baums

Kann mit hoher Geschwindigkeit suchen

Das Tolle an diesem Versuchsbaum ist, dass Sie sehr schnell suchen können. In einem Tri-Tree ist die Suchgeschwindigkeit proportional zur Größe des zu suchenden Schlüssels. Und es ist nicht proportional zur Größe des __ Baums! __ __

Angenommen, Sie implementieren ein japanisches Wörterbuch mit einem Tri-Tree. Die Suche nach dem 12-stelligen "Waraukado ni Fukukitaru" im japanischen Wörterbuch dauert etwa 4 (= 12/3) Mal so lange wie im 3-stelligen "Warau". Wenn Sie jedoch dasselbe Wort nachschlagen, unabhängig davon, ob es 100 Wörter oder 1 Million Wörter im Wörterbuch enthält, ändert sich die Suchgeschwindigkeit theoretisch nicht. Es ist wunderbar.

Reduzieren Sie verschwenderische Suchvorgänge

Wenn Sie nach einer Zeichenfolge suchen, die einen gemeinsamen Teil hat, können Sie unnötige Suchvorgänge reduzieren, indem Sie die Suche von der Mitte aus neu starten. Als ich beispielsweise früher nach "inn" gesucht habe, konnte ich die Suchergebnisse für "inn" schnell finden, indem ich die Suche vom Knoten "5" im Ergebnis der Suche nach "in" neu startete.

Implementierung durch LOUDS

Das Implementieren eines Tri-Tree, ohne mit Strukturen und Zeigern darüber nachzudenken, verbraucht viel Speicher. Das Gerät friert ein, wenn der Speicher zu voll ist, um hängen zu bleiben. Daher verwenden wir eine Datendarstellungsmethode namens LOUDS. Mit LOUDS kann ein Knoten nur durch 2 Bits dargestellt werden. Ein Baum mit 11 Knoten wie dem am Anfang gezeigten kann nur durch 23 Bits dargestellt werden und passt in eine lange Typvariable.

Ich möchte LOUDS hier erklären, aber da Erklärung der prägnanten Datenstruktur LOUDS sehr einfach zu verstehen war, werde ich es Ihnen geben. ..

Code

Der Code ist unten. Implementiert in D-Sprache bzw. Python. github.com/IshitaTakeshi/Louds-Trie Ich wollte viele Kommentare schreiben, daher denke ich, dass Sie dies verstehen können, indem Sie die Erklärung von LOUDS im obigen Link lesen und dann den Code lesen. Wenn Sie Fragen oder Bedenken haben, kommentieren oder teilen Sie uns dies bitte auf Twitter mit. Wir werden Ihnen dann antworten.

Boxed Edition

Es kann vom D-Sprachpaket-Management-System DUB verwaltet werden. DUB-Seite Quellcode