LZ78
LZ78 は Lempel と Ziv が 1978 年に提案した辞書圧縮アルゴリズムである。明示的な辞書を構築し、データを (辞書番号、リテラル) の組で符号化する。
目的
明示的な辞書によって普遍的な可逆圧縮を実現する。LZW の直接の前身である。
メカニズム
1 番から番号を振った辞書を維持し、入力を走査しながら辞書内にある最長の接頭辞を見つけて (番号、次の文字) を出力し、その接頭辞と文字を辞書に挿入する。辞書はオンラインで構築され、送信は不要である。
ユースケース
- LZWアルゴリズムの基礎
- 汎用のファイル圧縮
- 理論解析と教育での活用（teaching）