Compressed Suffix Arrayの解説(6) -B Vectorと Ψ Vector-

< Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- < | > Compressed Suffix Arrayの解説(7) -Succinct Bit Vector-Suffix Arrayの復元 >

================================================

前回までSuffix Array、unary符号、Siccinct Bit VectorというConpressed Suffix Arrayを説明するのに必要な要素が揃ったので、今回から本題に入る。
CSAのメインアイデアSuffix Array(SA)の要素を部分的に昇順に値が並ぶように置き換える、というもの。この置き換えたものをΨ(psi,プサイ) Vectorとよぶ。昇順な部分列は、その差分をunary符号化することで効率的にデータを持つことが出来る。
Ψ Vector単体では元のSAを復元できないので補助的にB Vectorというものも必要となる。今回はこれらの2つのVectorについて解説する。
なお元論文ではVectorのインデックスが1から始まっているのだがプログラムとして実装する場合の利便性を考え0スタートで置き換えて解説している。あしからず。


SAはある手続きを踏むことでΨ Bector、B Vector、SA1 Vectorという3つのVectorに分解される。そしてSA1 Vectorはそれ自身がSuffix Arrayになっていて再帰的な手続きでΨ1 Bector、B1 Vector、SA2 Vectorという3つのVectorに分解される。
この手続きを(L-1)回繰り返して生成されるΨi Vector(i=0,...,L-1)、Bi Vector(i=0,...,L-1)、SAi Vector(i=L)がCompressed Suffix Arrayの構成要素となる。なおLの値はSAのサイズNに対してloglogNを越えない最大の整数とする。
B Vectorのi番目の要素はSA[i]の値が奇数であれば1を、偶数であれば0を持つ。例えばaabbababという文字列

i : 01234567
T : aabbabab
SA: 06417532

に対してB Vector

SA: 06417532
B : 00011110

となる。
Ψ Vectorのi番目の要素はSA[i]の値が奇数であればそのままiを、偶数であればSA[j]=SA[i]+1となるようなjを値として持つ。↑のaabbababの例で説明。まずSA[i]が奇数の要素を埋める。

i  : 01234567
SA : 06417532
PSI:    3456

次に偶数の要素を埋める、例えばPSI[0]はSA[0]=0であるからSA[j]=SA[0]+1=0+1=1となるjを探すとj=3であることがわかる。よってPSI[0]=3となる。同様に他も埋めると、

i  : 01234567
SA : 06417532
PSI: 34534566

となる。
SA1 VectorはSAの値が奇数であるものを2で割ったものを並べて作る(余りは捨てる)。つまり

i  : 01234567
SA : 06417532
   : 064    2
SA1:    0321

となる。
今回はここまで。次回は、今回作ったΨ Vector、B Vector、SA1 Vectorから元のSAを復元する方法を解説する。

================================================< Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- < | > Compressed Suffix Arrayの解説(7) -Succinct Bit Vector-Suffix Arrayの復元 >