LZ77分解 3

LZ77分解 2 - kg86 Laboratory

前回までは接尾辞木を使ったアルゴリズムを紹介した.今回は接尾辞配列を使った計算アルゴリズムを紹介する.接尾辞木は全ての接尾辞を辞書順に並べた時の各接尾辞の開始位置の並びを保存した配列である.(今後SAと表記する).

以下の論文を参考にする.

 Gang Chen, Simon J. Puglisi, William F. Smyth: Lempel-Ziv Factorization Using Less Time & Space. Mathematics in Computer Science 1(4): 605-623 (2008)

CPS1, CPS2, CPS3が提案されているがCPS1, 3に関しては理解できなかった.とても難しい.そのためCPS2のみ解説する.

入力文字列Tのi番目から開始するファクターfjについて考える.接尾辞配列は辞書順に並んでいるため,ある文字列をprefixにもつ接尾辞は接尾辞配列上で連続している.ここでSA[l..r]をfjをprefixとして持つ接尾辞の最大の範囲とする.そのような範囲に必ずSA[j]=iとなる接尾辞とSA[j'] < iとなる接尾辞も含まれているはずである.(LZ77分解の定義よりi未満にもfjが出現していなくてはいけない).もしfjとそのような範囲が分かっていれば,Prev(i)=SA[l..r]の最小値,LPF(i)=|fj|となる.

ではこのような範囲とfjをどのように求めるかが問題である.T[i..i'] (i ≦ i')をprefixとして持つ接尾辞配列の範囲SA[li'...ri']を考えよう.LZ77分解は以前に出現した部分文字列で最長の部分文字列で分解するので,i'をSA[li'...ri']にi未満の接尾辞が含まれる最大の値とした時T[i..i']で分解される(SA[l(i'+1)...r(i'+1)]の最小値はi).

それでは1文字ずつ追加し,範囲を求め,その最小値を求めていけば良い.1文字ずつ追加した時の接尾辞配列の範囲はTの逆文字列についてバックワードサーチと呼ばれるテクニックを使用することにより求めることができる.(本来ならばTのフォワードサーチと呼ぶべきかもしれないが,バックワードサーチのほうがこの業界ではよく使われるためこのようなややこしい表記になっている).1文字追加した時に次の範囲を求めるコストはO(log N).また範囲上の最小値の計算はRange Minimum Queryを使いO(N)時間の前処理で任意の範囲についてO(1)時間で計算可能である.よって全体でO(N log N)時間でLZ77分解可能.