概要
PythonでTRIE木を実装した
TRIE木を作成する上でデータ構造にLOUDSを使用している
TRIE木
- TRIE木とは、文字列の集合を順序付きの木構造で表したもの
- ノードとエッジから構成され、各ノードの位置とキー（検索文字列）が対応している
- ルートノードには空文字列が対応している
TRIE木の特徴
- 高速な辞書検索：木の大きさに関わらず定数時間で検索することができる
- メモリを節約：ノードにキーが格納されないため、複数のキーでノードを共有することができ、メモリを節約することができる
- 効率的なプレフィックス検索：複数のキーでノードを共有しているため、親ノード（プレフィックス）に紐づく子ノードの検索も効率的に行うことができる
TRIE木はその特徴から、かな漢字変換や自動補完などに使用されている
LOUDS
- LOUDS（level order unary degree sequence）とは、順序木表現の一つ、極めて小さいサイズで木構造を表現することができる
- 具体的にはノード数がN個の場合、その木構造は長さNのラベル配列と2N+1のbit配列で表現される
- ただし、作成したTreeから効率よく検索するために、補助的なデータ（完備辞書）が別途必要になる
完備辞書
- 完備辞書とは、簡潔データ構造において最も基本的なデータ構造
- 完備辞書を補助データとして用いることによって、定数時間での検索が可能になる
- 具体的にはrankとselectという操作を用いて、TRIE木の検索を行う
- rank():ビット列の先頭から位置 k までに、1 のビットがいくつあるか
- select():ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか
簡潔データ構造については、こちらのページで詳しく解説されている
実装
Pythonで以下を実装した（GitHub）
- trie.py：TRIE木
- constructor.py：ビット配列
- words.py：辞書データの作成・読み込み
- measure.py：メモリと検索時間の測定
- search_word.py：単語検索
- test.py：検索時間の測定
辞書データの作成
以下のように実行すると、TRIE木のノード番号と単語がカンマ区切りで書かれている辞書データが作成される
データはnltkのwordnetコーパスを使用した
後にテストデータをこの辞書データから作成する
from words import CreateWords
CreateWords("./data/origin/wordnet_words.csv")
単語検索
python search_word.py 辞書データPATH
上記のファイルを実行すると、単一の単語検索をすることができる
任意の単語を入力すると、以下のように、検索から得られたノード番号、単語の定義、プレフィックスが出力される
検索時間の測定
テストデータの作成
以下を実行すると、任意の単語数のテストデータを辞書データから作成できる
python words.py 辞書データPATH サンプル数1,サンプル数2,サンプル数3,…
複数のテストデータを作成したい場合は、データのサンプルサイズをカンマ区切りで指定
"Test data is created."と出力されればok。テストデータが./data/testに作成される
測定
以下のように、実行するとテストデータで任意の回数、テストを実行することができる
python test.py 辞書データPATH テストデータPATH テスト回数
"Test is done."と出力されればok。出力結果が./resultsに作成される
測定では、完全一致検索時間とプレフィックス検索時間を計測している
- 完全一致検索：trieクラスのsearch関数の実行時間の合計
- プレフィックス検索：trieクラスのget_blow_nodes関数の実行時間の合計
内部的には入力された単語に対して、trieクラスのsearch関数が実行され、TRIE木のノード番号を出力する
出力されたノード番号は辞書データのノード番号と照合され、一致していれば検索件数を+1し、正確に検索ができているかどうか確認している。プレフィックス検索も同様
出力結果
- 完全一致検索：単語の検索にかかった合計時間
- 検索結果：辞書データのノード番号と一致した件数
- プレフィックス検索：検索単語に紐づくプレフィックスをすべて検索するまでにかかった合計時間
- プレフィックス検索（１件当たり）：検索単語に紐づくプレフィックス１件当たりの検索時間
- メモリ使用量
- bit_array：bit配列のメモリ使用量
- labels：ラベル配列のメモリ使用量
- rank：rankのメモリ使用量
- select：selectのメモリ使用量