はじめに

まず、LZSS とはどういったアルゴリズムなのかを簡単に説明します。
簡単な例をあげます。

"aiueoaiueoaiueo"

このような文字列が入力として与えられた時、"aiueo" の繰り返しに注目します。
2回目の "aiueo" は最初の "aiueo" からコピーするようにします。同様に3回目も同じようにします。
すると以下のように表すことができます。

"aiueo[5文字戻り,5文字分参照][10文字戻り,5文字分参照]"
(ここでは、これを簡単に "aiueo[5,5][10,5]" と表すことにします。)

この表現でもまだ無駄があります。
ここでは5文字分を一区切りとして使用していますが、"aiueoaiueo" 2つの重なりで表現した方が短くなります。

"aiueoaiueo....."
".....aiueoaiueo"

から

"aiueo[5,10]"

とすることができます。

なお、実際のデータでは LZSS は先頭ビットで長さ距離符号かそうでないかを判定するようにしています。
DEFLATE の実装では 0-255 (0x000-0x0FF) をリテラル、256-285 (0x100-0x11D) を記号として扱い、257-285とその後に続くデータで長さと距離を表しています。(256は終端記号)
また、DEFLATE ではそれぞれの範囲が、長さ 3-258, 距離 1-32768 と決められています。

LZ77 と LZSS の違い

ちなみに、よく LZ77 と書かれているものは LZSS であることが多いのですが、違いについて一応書いておきます。
LZ77 では先ほどの簡易表現の最後に「不一致だった場合は不一致文字」を追加して、上記の例は以下のように表現されます。

"a[0,0,i][0,0,u][0,0,e][0,0,o][5,10]"

不一致に関しても符号化しているため、長くなってしまうのが欠点でそれを短縮したのが LZSS という位置づけです。

lazy matching

先ほどの例は簡単な例なので特に悩む点はありませんでしたが、以下のような例はどうでしょうか。

"bcdefghijklmnabcabcdefghijklmn"

一般的な実装では、左から順に一致を見ていくようになっているので

"bcdefghijklmnabcabcdefghijklmn"
"bcdefghijklmnabc[3,3][17,11]"

となります。しかし、もっと短い表現があります。

"bcdefghijklmnabcabcdefghijklmn"
"bcdefghijklmnabca[17,13]"

です。長さと距離の符号よりもリテラルの方が短いビットで表現できるため、こちらのほうが短くなります。

lazy matching とは、前の例で [3,3] を見つけた時点で「保留」しておき、より長いものが見つかった場合はそちらを採用するようにします。
今回実装したのは、以下のようなアルゴリズムです。

 1. [3,3]を見つけたら「保留」にする。
 2. 次の位置でマッチした場合(上記の例の場合 [17,13] )、「保留」のマッチの一致長と比較する。
 3. 「保留」のマッチの方が長ければ今回のマッチはなかったことにして戻り、「保留」のマッチを採用する。
    現在のマッチの方が長ければ、前回のマッチは捨て前回の位置はリテラルとして扱い、現在のマッチを採用する。

これにより、圧縮率が上昇するようになっています。
ただし、「最長一致」の探索が増えているため、負荷は上昇します。
そのため、一般的な実装では圧縮レベルによって「lazy matching を行うかどうか判定する一致長」を変えて、ある程度長い一致ならば lazy matching せずに採用するといった工夫がされています。