Compressed Suffix Arrayの解説(3) -圧縮の方針-
< Compressed Suffix Arrayの解説(2) -SAの計算量- < | > Compressed Suffix Arrayの解説(4) -unary記法- >
================================================
今回からCompressed Suffix Array(CSA)の仕組みについて解説する。
基本的に、以下の論文に従って説明をしているので詳細を知りたい場合は適宜参照するといいかも。
Compressed Suffix Array and Suffix Trees with Applications to Text Indexing and String Matching(Grossi & Vitter 2000)
まずCSAの圧縮の方針について。
通常のSuffix Array(SA)は各々のインデックスにlogN bit使って部分文字列の位置を持たせていた。つまり、すべてのインデックスに同じだけのbitを用いていたのだが、これは効率が良くない。頻出する値には短いbit列を、滅多にでない値には長いbit列を割り当てた方が全体で必要になるbit数は小さくなる。
SAではインデックスをunary記法でbit列に変換する。unary記法というのは小さい数値ほど短いbit列を割り当てる方式で、具体的に数値からbit列に変換する方法は次回以降で説明する。
さてSAでは1からNまでの値が一度ずつ出てくるので小さい数値が頻出するという状況にはならない。このままunary記法でbit列しても大きな圧縮効果は得られない。そこでSAのうち値が昇順になっている部分について、値そのものの代わりに差分を持たせることで、意図的に小さな値を頻出させる、ということを考える。
例えば、SAが
1 2 5 3 4 6
であったとする。この場合前半の3つ、後半の3つがそれぞれ昇順になっているので差分をとって
1 2 5 => 1 (1+1) (1+1+3) => 1 1 3 3 4 6 => 3 (3+1) (3+1+2) => 3 1 2
と変形し差分をとったSA
1 1 3 3 1 2
を得る。これによって元のSAが持っていた5や6などの大きな値がなくなり1や2などの小さい値ばかりとなった。
だが、実際のSAでは今の例のように、まとまって昇順に値が並んだ箇所というのは頻出しない。そこで意図的にそのような状況を作り出す必要がある。そのようにして作り出したのがΨという値の列(vector)である。Ψ vectorは部分的に値が昇順になっているので、unary記法でbit列に変換することで高い圧縮率が得られる。
Ψ vectorは、それ単体ではSAを復元できない。併せてB vectorというbit列を持っておく必要がある。B vectorはbit列なのでbit列に変換することなく、そのまま持たせる。
まとめると、Compressed Suffix ArrayというのはSuffix ArrayをΨ vector(をbit列にしたもの)とB vectorに分割して持たせることで圧縮を実現する方法、といえる。
これを実現するためには、
という3つの要素が必要。これらを次回以降で説明する。
================================================< Compressed Suffix Arrayの解説(2) -SAの計算量- < | > Compressed Suffix Arrayの解説(4) -unary記法- >
