ハフマン符号 — 最小限の bit で最大限のデータ
# コンピュータ工学僕たちは毎日、ネット上で画像、音声、テキストを送っているが、これらのファイルは送信前にほとんど圧縮されている。圧縮は一体どうやって実現しているのだろうか？なぜ圧縮後のファイルを元の形に復元できるのだろうか？
前回の JPEG 圧縮についての記事では、ハフマン符号が JPEG 圧縮フローの最後のステップだと触れた。この記事では、ハフマン符号そのものについて、より深く掘り下げていきたい。
頻度と符号化
A、B、C、D の4文字だけからなる文章を送るとしよう。最も直感的な方法は、固定長の二進符号を使うことだ。
| 文字 | 符号 |
|---|---|
| A | 00 |
| B | 01 |
| C | 10 |
| D | 11 |
各文字 2 bits で、明快だ。だが、A が 1000 回現れて、D は 1 回しか現れないとしたらどうだろう。頻度に大きな差がある文字を同じ長さの符号で表すのは、どうにも無駄に思える。
これこそがハフマン符号が解決したい問題だ。
頻度の高い文字には短い符号を、頻度の低い文字には長い符号を割り当てる。
この考え方はモールス信号にかなり似ている。英語で最もよく使われる文字 E は . ひとつで表され、あまり使われない Q は --.- という4つの記号が必要だ。
情報量とエントロピー
圧縮の話をする前に、ひとつ考えたいことがある。ある事象の「情報量」は、どうやって測るべきなのだろうか？
誰かが「明日、太陽は東から昇る」と教えてくれたとしても、僕たちは何も新しいことを学んだ気にはならない。ほぼ確実だからだ。だが「明日はひょうが降る」と言われたら、かなり驚くだろう。起こる確率が非常に低いからだ。
Claude Shannon は 1948 年に情報量の数学的定義を提案した。発生確率が の事象の情報量（information content）は次のように表される。
確率が低いほど情報量は大きい。これは直感的だ。より意外な出来事ほど、より多くの情報をもたらす。あるメッセージ源のエントロピー（entropy）は、すべての記号の平均情報量である。
エントロピーが示すのは、このメッセージ源に対して、理論上、各記号を符号化するのに平均で最低何 bits 必要かということだ。ハフマン符号のすごさは、この理論的下限に非常に近づける点にある。
ハフマン符号のアルゴリズム
David A. Huffman がこのアルゴリズムを提案したのは 1952 年だ。当時彼は MIT の大学院生で、これは授業課題だった。教授の Robert Fano が「最も効率のよい二進符号化方法を見つけよ」という問題を出したのだ。Huffman は Fano と Shannon のトップダウン方式をそのまま使わず、逆にボトムアップで構築した。
このアルゴリズムは非常に理解しやすく、実装も簡単だが、効果は驚くほど大きい。
手順
- 頻度を数える：各文字の出現回数を計算する
- Priority Queue を作る：すべての文字を頻度の小さい順に並べる
- 繰り返し結合する：頻度の最小な2つのノードを取り出して、新しいノード（頻度は両者の和）にまとめ、キューへ戻す
- 1つだけ残るまで繰り返す：そのノードがハフマン木の根になる
- 符号表を生成する：根からたどり、左に進んだら
0、右に進んだら1を記録する
実際にたどってみる
文字列 "aabbbcccc" を例にする。
Step 1 — 頻度を数える：
a: 2, b: 3, c: 4Step 2 — 最小の2つを取り出して結合する：
a(2) + b(3) → ab(5)Step 3 — さらに最小の2つを取り出す：
c(4) + ab(5) → root(9)最終的なハフマン木：
(9)
/ \
0 1
c(4) (5)
/ \
0 1
a(2) b(3)符号表：
| 文字 | 符号 | 長さ |
|---|---|---|
| c | 0 | 1 |
| a | 10 | 2 |
| b | 11 | 2 |
元の ASCII 符号では、 bits。ハフマン符号化後は、 bits だ。
なぜハフマン符号はそんなに便利なのか
ハフマン符号は前綴り符号（prefix code）である。前綴り符号の定義は、どの符号も他の符号の前綴りにならないことだ。
例えば、A = 0、B = 01 だとすると、復号器が 01 を読んだとき、それが「A の後ろに 1 が続いている」のか、それとも「B」なのか判断できない。
ハフマン符号ではそんなことは起こらない。すべての文字が葉ノード上にあるからだ。根から任意の葉への経路は、別の経路の前綴りにはならない。この性質により、解析そのものも非常に簡単になる。すべての前綴り符号の中で、ハフマン符号は最短の平均符号長を生み出す。
コード実装
以下は JavaScript の実装だ。
function buildTree(freqMap) {
const nodes = [...freqMap.entries()]
.map(([char, freq]) => ({ char, freq, left: null, right: null }))
while (nodes.length > 1) {
nodes.sort((a, b) => a.freq - b.freq)
const left = nodes.shift()
const right = nodes.shift()
nodes.push({
char: null,
freq: left.freq + right.freq,
left,
right,
})
}
return nodes[0]
}
function buildCodeTable(node, prefix = '', table = {}) {
if (node.char !== null) {
table[node.char] = prefix || '0'
return table
}
buildCodeTable(node.left, prefix + '0', table)
buildCodeTable(node.right, prefix + '1', table)
return table
}buildTree は毎回最小の2つを取り出して結合し、1つの根ノードだけが残るまで続ける。buildCodeTable は根から再帰的にたどり、左へ進むたびに 0 を、右へ進むたびに 1 を追加する。
復号の過程も直感的だ。根ノードから始め、0 を読んだら左へ、1 を読んだら右へ進み、葉ノードに到達したら対応する文字を出力し、また根へ戻って続ける。
function decode(encoded, root) {
let result = ''
let current = root
for (const bit of encoded) {
current = bit === '0' ? current.left : current.right
if (current.char !== null) {
result += current.char
current = root
}
}
return result
}インタラクティブ：ハフマン符号エンコーダ
下に任意のテキストを入力して、ハフマン符号化の結果をリアルタイムで観察してみよう。符号表のある文字にマウスを乗せると、符号結果中の対応する bits がハイライトされる。
さまざまなテキストを入力して、いくつかの興味深い現象を観察してみよう。
- 1 種類の文字しかないテキスト（例:
aaaa）を入力すると、各文字に必要なのは 1 bit だけだ - すべての文字の頻度が同じテキストを入力すると、符号長は固定長に近づく
- 頻度差が大きいテキストほど、圧縮率は高くなる
ハフマン符号の限界
ハフマン符号は万能ではなく、実務上いくつかの制約がある。
各記号は少なくとも 1 bit 必要だ。 たとえある文字の理論上の最適符号長が 0.3 bits でも、ハフマン符号は最低でも 1 bit しか割り当てられない。これは極端な分布では効率の損失につながる。
事前に頻度を知る必要がある。 符号化の前に一度データを走査して頻度を集計するか、あらかじめ定義された頻度表を使う必要がある。JPEG では標準でデフォルトのハフマン表が定義されており、カスタム表も許可されている。
符号表も一緒に送る必要がある。 復号側はデータを復元するために符号表を知っていなければならないので、符号表自体にも空間が必要だ。小さなデータでは、符号表のオーバーヘッドが圧縮の利点を打ち消すこともある。
ハフマン符号はどこで使われているのか
- JPEG — 画像圧縮の最後のステップがハフマン符号化だ
- DEFLATE（ZIP、gzip）— LZ77 とハフマン符号化を組み合わせている
- MP3 — 音声圧縮でもハフマン符号が使われている
- HTTP/2 — HPACK のヘッダ圧縮では静的ハフマン表が使われる
後記
ハフマン符号は、「理解した瞬間に当然だと思える」タイプのアルゴリズムだ。その核心は極めて単純で、よく出るものは短く、まれなものは長く表す。ただし、この発想を汎用アルゴリズムに落とし込むには、多くの設計上の工夫が必要になる。
70年以上が過ぎた今でも、このアルゴリズムは僕たちが毎日使うさまざまなフォーマットの中で生き続けている。
この人たちが AI の補助を得たら、いったいどうなっていたのだろうか。