LZ77分解 2

LZ77分解 - kg86 Laboratory

前回の続きである.前回はLZ77分解の定義とその応用について説明した.今回はLZ77分解(圧縮)の計算方法について説明する.

接尾辞木を用いたLZ77分解(Algorithm KK)

接尾辞木とは,入力文字列の全ての接尾辞を格納した木構造で,様々な文字列処理に使われる汎用的な索引構造である.接尾辞木を用いたLZ77分解はKolpakov & Kucherovにより提案されているらしいが,接尾辞木に詳しければその計算は自明である.これからの説明は僕が考えた接尾辞木を使った方法であり,もし間違っていればコメントにて指摘して欲しい.

Ukkonen 1995の線形時間オンライン接尾辞木構築アルゴリズムを使用する.このアルゴリズムは入力文字列を1文字ずつ読み込み,各ステップにおける接尾辞木を出力するアルゴリズムである.このアルゴリズムの特徴は,もし1文字追加したことによって接尾辞木に新しい分岐が作られると,その全ての分岐ノードを検出出来るということだ.接尾辞木は全ての接尾辞を格納した配列である.もし1文字追加した時に新しい分岐が発生しないならば,対応する部分文字列はそれ以前に少なくとも1回出現していることを意味する.逆にもし新しい分岐が発生するならば,その部分文字列はそれ以前に出現していないことを意味する.Ukkonenのアルゴリズムを用いた時,ある項から新しい分岐ノードが作成するまでできるだけ伸ばした部分文字列がLZ77分解の項となる.(分岐が作成されるまでは,その部分文字列はそれ以前に出現するので伸ばし続ける).後は分岐を作成する度にその部分文字列の開始位置を覚えておけば新しく作成される分岐ノードの親に保存された部分文字列の開始位置がprevious positionとなる.また各ノードの深さは対応する部分文字列の長さに対応するので深さも覚えておけばlongest previous factorも同様に分かる.

このように計算することで線形時間でUkkonenの接尾辞木構築アルゴリズムを用いながらLZ77分解をオンラインに計算することが出来る.

# UkkonenのアルゴリズムはO(N log σ)時間だったかもしれない.

拡張接尾辞配列を用いた計算(Algorithm AKO)

拡張接尾辞配列[Abouelhoda et al.  2004]とは接尾辞配列と補助配列を用いて接尾辞木を模倣する手法である.(手法と呼んでいいのだろうか?)

接尾辞木でできることは当然拡張接尾辞配列でもできる.拡張接尾辞配列は接尾辞木の配列表現とも呼ばれる.