ウェーブレット行列とウェーブレット木の性能比較をしてみた
FM-Indexで用いる簡潔データ列としてウェーブレット行列とウェーブレット木のどちらがいけてるのかを調べてみた。
データは以下の実験で用いた住所データを使った。
データサイズは
ウェーブレット行列: 5, 693, 256 byte ウェーブレット木: 5, 709, 560 byte
となった。ビット列のセパレータ数が少ないぶんウェーブレット行列のほうがやや小さい。
速度についてはsample/search_fm_indexを用いてインデックスした住所データ(118,073件)をシャッフルしたものをクエリとして全件検索にかかる時間を測った。
$$ time sample/search_fm_index var/zenkoku.key.fm.wm m y < var/zenkoku.shuf real 0m22.376s user 0m22.328s sys 0m0.045s $$ time sample/search_fm_index var/zenkoku.key.fm.wt t y < var/zenkoku.shuf real 0m25.228s user 0m25.147s sys 0m0.067s
というわけでウェーブレット行列のほうが速い様子。
以上。
データサイズ・速度・実装の簡単さ、あらゆる点でウェーブレット行列のほうがよさそう。
