TRIE-Baum in Python implementiert LOUDS wird für die Datenstruktur beim Erstellen des TRIE-Baums verwendet
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.
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
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")
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.
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
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.
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
Recommended Posts