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