圧縮接尾辞配列ライブラリ csalibの圧縮率の高さは異常

計算機科学

圧縮接尾辞配列の第一人者、定兼先生が開発、公開してくださっているcsalibを試してみたのでメモ。

http://researchmap.jp/sada/csalib/


まずはgooglecodeからcsalibとdbwtを入手。解凍しmakeする。

$$ mkdir csalib/
$$ cd csalib/
$$ wget http://csalib.googlecode.com/file/csalib100810.zip
$$ unzip csalib100810.zip
$$ make
$$ cd ..

$$ mkdir dbwt/
$$ cd dbwt/
$$ wget http://csalib.googlecode.com/file/dbwt100730.zip
$$ make
$$ cd ..

このライブラリはdbwtでテキストをBurrows-Wheeler変換し、その後mkcsaでself-indexingするという二段構成になっている。
まず適当な大きさのテキストを用意しtest.txtとする。これをBurrows-Wheeler変換する。

$$ ./dbwt/dbwt test.txt

これでoutput.bwとoutput.lstという二つのファイルが出来る。
次にself-indexingをすることで圧縮接尾辞配列ができる。mkcsaは複数のindexingをサポートしているが、それぞれに共通の部分がある。まずはこれを生成する。

$$ ./csalib/mkcsa output -I

これでoutput.idxというファイルが出来る。
最後に好みの方式でindexingする。今回はマニュアルでオススメされているP4(ウェーブレット木を使う方法)を使ってみる。

$$ ./csalib/mkcsa output -P4

これでoutput.wtdができた。
あとはcsaというコマンドで動作テストが出来る(PizzaChili準拠のAPIも用意されている)。

$$ ./csalib/csa output.idx output.wtd
(中略)
key ...

あとは適当なキーワードを入力すると出現回数と、出現位置の前後のテキストが表示される。
手元にあった400M程度の地名データで試したところoutput.idxとoutput.wtdを併せて150Mくらいに圧縮された。元テキストの1/3の大きさになってしまい大変驚いた。普通のCSAだと元テキストと大体同じくらいのサイズになるので、これは凄いと思った。
(元テキストと同じって普通じゃね？と思った方もいるかもしれないので補足。CSAはテキストに前方一致検索できるようにインデックスが付加されたものなので、圧縮しないSAだとテキストサイズをNとしてNlogNの大きさのインデックスができる。よってテキストと併せてN+NlogNの大きさのデータになってしまう。)
マニュアルでオススメされていた手法選択オプションはどれもウェーブレット木を使っていたので、時代はウェーブレット木かもしれない。勉強しないと。ただウェーブレット木はデータとしては小さいけれど、実行時に構築に少し時間がかかっていたので、そこがネックかも。