Compressed Suffix Arrayの解説(7) -Suffix Arrayの復元-

計算機科学

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

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

いい加減、記事書くのをサボっていたCSAの記事だけど、気が向いたので続きを書く事にした。というか今回で最後。全7回。長い。。
こういう長い記事は自分に向いてない気がしてきた。うーん。ともあれSuffix Arrayの復元に付いて書いて説明を終える。


目的はインデックスの位置iが与えられた時に対応するSuffixArrayの値SA[i]を得ること。
前回、SuffixArrayをB Vector、Ψ Vector、SA1 Vectorの3つに分解した。Ψ VectorでPSI[i]=iとなるものは持っていなくても良いので省略。

i  : 01234567
SA : 06417532

B  : 00011110
PSI: 345    6
SA1:    0321

PSIおよびSA1は実際には詰めて持っておく。つまり以下のとおり。

i  : 01234567
SA : 06417532

B  : 00011110
PSI: 3456
SA1: 0321

これをもとに、SAを復元する方法を考える。まずB[i]の値をチェックする。B[i]が1であれば対応するSA1[j]が存在する。jはBについてi番目までにいくつ1が出現したかを数えれば良い(Bが1の要素にしか対応したSA1が無いため)。
この数え上げにはselect()を使えば良い。そしてSA1[j]を倍にして1足した数がSA[i]となる。ここまでをまとめると、以下のようになる。

get_SA(i):
  j = select_B(i, 1)
  return (SA1[j] * 2 + 1)

次にB[i]が0の場合。このときは対応するPSI[j]が存在する。jはBについてi番目までにいくつ0が出現したかを数えれば良い(Bが0の要素にしか対応したPSIが無いため)。
この数え上げにはselect()を使えば良い。そしてPSI[j]を添字とするSAの値SA[PSI[j]]はSA[i]に1足した数なので

get_SA(i):
  j = select_B(i, 0)
  return (SA[PSI[j]] - 1)

とすればSA(i)が求まる。
実際に適当な数を入れてみると、正しくSA(i)の値が求まることがわかる。<おまけ>

  • Succinct Bit Vectorは実はUnary符号よりもVertical Codeを使ったほうが6倍圧縮率が高いのでそっちを推奨。Vertical Codeについては以下を参照。

Vertical Codeを調べたよ - EchizenBlog-Zwei

  • なぜSAをそのまま圧縮しないでBとPSIに分けたのか？これはPSIが部分的に単調増加(差分圧縮できる)する性質を持っているから。なぜ部分的に単調増加するのかというと、SAが"テキストの"インデックスを持っているのに対して、PSIは"SAの"インデックスを持っているから。SAのインデックスというのは0,1,2,...という普通の数の並び。なので完全に単調増加。でもそのかわり何の情報もない。そこで"隣あっているSAのインデックス"を持たせることでSAを復元できると同時に、SAの値を"SAのインデックス"化している。この"隣のインデックス"は完全な単調ではないものの部分的に単調になっている。

================================================< Compressed Suffix Arrayの解説(6) -B Vectorと Ψ Vector- < | > ---- >