RFC 1951に書かれているDeflate圧縮のアルゴリズムについて。

もう今だと、だいたいパテントも切れてるみたいな話だけど、その当時パテントを気にしなくてもいいアルゴリズムとして記載されてたわけだけど、こんな感じ。

先頭3文字をキーにして、その文字列があらわれる位置を値にしてハッシュ表を用意する。チェインドなハッシュ表。つまり値は複数の位置を含むリンクトリストになっている。

読み込んでいる位置から3文字を先読みしてハッシュ表から位置を探す。複数の位置について、その後の入力に最も長くマッチするものを選ぶ。

で一文字進むのだけど、その時にハッシュ表に値を追加する。

これが基本的な感じ。あとは、決められた範囲よりも遠い値についてはハッシュ表から削除したほうが良さそう。

この基本に対して、圧縮率を上げるという側面と速度を上げるという側面とから、バリエーションがある。

圧縮率を上げるという側面を考えると、ある時点でマッチしたとしても、それで決めてしまわないで、もう一文字読み込んだ場合により長くマッチするかどうかを調べるというやりかたがある。

スピードを上げるという側面では、まず上記のバリエーションについて、ある程度以上長くマッチした場合には次の読み込み位置でのマッチは試さないというものがある。また、スピードがかなり重要という場面では、3文字のキーに対して、値が存在しないときだけ値を追加するとか、「長くマッチした」ものについてはハッシュ表に追加しないとかがある。