LOUDSトライのライブラリの性能を比較してみた

LOUDSは木構造を非常に小さなデータサイズで表現することができる簡潔データ構造の一種。とくに自然言語処理ではトライ木という木構造が重要で形態素解析や日本語入力(IME)など多くの場面で利用されている。
トライ木としてはdouble arrayが有名。LOUDSはdouble arrayより速度で劣る反面、データサイズを非常に小さく抑えることが可能である。このため近年、大規模データを扱うためのデータ構造として注目されている。
LOUDSを用いたトライ木には優れた実装がいくつかある。なかでも有名なものとして@s5yata氏によるmarisa-trieと@hillbig氏によるux-trieがある(ux-trieのクローンであるrx-trieはGoogleIMEで利用されている)。
今回はこれらのライブラリと、参考までに私の作ったerika-trieを使ってみて簡単に性能比較をしてみた。


評価には

http://jusyo.jp/

で公開されている住所データ(118073件)を用いた。

まずデータサイズは以下のとおり。

元データ		: 3,872,813 byte
marisa-trie	: 537,224 byte
ux-trie		: 697,028 byte
erika-trie		: 1,263,925 byte

というわけでmarisa-trieが最もデータサイズが小さくなった。LOUDSとしては最もサイズの大きいerika-trieでも元データの1/3まで縮小されている。LOUDSすごい。


つぎに検索速度。トライ木の基本的な操作はcommon-prefix-searchとpredictive-searchの2つ。それぞれについて各ライブラリの付属のツールを使って実行時間をtimeコマンドで計測した(小数点2桁目を四捨五入)。また入力クエリとして元データをそのまま与えた。ちなみにux-trieのuxツールは検索時にすべての操作を一括して実行する仕様なので比較対象となる操作以外をコメントアウトして実行した。

[common-prefix-search]
marisa-trie	: 1.0sec
ux-trie		: 4.9sec
erika-trie		: 1.6sec

[predictive-search]
marisa-trie	: 1.0sec
ux-trie		: 4.3sec
erika-trie		: 1.7sec

検索速度に関してもmarisa-trieがもっとも優れていた。またux-trieはデータサイズではmarisa-trieに匹敵する性能があったが検索速度はイマイチだった。


以上の結果からデータサイズ、検索速度両面でmarisa-trieが大勝利であることがわかった。marisa-trie恐るべし・・・。

比較に使ったライブラリ:
http://code.google.com/p/marisa-trie/
http://code.google.com/p/ux-trie/
http://code.google.com/p/erika-trie/