counter7089

圧縮接尾辞配列ライブラリ csalib

文字列を圧縮したまま検索するライブラリです.
文字列の一部を高速に復元することもできます.

圧縮接尾辞配列ライブラリ (2010-08-10版)
Direct BWT construction
External Memory BWT construction

http://code.google.com/p/csalib/ にもあります.

注意: dbwt100717.zipにはバグがありました.Ubuntuでは動かない可能性が高いです.
dbwt100730.zipを使ってください.
 

索引

索引とは,本の索引と同じ意味で,検索を高速に行うためのデータのことです.
ただし,本の索引では代表的な言葉のみが登録されていますが,このライブラリの索引は
任意の語が検索できるようになっています.
 

BW変換

検索したいファイルの索引を作る場合,まずファイルをBW変換する必要があります.
そして,BW変換されたファイル(以後BWT)から索引を作ります.
 

索引の作り方

BW変換されたファイルから,圧縮された索引を作ります.
 

圧縮法

圧縮接尾辞配列と一言で言っていますが,大きく分けて2種類の圧縮法が存在します.
compressed suffix array (CSA) と FM-index と呼ばれます.
両者は可能な操作は同じですが速度と圧縮率が違います.
 

コンパイルの仕方

単に make するだけですが,いくつか注意点があります.
 

C言語でのライブラリの利用

自作のCプログラムからライブラリを利用する場合,csa.h をインクルードし,csa.a をリンクする必要があります.
 

Rubyでのライブラリの利用

Rubyの拡張ライブラリとしても利用できます.
 

Pizza&Chili Corpus API

Pizza&Chili CorpusのAPIにも準拠しています.
 

サンプルプログラム

Name
Size
Create date