2012/08/25

LOUDSTrie実装してみた

よく考えたらblogに載せてなかった(TwitterやGoogle+でつぶやいて載せた気になってた・・)ので、改めて。

LOUDSはLevel-order Unary Degree Sequenceの略。詳しくは書籍「日本語入力を支える技術」(amazon)や下記サイトを参照してください。

要は木構造を01のビット列で表そうというデータ構造で、遅いけどかなり小さく圧縮できる。ただでさえJavaではオブジェクトがメモリを食う(何もフィールド無くてもポインタ2個分消費する)ので、木構造がビット列で表現できれば、絶大なサイズ削減効果があります。

既に構築済みのトライからLOUDS Trieを構築するのは結構簡単で、幅優先でトライを辿り、子の数だけ1を追加、最後に0を追加というのを繰り返すだけ。trie4jではこんな感じに実装してます。

https://github.com/takawitter/trie4j/blob/master/trie4j/src/org/trie4j/louds/LOUDSTrie.java#L53

構築済みのトライを辿るには、ルートから、

  1. 左端の子ノードの位置を求める(簡潔ビット配列のselect0操作)
  2. 右端の子ノードの位置を求める(簡潔ビット配列のselect0操作)
  3. 左端の子ノードのIDを求める(簡潔ビット配列のrank1操作)
  4. 子ノードから適切なラベルを持つものを探す
  5. 子ノードのTAIL配列(2番目以降のラベル文字列)を得て検索文字列と比較

という感じで子ノードの検索、文字列比較を行っていく。これを高速に行うのが結構面倒で、select0やrank1をどう高速化するか、ビット配列の実装が肝になります。

trie4jでは、select0、rank1共にキャッシュを作って高速化してます。また、上記2の処理専用にnext0という操作を簡潔ビット配列クラス(SuccinctBitVector)に追加してます。そこらへんの工夫により、127万件の要素を照合するのに500ms程度と、まずまずの速度を確保してます(もちろんC++で実装されたライブラリに比べれば遅いだろうけど)。

trie4jの実装はこちら https://github.com/takawitter/trie4jからどうぞ。BuildHive使って、最新のスナップショットtrie4j-SNAPSHOT.jarも常にダウンロードできる状態にしてあります。

コメントを投稿