kzkの日記: trie木 1
日記 by
kzk
--- 実行結果 ---
[]
[a]
[i]
[u]
[e]
[o]
[j]
[i]
[n]
[k]
[o]
[u]
[t]
[u]
string = aiko
string = iko
string = ko
string = o
search aiko = true
string = aijo
string = ijo
string = jo
string = o
search aijo = false
anthyのsrc-diclibで使われているデータ構造。
anthyのtrie (スコア:1)
bitごとの二分木になっていることと、複数の分岐を一つのノードに格納することが素のtrieと異なる点です。(たとえば、0001と0000を格納する場合、prefixの000は一つのノードに格納されます)
anthyで使った理由は (1)検索がそこそこ速く、速度が安定していること。 (2)ツリーの中で要素の順序が保存されていること。 (3)最長マッチの検索ができること。などがあったと記憶しています。