15分でわかる(とうれしい)Suffix Arrayの簡単な圧縮法

文字列が超長い場合SuffixArrayが大きすぎてメモリが一杯になってしまう。
ので圧縮して小さくしたい。基本的な圧縮法である差分圧縮を使った簡単なSuffixArrayの圧縮法を紹介する。

参考:


さて以下のSuffixArrayを差分圧縮したい。

文字列     : b a n a n a
SuffixArray: 6 4 2 1 5 3

SuffixArrayの差分を取る。

SuffixArray: 6  4  2  1 5  3
差分       : 6 -2 -2 -1 4 -2

マイナスの数がたくさん出てきた。負の数があると差分圧縮できない。ので差分が正の数になるようにSuffixArrayをいじる。
SuffixArrayのそれぞれの数字に1から順に番号をふる。

Index      : 1 2 3 4 5 6
SuffixArray: 6 4 2 1 5 3

これをIndexとよぶ。Indexは順番にふった数字なので差分をとると

Index: 1 2 3 4 5 6
差分 : 1 1 1 1 1 1

となる。マイナスがなく、数が小さい。理想的。
理想的なのでIndexを使う。SuffixArrayさん、さようなら。
・・・というわけにはいかない。そもそもSuffixArrayを消しては意味が無い。
のでSuffixArrayを一意に復元できるようなIndexを考える。

文字列     : b a n a n a
Index      : 1 2 3 4 5 6
SuffixArray: 6 4 2 1 5 3

Indexに対応するSuffixArrayの値に1足した値をSuffixArrayから探す。例えばIndex=3に対して

# Index=3 に SuffixArray=2 が対応
Index      : 1 2 [3] 4 5 6
SuffixArray: 6 4 [2] 1 5 3

# SuffixArray=(2+1)=3を探す
Index      : 1 2 [3] 4 5  6
SuffixArray: 6 4 [2] 1 5 [3]

となる。ここで見つけたSuffixArray=3に対応するIndexを新Indexとしてみる。

# SuffixArray=3 に Index=6 が対応
Index      : 1 2 [3] 4 5 [6]
SuffixArray: 6 4 [2] 1 5 [3]

# Index=6をIndex=3に対する新Indexにする
Index      : 1 2 [3] 4 5 [6]
SuffixArray: 6 4 [2] 1 5 [3]
新Index    :      6

同じことを他のIndexに対してもやってみる。ただしSuffixArray=(6+1)=1とする。

Index      : 1 2 3 4 5 6
SuffixArray: 6 4 2 1 5 3
新Index    : 4 5 6 3 1 2

この新Indexに対して2点気になることがある。つまり

- 差分圧縮できるの？
- この新IndexからSuffixArrayが復元できるの？

ということ。これらを検証する。

まず差分圧縮できるか？実は全体に対してはできないのだが、部分的に可能

SuffixArray: [6] [4] [2] [1 5] [3]
新Index    : [4 5 6] [3] [1 2]

差分圧縮可能な箇所(差分が正の数になってるところ)を[]でまとめた。新Indexのほうが圧縮できる範囲が大きい。

次。SuffixArrayの復元。こっちも実は新Indexだけではできないのだが(またかよ)、SuffixArrayの値が1になる位置(サンプル位置)を余分にもっておけば復元できる。
今回の場合以下のとおり

SuffixArray: 6 4 2 [1] 5 3
新Index    : 4 5 6  3  1 2
サンプル位置は4だよ

まずSuffixArrayの4番目の値が1なのはサンプル位置が4なのですぐわかる。

新Index    : 4 5 6 3 1 2
SuffixArray:       1

つぎにIndexの4番目の位置にある値をみる。今回は3。

新Index    : 4 5 6 [3] 1 2
SuffixArray:        1

SuffixArrayの3番目の位置に2を入れる。

新Index    : 4 5 6 [3] 1 2
SuffixArray:     2  1

つぎにIndexの3番目の位置にある値をみる。今回は6。

新Index    : 4 5 [6] 3 1 2
SuffixArray:      2  1

SuffixArrayの6番目の位置に3を入れる。

新Index    : 4 5 [6] 3 1 2
SuffixArray:      2  1   3

これを繰り返すと

新Index    : 4 5 6 3 1 2
SuffixArray: 6 4 2 1 5 3

となる。ここで得られたSuffixArrayが最初のSuffixArrayと同じであることは本記事の最初の部分を見て確認されたい。
なお今回は簡単のためにサンプル位置としてSuffixArray=1の点を使ったが、実際はSuffixArrayがNの倍数の位置全部をサンプル位置にする。Nが小さいほどメモリをたくさん使うが、SuffixArrayの復元時間は短くなる。N=1のときが普通のSuffixArrayとなる。
余談だが、ここで紹介した簡単な圧縮法は一般にCompressed Suffix Arrayと呼ばれている。