2012/08/25

最新の各種トライ速度比較

trie4jの最新の実装で、Wikipedia日本語タイトル127万件を格納する速度(build)、全件を照合する速度(contains)、消費サイズ(size)を測ってみました。

クラスbuild(ms)contains(ms)size(MB)
java.util.HashSet417453160.4
java.util.TreeSet402261160.2
PatriciaTrie442244104.6
TailPatriciaTrie(SuffixTrieTail)1,220271100.8
TailPatriciaTrie(ConcatTail)51724186.0
MultilayerPatriciaTrie70438691.8
MultilayerPatriciaTrie(packed)2,82286682.9
DoubleArray47110648.5
TailDoubleArray(SuffixTrieTail)3,07817537.3
TailDoubleArray(ConcatTail)2,59715742.0
LOUDSTrie(SuffixTrieTail)77750818.1
LOUDSTrie(ConcatTail)23448322.9
  • 補足1 - 今回からbuild, contains共に正味の速度を測るようにした(前回まではWikipediaアーカイブからの要素取得も入っていた)ので、HashSetも前回に比べると速くなっている様に見えている。
  • 補足2 - TailPatriciaTrie(suffixTrieTail)のサイズが大きいのは、SuffixTrieTailBuilderのトライが消費している分がでかい(約23MB)。TailPatriciaTrieは要素追加に対応するので、SuffixTrieTailBuilderもトライを保持しておく必要がある。
  • 補足3 - MultilayerPatriciaTrie(packed)は、ラベルを2層目のトライに追い出した状態。追い出しに時間がかかる(2秒超)が、サイズは10MB弱小さくなる。但し以降要素の追加はできない。また、DoubleArray以降は構築に別のトライを必要とし(今回PatriciaTrieを使用)、構築後は要素の追加はできない(未実装)。
  • 補足4 - DoubleArrayやLOUDSTrieで構築後の要素追加を実装する方法がないわけではないが、実用的な速度で追加するのはかなり難しそう。特にWikipedia級のデータになると1要素ずつ何万件もずらすような操作が発生してしまい、性能が出ない。
  • 補足5 - DoubleArrayの速度が劇的に改善してるのは、文字へのコード採番方式を変更したため。今までHashMapを使っていたが、TreeSet(総数カウント、列挙用)とchar[Character.MAX_VALUE](コード変換テーブル)の2つに置き換えた。

意外とHashSetとTreeSetはがんばってるんだなという印象。Trieの利点であるcommonPrefixSearchやpredictiveSearchは使えないけど。あとメモリ消費はやっぱりでかい。あと、HashSetの方が速いと思ってたんだけど、意外にTreeSetの方が速かった。メモリ消費もこの2つでは変わらない。

MultilayerPatriciaTrieは結構実装がんばってるんだけど、packしない前(要素追加可能)はTailPatriciaTrie(concatTail)に負けてるし、pack後(要素追加不可)はDoubleArray, LOUDSTrieにぼろ負け。結構トリッキーな実装してるし、実装ほんとに苦労したから残念なんだけど、現状存在意義無さそう。experimental状態(src.kitchensink)にしようかな。

あとTailDoubleArrayが遅いのは、DoubleArrayと比較して、空き要素の検索に時間がかかるようになるため。DoubleArrayだと1文字だけのラベル、子供1つだけというノードが大量に存在し、それがbase/checkの隙間を埋めてくれる。一方TailDoubleArrayはラベルをTAIL配列に追い出すことによってそういうノードがなくなるため、空きノードの検索対象が増え、速度が遅くなる。

今のところ、

  • 要素動的追加必須 -> TailPatriciaTrie(ConcatTail)
  • 検索速度重視 -> DoubleArray
  • サイズ重視 -> LOUDSTrie(SuffixTrieTail)
と使い分けるのが良さそうです。

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も常にダウンロードできる状態にしてあります。