Double Array Trie

C/C++ gail

SEQUITURがとりあえず動くようになったので、次はDouble Array Trieを実装しようと思います。
Double Array TrieといえばDartsなどが有名ですが、Common Prefix Searchを高速に実行できるデータ構造らしいです。MeCabとかChaSenとかで使われてます。

辞書なし形態素解析では、まず文章中に反復して現れる文字列を単語としての確実度にしたがってSegment1, Segment2, Segment3と分類して辞書に登録します(これにSEQUITURを使うつもり)。
この辞書を使って形態素解析する時にはSegment1からSegment3まで順番に３回走査していきます。ここでDouble Array Trieを使おうということです。

とりあえず、このデータ構造について勉強しなければ。ざっとDouble Array Trieの解説を読んだけどぜんぜんアルゴリズムがつかめないorz