LZ77 【Lempel-Ziv 77】

概要

LZ77（Lempel-Ziv 77）とは、1977年にエイブラハム・レンペル(Abraham Lempel)氏とジェイコブ・ジブ(Jacob Ziv)氏が考案したデータ圧縮アルゴリズム。データ圧縮方式の主流の一つである「辞書圧縮」(辞書型符号化)の起源となったアルゴリズム。

圧縮時、データを先頭から順に読み込んでいき、過去に読み込んだ一定の範囲（スライディングウィンドウという）の中に同じものが出現していないか探す。一致する箇所が見つかったら、データを一致した箇所の位置と長さで置き換える。

例えば、英文の文書を圧縮しているとき「algorithm」という単語に出くわしたとする。このとき、もし過去に符号化済みの参照範囲の先頭から15文字目に同じ「algorithm」が出現していたら、「algorithm」と書く代わりに「ここにある単語は先頭15文字目からの9文字に一致している」という意味の（15,9）という数値列で置換することができる。数値一つを1バイトで表すことにすればこれは2バイトで表現でき、元の9バイトから7バイト削減できる。

LZ77を元に、1982年にジェームズ・ストラー（James Storer）氏とトーマス・シマンスキー（Thomas Szymanski）氏が改良を加えた「LZSS」が発表され、Deflateアルゴリズム（Zipやgzip、LHZ、PNGが採用）などに広く応用されている。Lempel氏とZiv氏は1978年に別の辞書圧縮方式であるLZ78を考案しており、こちらはGIF画像形式に用いられたLZWへと発展している。

(2023.5.9更新)