LZ77は、1977年にジェイコブ・ジヴ (Jacob Ziv) とエイブラハム・レンペル (Abraham Lempel) によって開発されたデータ圧縮アルゴリズム。LZ77を改良したLZSSにハフマン符号化を組み合わせ改良されたDeflateが、圧縮ツールのLHAやGZIPなどに用いられている。LZ77を使っていると書いてあるケースでも、厳密には、ほとんどのケースでLZ77の改良であるLZSSが使われている。
LZ77やLZ78の論文の著者名はZiv and Lempelの順であるが、LZの順で呼ばれることが多い。 データを先頭から順番に符号化していく方式である。現在注目している位置から始まる記号列が、それ以前に出現していたかを探す。もし出現していたならば、記号列をその出現位置と長さのポインタに置き換える。記号列を探す範囲をスライド窓
符号化の原理
もともとのLZ77では、記号列を（一致位置、一致長、次の不一致記号）という3つの値に置き換えるが、さまざまな亜種が存在する。中でもLZSSは、単純で性能もよく、いろいろな応用に使用されている。 辞書探索において、ツリーを用いる方法はゼロックスが、ハッシュテーブルを使用する方法はStac社が特許を保持していた[1]。その他、色々な会社・人物が様々な特許を取得した。ただし、特許のほとんどは既に有効期限が切れている。
特許
参照^ ⇒8 What about patents on data compression algorithms?
関連項目
LZ78
表
話
編
歴
データ圧縮方式
可逆
エントロピー符号
一進法
算術
Asymmetric numeral systems（英語版）
ゴロム
ハフマン
適応型（英語版）
正準（英語版）
MH
レンジ
シャノン
シャノン・ファノ
シャノン・ファノ・イライアス（英語版）
タンストール（英語版）
ユニバーサル（英語版）
指数ゴロム（英語版）
フィボナッチ（英語版）
ガンマ
レーベンシュタイン（英語版）
辞書式（英語版）
BPE
Deflate
Lempel-Ziv
LZ77
LZ78
LZFSE
LZH
LZJB（英語版）
LZMA
LZO
LZRW（英語版）
LZS（英語版）
LZSS
LZW
LZWL（英語版）
LZX
LZ4
ROLZ（英語版）
統計型（英語版）
Brotli
Snappy
Zstandard
その他
BWT
CTW（英語版）
Delta
DMC（英語版）
MTF
PAQ
PPM
RLE
音声
理論
ビットレート
平均(ABR)
固定(CBR)
可変(VBR)
コンパンディング
畳み込み
ダイナミックレンジ
レイテンシ（英語版）
標本化定理
標本化
音質
音声符号化
サブバンド符号化
変換符号化
知覚符号化
コーデック
A-law
μ-law
ACELP
ADPCM
CELP
DPCM
フーリエ変換
LPC
LAR