データ圧縮法概説　第5章−２

5.3 LZ77符号化の手順

LZ77符号化の手順は以下のとおりです。

参照部Ｎバイト、符号化部Ｆバイトの大きさのスライド窓を用意する。
通常、Ｎは1024〜4096バイト、Ｆは16〜256バイト程度が用いられます。例えばＮ＝4096、Ｆ＝256としますと、最大(Ｆ−１＝255)バイトまでの最長一致系列を処理することができ、［最長一致系列の参照部の先頭からのオフセット値］12ビット、［最長一致系列の記号数］８ビット、［一致しない最初の記号」８ビットの、計28ビットの固定長で符号化することになります。
元データの先頭からＦバイトを符号化部にコピーする。
最初の記号はそのまま出力する。
最初は参照部にデータがありませんから、最初の記号は必ず「00＜最初の記号＞」と符号化されます。このため、最初の記号だけは00を付けずに記号だけ出力します。
スライド窓を１バイト右にスライドする。
符号化部の先頭から始る記号列に対する最長一致系列を参照部から探し、［最長一致系列の参照部の先頭からのオフセット値］［最長一致系列の記号数］［一致しない最初の記号」という形式で符号化し、それを出力する。
例えばオフセットｍから始るｐバイトが最長一致系列であり、一致しない最初の記号がｘだとしますと、「mpｘ」という符号を出力し、一致する記号がない時は「00＜符号化部の最初の記号＞」という符号を出力します。

最長一致系列は最大(Ｆ−１)バイトであり、符号化部のＦバイト全体が一致する場合でも最長符号系列を(Ｆ−１)バイトとし、最後の記号を一致しない最初の記号として扱います。また最長一致系列の先頭は参照部にある必要がありますが、末尾は符号化部にまで入ってもかまいません。例えば下図のような場合、最長一致系列はオフセット(N-3)から始る５バイトが最長一致系列となり、一致しない最初の文字はｄとなります。したがって０≦ｍ≦(Ｎ−１)、０≦ｐ≦(Ｆ−１)ということになります。
スライド窓を符号化した(ｐ＋１)バイトだけ右にスライドする。
元データが終了するまで5.と6.を繰り返す。
下図のように、最後に不一致記号がない場合は「mp」だけを出力します。

5.4 LZ77符号化の実例

例として３章５節のハフマン符号の例と同じ「aabbccccddddeeeeeeeeffff」という元データを、前節の手順に従って符号化してみましょう。

元データが短いため、参照部８バイト、符号化部８バイトの大きさのスライド窓を用意する。
元データの先頭から８バイトを符号化部にコピーする。
最初の記号はそのまま出力する。

符号化データ：ａ
スライド窓を１バイト右にスライドする。
最長一致系列が「ａ」なので「71ｂ」を出力する。

最長一致系列のオフセット値ｍ＝７　バイト数ｐ＝１　最初の不一致記号：ｂ
符号化データ：ａ71ｂ
スライド窓を２バイト右にスライドする。
最長一致系列が「ｂ」なので「71ｃ」を出力する。

最長一致系列のオフセット値ｍ＝７　バイト数ｐ＝１　最初の不一致記号：ｃ
符号化データ：ａ71ｂ71ｃ
スライド窓を２バイト右にスライドする。
最長一致系列が「ｃｃｃ」なので「73ｄ」を出力する。

最長一致系列のオフセット値ｍ＝７　バイト数ｐ＝３　最初の不一致記号：ｄ
符号化データ：ａ71ｂ71ｃ73ｄ
スライド窓を４バイト右にスライドする。
最長一致系列が「ｄｄｄ」なので「73ｅ」を出力する。

最長一致系列のオフセット値ｍ＝７　バイト数ｐ＝３　最初の不一致記号：ｅ
符号化データ：ａ71ｂ71ｃ73ｄ73ｅ
スライド窓を４バイト右にスライドする。
最長一致系列が「ｅｅｅｅｅｅｅ」なので「77ｆ」を出力する。

最長一致系列のオフセット値ｍ＝７　バイト数ｐ＝７　最初の不一致記号：ｆ
符号化データ：ａ71ｂ71ｃ73ｄ73ｅ77ｆ
スライド窓を８バイト右にスライドする。
最長一致系列が「ｆｆｆ」なので「73」を出力し、符号化終了。

最長一致系列のオフセット値ｍ＝７　バイト数ｐ＝３　最初の不一致記号：なし
符号化データ：ａ71ｂ71ｃ73ｄ73ｅ77ｆ73