CSAを使った全文検索ライブラリtsubomiを公開してみる
しばらく前から作っていた全文検索ライブラリtsubomiを公開しておく。
本ライブラリは接尾辞配列(Suffix Array)というアルゴリズムを使っていて、入力として与えたキーワードを含む行をテキストデータから探して、その行と出現位置を取得できる。さらに圧縮接尾辞配列(Compressed Suffix Array)による圧縮もサポートしているのでインデックスサイズを小さく抑えることができる。
本ライブラリは検索のためのAPIのほかに、インデックス作成、圧縮、検索を行うツールが付属している。ツールを使うだけでも、ある程度のことができる。
以下、簡単に紹介。
tsubomiはGoogleCodeでコードを管理している。詳細は下記URLを参照。
コード管理にはsubversionを使っているので
$$ svn checkout http://tsubomi.googlecode.com/svn/trunk/ tsubomi
としてコードを取得できる。なんらかの事情でsubversionが使えない場合は
$$ mkdir tsubomi $$ cd tsubomi $$ wget http://tsubomi.googlecode.com/files/tsubomi-2010-09-04.tgz $$ tar xzfv tsubomi-2010-09-04.tgz
でtarballを入手&解凍して使うことができる。
コードを入手したら
$$ make $$ sudo make install
でインストールする。
例えば、住所JP(http://jusyo.jp/)という住所データが入手できるサイトがあるので、ここからデータをとってきて使う。
$$ mkdir var $$ cd var $$ wget http://jusyo.jp/downloads/new/csv/csv_zenkoku.zip $$ unzip csv_zenkoku.zip $$ nkf -w zenkoku.txt > zenkoku.txt.utf8 $$ perl -ne '@a=split(/\t/);$s="$a[7]$a[9]$a[11]";$s=~s/"//g;print "$s\n"' zenkoku.txt.utf8 > zenkoku.key $$ sort -u zenkoku.key -o zenkoku.key $$ cd ..
今回は、住所データから「都道府県」「市区町村」「町域」の3列を繋げて1データとした。テキストデータはutf8を使うこと。
まずtsubomi_mkaryというコマンドでインデックスをつくる。
$$ tsubomi_mkary -p var/zenkoku.key
-pオプションを指定しておくとインデックス作成の進捗がバーで表示される。var/以下を見ると、zenkoku.key.aryというファイルが出来ているのがわかる。これがインデックス。
早速、検索を実行してみる。tsubomi_searchというコマンドを使う。
$$ tsubomi_search var/zenkoku.key 麻布 東京都港区麻布十番 : 15 東京都港区麻布台 : 15 ... 東京都港区西麻布 : 18
キーワード麻布を含む行が表示された。「:」の後ろは出現位置がバイト単位で表示されている。
次にインデックスを圧縮してみる。tsubomi_mkcsaというコマンドを使う。
$$ tsubomi_mkcsa -p var/zenkoku.key
-pオプションに付いてはtsubomi_mkaryと同様。圧縮されたインデックスはzenkoku.key.csaという名前のファイルで保存されている。この圧縮インデックスはself-indexingというもので検索に元のテキストを必要としない。試しに、元テキストと圧縮していない方のインデックスを別の場所に移して正しく検索できるか確認。
$$ mkdir tmp $$ mv var/zenkoku.key tmp/ $$ mv var/zenkoku.key.ary tmp/ $$ tsubomi_search -c var/zenkoku.key 麻布 東京都港区麻布十番 : 15 東京都港区麻布台 : 15 ... 東京都港区西麻布 : 18
このように正しく検索できることがわかる。圧縮インデックスを使う場合は-cオプションを付ける。ちなみにデータサイズはというと
$$ ls -la var/zenkoku.key* -rw-rw-r--. 1 xxxx xxxx 3869373 2010-09-04 10:10 zenkoku.key -rw-rw-r--. 1 xxxx xxxx 15477492 2010-09-04 10:12 zenkoku.key.ary -rw-rw-r--. 1 xxxx xxxx 6087740 2010-09-04 10:12 zenkoku.key.csa
となっていてzenkoku.key(元テキスト)とzenkoku.key.ary(インデックス)を併せて約19MBなのに対して、これらが圧縮されたzenkoku.key.csaは6MBなので1/3くらいに圧縮されている(tsubomi_mkcsaに、さらに圧縮率を上げるオプションがある。但し速度が犠牲になる)。
最後に実行速度についてだが、zenkoku.keyの各行をキーワードとして検索をした時にかかった時間を以下に示す(CPU:Core2Duo(1GHz) / Memory:500MB)。
$$ wc -l var/zenkoku.key 117957 $$ time tsubomi_search -c var/zenkoku.key < var/zenkoku.key > hogehoge real 0m6.926s user 0m1.473s sys 0m4.998s $$ time tsubomi_search -c var/zenkoku.key < var/zenkoku.key > hogehoge real 2m53.556s user 0m16.097s sys 2m27.487s
圧縮しない場合は12万件で約7秒、圧縮した場合は約3分かかっている。圧縮した場合は約25倍の時間がかかる。
以上。解説はここまで。ライブラリのAPIについては別途解説予定。sadakane先生の高性能ライブラリがある昨今、あえてCSAライブラリを公開する必要があるのかとか色々あるんだけど、折角作ったので。。。元々自分の作業効率化のために作ったので、それなりに使いやすいはず。たぶん。
