操作して学ぶ
圧縮アルゴリズム可視化
データ圧縮の基本は2つ。Huffman符号は「頻出する文字ほど短いビット列」を割り当て、LZ77は「過去に出た並びの繰り返し」を参照に置き換えます。 文字列を入れて、木の形やスライド窓の動きがどう変わるか試してください。
33
固定長 (3bit/字)
23
Huffman
30%
削減
符号表（頻出文字ほど短い）
a ×5 → 0b ×2 → 110r ×2 → 111c ×1 → 100d ×1 → 101
符号化されたビット列（23 bit）
01101110100010101101110頻度の低い2ノードを繰り返し併合して木を作る貪欲法。葉までの深さがそのままビット長になり、頻出文字が浅い＝短い符号になります。どの符号も他の符号の接頭辞にならない（接頭符号）ため、区切りなしで復号できます。
ここが要点
- Huffmanは貪欲法。頻度最小の2ノードを繰り返し併合するだけで、平均符号長が最適になる（接頭符号なので区切り不要で復号できる）。
- LZ77は辞書式。直前の一定範囲（窓）から最長一致を探し、(距離, 長さ, 次の文字) に置換。繰り返しに強い。
- 実際の deflate（gzip / zip / PNG）は両者の合わせ技。まず LZ77 で繰り返しを潰し、その出力を Huffman でさらに縮める。
- どちらも可逆圧縮。JPEGやMP3のような非可逆圧縮とは別物。