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

5.5 LZ77符号の復号化手順

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

参照部Ｎバイト、符号化部Ｆバイトの大きさのスライド窓を用意する。
ＮとＦは符号化時と同じ値を用いる必要があります。そのためには最初からＮとＦをある定数に固定してしまってもかまいませんし、ＮとＦの値を符号化したデータ中にオーバーヘッドとして追加してもかまいません。

LZ77符号を応用した圧縮アーカイバLHAは、スライド窓の大きさが異なる数種類の圧縮法をサポートしていて、それらを「-lh5-」や「-lh6-」といった識別コードによって区別しています。
最初の記号を符号化部の先頭にコピーする。
最初の記号は本来は「00＜最初の記号＞」であり、この作業はその符号を復号したことに相当します。
符号化部の記号を復号し、スライド窓を１バイト右にスライドする。
［最長一致系列の参照部の先頭からのオフセット値］［最長一致系列の記号数］［一致しない最初の記号」という形式の符号を読み込み、それを各要素に分解する。そして対応する参照部の記号列を符号化部の先頭からコピーし、その後に一致しない最初の記号をコピーする。
例えば「mpｘ」という符号の場合、参照部のオフセットｍから始るｐバイトを符号化部の先頭からコピーし、その後にｘをコピーします。ｍとｐがどちらも０の場合は、一致しない最初の記号を符号化部の先頭にコピーします。

また下図のように、コピーする記号列が符号化部にまで入り込む場合もあります。例えば「(N-3)5ｄ」という符号の場合、オフセット(N-3)から始る３バイトを符号化部の先頭にコピーし、その後にコピーしたばかりの符号化部の先頭の２バイトをコピーし、さらにその後にｄをコピーします。
符号化部の記号列を復号し、スライド窓を復号化した(ｐ＋１)バイトだけ右にスライドする。
符号化データが終了するまで4.と5.を繰り返す。
最後の符号が「mp」だけの場合は、参照部の記号列をコピーし、それを復号して終了します。

5.6 LZ77符号の復号化実例

例として、符号化の実例で符号化した「ａ71ｂ71ｃ73ｄ73ｅ77ｆ73」を前節の手順に従って復号化してみましょう。

参照部８バイト、符号化部８バイトの大きさのスライド窓を用意する。
最初の記号を符号化部の先頭にコピーする。
符号化部の記号を復号し、スライド窓を１バイト右にスライドする。

復元データ：ａ
「71ｂ」を読み込み、対応する参照部の記号列を符号化部にコピーし、その後に不一致記号をコピーする。

最長一致系列のオフセット値ｍ＝７　バイト数ｐ＝１　最初の不一致記号：ｂ
符号化部の記号列を復号し、スライド窓を２バイト右にスライドする。

復元データ：ａａｂ
「71ｃ」を読み込み、対応する参照部の記号列を符号化部にコピーし、その後に不一致記号をコピーする。
最長一致系列のオフセット値ｍ＝７　バイト数ｐ＝１　最初の不一致記号：ｃ
符号化部の記号列を復号し、スライド窓を２バイト右にスライドする。

復元データ：ａａｂｂｃ
「73ｄ」を読み込み、対応する参照部の記号列を符号化部にコピーし、その後に不一致記号をコピーする。
最長一致系列のオフセット値ｍ＝７　バイト数ｐ＝３　最初の不一致記号：ｄ
符号化部の記号列を復号し、スライド窓を４バイト右にスライドする。

復元データ：ａａｂｂｃｃｃｃｄ
「73ｅ」を読み込み、対応する参照部の記号列を符号化部にコピーし、その後に不一致記号をコピーする。

最長一致系列のオフセット値ｍ＝７　バイト数ｐ＝３　最初の不一致記号：ｅ
符号化部の記号列を復号し、スライド窓を４バイト右にスライドする。

復元データ：ａａｂｂｃｃｃｃｄｄｄｄｅ
「77ｆ」を読み込み、対応する参照部の記号列を符号化部にコピーし、その後に不一致記号をコピーする。

最長一致系列のオフセット値ｍ＝７　バイト数ｐ＝７　最初の不一致記号：ｆ
符号化部の記号列を復号し、スライド窓を８バイト右にスライドする。

復元データ：ａａｂｂｃｃｃｃｄｄｄｄｅｅｅｅｅｅｅｅｆ
「73」を読み込み、対応する参照部の記号列を符号化部にコピーする。

最長一致系列のオフセット値ｍ＝７　バイト数ｐ＝３　最初の不一致記号：なし
符号化部の記号列を復号し、復号化終了。

復元データ：ａａｂｂｃｃｃｃｄｄｄｄｅｅｅｅｅｅｅｅｆｆｆｆ

5.7 LZ77符号化の特徴

どんなデータにも適用可能で汎用性がある。
同じ語句が続けてたくさん出てくるデータに特に向いている。
１パスで符号化するため圧縮過程が高速。
圧縮率が高い。
高性能で実用的な手法のため実用例が多い。
圧縮／展開方法はやや複雑だが理解はしやすい……と思う？(^^;)