LZSS

LZSS(Lempel–Ziv–Storer–Szymanski)とは、LZ77を改良して圧縮効率を高めたデータ圧縮アルゴリズムのことです。

LZSSでは、以下の形式で符号化を行います。

不一致の場合:[不一致ビット][不一致記号]

一致の場合:[一致ビット][一致位置][一致長]

LZ77との違いはこれだけで、これ以外の符号化の手順は、LZ77と同じです。

LZSSの用語説明

不一致ビット

参照部で符号化部の記号列が一致しなかった場合、符号化データの一部として0を出力します。この0は、1ビットです。

一致ビット

参照部で符号化部の記号列が一致した場合、符号化データの一部として1を出力します。この1は、1ビットです。

LZSSによる符号化の手順

符号化する元データをababcbababababababcbababababbabaとします。今回は、一つの記号を1バイトで表すこととします。よって、32バイトの記号列です。

まず、符号化部に記号列の先頭部分をコピーします。ここでは、参照部も符号化部も長さ(サイズ)は、14バイトとします。参照部の下には、記号位置を16進数で表示しています。

参照部には、この時点では何も入っていないのでスライド窓内の記号列全体を1バイト左にずらします。そして、符号化データとして、0aを出力します。0は不一致ビット、aは不一致記号です。区別しやすいように以降、ビットは太文字にします。(ここまでの符号化:0a)

次に、bから始まる記号列は参照部にないのでスライド窓内の記号列全体を1バイト左にずらします。符号化データとして、0bを出力します。(ここまでの符号化:0a0b)

今度は、abが参照部と最長一致しました。符号化データとして、1C2を出力します。1は一致ビットです。C2は、LZ77と同様に一致位置と一致長です。(ここまでの符号化:0a0b1C2)

そして、符号化が完了した記号列が参照部に押し出されるようにスライド窓内の記号列全体を左にずらします。

次に、cから始まる記号列は参照部にないのでスライド窓内の記号列全体を1バイト左にずらします。符号化データとして、0cを出力します。(ここまでの符号化:0a0b1C20c)

次は、babが参照部と最長一致しました。符号化データとして、1A3を出力します。(ここまでの符号化:0a0b1C20c1A3)

そして、符号化が完了した記号列が参照部に押し出されるようにスライド窓内の記号列全体を左にずらします。

次は、ababが参照部と最長一致しました。符号化データとして、164を出力します。(ここまでの符号化:0a0b1C20c1A3164)

そして、符号化が完了した記号列が参照部に押し出されるようにスライド窓内の記号列全体を左にずらします。

次は、abababが参照部と最長一致しました。符号化データとして、186を出力します。(ここまでの符号化:0a0b1C20c1A3164186)

そして、符号化が完了した記号列が参照部に押し出されるようにスライド窓内の記号列全体を左にずらします。

次は、cbababababが参照部と最長一致しました。符号化データとして、10Aを出力します。(ここまでの符号化:0a0b1C20c1A316418610A)

そして、符号化が完了した記号列が参照部に押し出されるようにスライド窓内の記号列全体を左にずらします。

最後に、babaが参照部と最長一致しました。符号化データとして、154を出力します。符号化が完了しました。(最終的な符号化:0a0b1C20c1A316418610A154)

どれだけ圧縮できたか

参照部の記号位置と符号化部の一致長は、今回はそれぞれ4ビットで表現できるので合わせて1バイトとします。よって、今符号化した0a0b1C20c1A316418610A154は、81ビットとなります。

LZ77で符号化した場合、96ビット(12バイト)なので、LZSSの方が圧縮できています。

LZSSの復号

LZ77と同様に、逆参照を行えば、復号できます。