データ圧縮は記憶装置の節約、アクセスの高速化、ネットワークでの
転送時間の短縮のために重要である。
近年良く使われている圧縮プログラムである gzip は、LZ77符号を使っており、
その符号化には辞書から最大一致文字列を探索することが必要である。
gzipでは文字列をハッシュ表に登録しているが、ハッシュの衝突が多い場合に
検索が遅くなる。
本研究では、gzipで使われている最大一致文字列検索アルゴリズムを
我々のものと入れ換えることで高速化した。
あらかじめハッシュの衝突の回数を数え、衝突が多く起きるところは
各文字列の4文字目以降を使い、2レベルのハッシュを使うことで
ハッシュのリストの長さを短くでき、
文書ファイルやPost Scriptファイル
のようなファイルに対しては探索領域を減らすことができた。
その結果、英文のテキストの圧縮で1.3倍、英語の論文のPost Scriptファイルで
3倍から5倍の速度が達成できた。