Überblick

TRIE-Baum in Python implementiert LOUDS wird für die Datenstruktur beim Erstellen des TRIE-Baums verwendet

TRIE Baum

Ein TRIE-Baum ist ein Satz von Zeichenfolgen, die durch eine geordnete Baumstruktur dargestellt werden.
Bestehend aus Knoten und Kanten, entsprechen Position und Schlüssel jedes Knotens (Suchzeichenfolge)
Eine leere Zeichenfolge entspricht dem Wurzelknoten

Merkmale des TRIE-Baums

Schnelle Wörterbuchsuche: Sie können unabhängig von der Größe des Baums zu einer festgelegten Zeit suchen.
Speicher speichern: Da der Schlüssel nicht im Knoten gespeichert ist, kann der Knoten von mehreren Schlüsseln gemeinsam genutzt werden, wodurch Speicherplatz gespart wird.
Effiziente Präfixsuche: Da der Knoten von mehreren Schlüsseln gemeinsam genutzt wird, ist es möglich, effizient nach untergeordneten Knoten zu suchen, die dem übergeordneten Knoten zugeordnet sind (Präfix).

Aufgrund ihrer Eigenschaften werden TRIE-Bäume für die Kana-Kanji-Konvertierung und die automatische Vervollständigung verwendet.

LOUDS --LOUDS (Level Order Unary Degree Sequence) ist einer der Ordnungsbaumausdrücke und kann die Baumstruktur mit einer extrem kleinen Größe ausdrücken.

Insbesondere wenn die Anzahl der Knoten N ist, wird die Baumstruktur durch ein Beschriftungsarray der Länge N und ein Bitarray von 2N + 1 dargestellt. ―― Für eine effiziente Suche im erstellten Baum sind jedoch Zusatzdaten (vollständiges Wörterbuch) separat erforderlich.

Komplettes Wörterbuch

Ein vollständiges Wörterbuch ist die grundlegendste Datenstruktur in einer übersichtlichen Datenstruktur.
Durch die Verwendung des vollständigen Wörterbuchs als Hilfsdaten ist es möglich, in einer festen Zeit zu suchen.
Suchen Sie speziell den TRIE-Baum anhand des Operationsrangs und wählen Sie ihn aus. --rank (): Wie viele 1 Bits gibt es vom Anfang der Bitfolge bis zur Position k? --select (): Wo befindet sich die Position neben dem n-ten 1-Bit, wenn sie vom Anfang der Bitfolge aus betrachtet wird?
Die übersichtliche Datenstruktur wird auf dieser Seite ausführlich erläutert

Implementierung

Implementierte Folgendes in Python (GitHub)

--trie.py: TRIE-Baum --builder.py: Bit-Array --words.py: Wörterbuchdaten erstellen / lesen --measure.py: Messen Sie den Speicher und die Suchzeit --search_word.py: Wortsuche --test.py: Messung der Suchzeit

Wörterbuchdaten erstellen

Bei der folgenden Ausführung werden Wörterbuchdaten erstellt, in die die Knotennummern und Wörter des TRIE-Baums durch Kommas getrennt geschrieben werden. Die Daten verwendeten den Wordnet-Korpus von nltk Später werden Testdaten aus diesen Wörterbuchdaten erstellt.

from words import CreateWords
CreateWords("./data/origin/wordnet_words.csv")

Wortsuche

 python search_word.py Wörterbuchdaten PFAD

Sie können eine einzelne Wortsuche durchführen, indem Sie die obige Datei ausführen Wenn Sie ein Wort eingeben, werden die Knotennummer, die Wortdefinition und das Präfix, die bei der Suche erhalten wurden, wie unten gezeigt ausgegeben.

Suchzeitmessung

Testdaten erstellen

Sie können Testdaten für eine beliebige Anzahl von Wörtern aus Wörterbuchdaten erstellen, indem Sie Folgendes ausführen

 python words.py Wörterbuchdaten PFAD Anzahl der Proben 1, Anzahl der Proben 2, Anzahl der Proben 3,…

Wenn Sie mehrere Testdaten erstellen möchten, geben Sie die Stichprobengröße der durch Kommas getrennten Daten an. Wenn "Testdaten erstellt werden" ausgegeben wird, ist dies in Ordnung. Testdaten werden in ./data/test erstellt

Messung

Bei der Ausführung kann der Test mit den unten gezeigten Testdaten beliebig oft ausgeführt werden.

 python test.py Wörterbuchdaten PFAD Testdaten PFAD Testanzahl

Wenn "Test ist abgeschlossen" ausgegeben wird, ist dies in Ordnung. Ausgabeergebnisse werden in ./results erstellt

Bei der Messung werden die genaue Übereinstimmungssuchzeit und die Präfixsuchzeit gemessen.

Genaue Übereinstimmungssuche: Gesamtausführungszeit der Suchfunktion der Trie-Klasse --Prefix-Suche: Gesamtausführungszeit der Funktion get_blow_nodes der Klasse trie

Intern wird die Suchfunktion der Trie-Klasse für das Eingabewort ausgeführt und die Knotennummer des TRIE-Baums ausgegeben. Die Ausgabeknotennummer wird mit der Knotennummer in den Wörterbuchdaten sortiert. Wenn sie übereinstimmen, wird die Anzahl der Suchvorgänge um 1 erhöht und es wird bestätigt, ob die Suche korrekt ist. Gleiches gilt für die Präfixsuche

Ausgabeergebnis

Genaue Übereinstimmungssuche: Gesamtzeit für die Suche nach einem Wort
Suchergebnisse: Anzahl der Datensätze, die mit der Knotennummer der Wörterbuchdaten übereinstimmen --Prefix-Suche: Gesamtzeit für die Suche nach allen mit dem Suchwort verknüpften Präfixen
Präfixsuche (pro Element): Suchzeit pro Präfix, das dem Suchwort zugeordnet ist
Speichernutzung --bit_array: Speichernutzung des Bit-Arrays --labels: Speichernutzung des Label-Arrays --rank: Rang Speichernutzung --select: Wählen Sie die Speichernutzung

TRIE-Baumimplementierung mit Python und LOUDS