読み方 ： じしょしきあっしゅくほう

辞書式圧縮法とは？

例えば、自然言語の文章を圧縮する場合、文章を先頭から順に走査しながら、初めて現れた単語を順次「辞書」と呼ばれる専用の記憶領域へ登録していく。以降に同じ単語が現れた場合、その単語そのものを記録するのではなく、辞書内の位置と長さを示す短い符号に置き換える。復元時は、単語がそのまま記録されている箇所は単語を取り出し、参照符号が記録されている箇所は辞書を参照して対応する単語に置き換える。

辞書の構築方法には大きく二つの方式がある。対象データ全体を事前に走査して辞書を作成する静的な方式と、圧縮処理を進めながら動的に辞書を構築する方式である。後者では圧縮側と復元側が同一の規則で辞書を生成するため、辞書データを別途保存しなくて済む場合がある。

代表的なアルゴリズムとして、1977年にジェイコブ・ジブ（Jacob Ziv）とアブラハム・レンペル（Abraham Lempel,）が考案した「LZ77」と、改良版の「LZ78」がある。LZ77は「直前の一定範囲のデータ」（スライディングウィンドウ）を辞書として扱い、一致する符号列を参照位置と長さで表現する。「LZSS」をはじめとする様々な亜種があり、現代でも派生手法が様々な用途で用いられている。

LZ78は出現した符号列を明示的な辞書テーブルへ登録しながら処理を進める方式で、これを改良した「LZW」は、GIFやTIFF等の画像形式に採用されている。現在広く使われている「Deflate」はLZ77とハフマン符号化を組み合わせたもので、Zip形式やgzip形式の圧縮アルゴリズムとして知られる。

辞書式圧縮法は同じパターンが多く登場するデータほど圧縮率が高くなる。自然言語の文書やプログラムのソースコード、ログデータなど、同じ単語や構文が繰り返し登場するデータに対して高い圧縮率を発揮する。逆に、規則性の乏しいデータや、写真画像・音声・動画などに見られる「似ているがわずかに異なるパターン」が頻出するデータにそのまま適用してもあまり効果が得られない。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。