http://linux.thai.net/~thep/datrie/datrie.html
のはなし。
Trieって何・・・
決定性有限オートマトン(DFA)の一種で、文字列の検索とかに使うらしい。例えばある単語が辞書にあるかどうかを検索する、とかそんな感じでしょうか。長所としては、検索の早さがデータベースの大きさに依存せず、キーの長さのオーダーで実行できるということらしい*1。ハッシュと同じくらい早い！とか。図とかは上のURLに書いてあるのでそっちを見たほうが直感的には分かりやすい。
実装
一番単純な実装としては、2次元行列で実装すること。例えば行を状態、列を遷移ラベルとすることで実装できる。図にするとこんな感じ？(見にくい・・・)
trie
１─２┬─３
ｃ ａ│ ｒ
└─４
ｔ配列
a r t 1 2 * * 2 * 3 4 3 * * * 4 * * *
ただ、2次元配列にすると配列がスカスカになってしまって効率が悪い。かといって2次元配列をリンクリストで実装するのはちょっと速度の点で難があるので、色々と効率化の方法が考えられた・・・ということのようです。
Tripple-Array Trie
3つの配列を使って効率化させようっていう手法。
- base
- inedxはtrieのノードに対応する。配列の値は、next/checkに対するオフセット。
- next
- 遷移ベクトル*2を保持する配列。
- check
- nextの各要素に対して、その所有者を保持する配列。元々のbaseとcheckの値が違っていたら、それは辞書にない単語ということになる(多分)。
つまり
check[base[s] + c] = s next[base[s] + c] = t
という関係。
確かにこの方法だと2次元配列よりは効率的にメモリーを使えそうではあります。
キーの挿入について。ある状態sに対して、新しい遷移tを挿入するとき、next[base[s]+t]が空いてればラッキーだけど、空いてなければ遷移ベクトルごと移動する必要がある。つまりnext[base[s]+c]=sであるような全てのcに対して、nextとcheckの移動をさせないといけない。これはめんどくさいなあ・・・
Double-Array Trie
いよいよ本題。tripple-array trieは効率的だけど、1つのファイルに保存するのには向いてない*3。そのため、base+nextを一つにまとめてbaseとして、baseとcheckの2つの配列で実装するようにした。つまりこういう関係。
check[base[s] + c] = s base[s] + c = t
・・・まあ、たしかにまとめても問題なさそうな気はする。
その後、分岐しない文字列をまとめるとか挿入/削除の話とかあるけど、その辺は気が向いたら。
