ハフマン符号化 — 最小のビットで最も多くを語る

僕たちは毎日ネット上で画像や音声、テキストをやり取りしているが、これらのファイルは転送前にほぼすべて圧縮されている。圧縮はいったいどのように行われているのだろうか？なぜ圧縮後のファイルを元の姿に復元できるのだろうか？

JPEG圧縮に関する前回の記事で、僕たちはハフマン符号化がJPEG圧縮プロセスの最終ステップであることを紹介した。この記事では、ハフマン符号化そのものについてさらに深く掘り下げていきたい。

出現頻度と符号化

例えば、A、B、C、Dの4文字だけを含むテキストを送信するとしよう。最も直感的なやり方は、固定長の2進数符号を使うことだ：

文字	符号
A	00
B	01
C	10
D	11

1文字あたり2ビットで、明快そのものだ。しかし、もしAが1000回出現し、Dが1回しか出現しなかったらどうだろう？出現頻度がこれほど大きく異なる文字を同じ長さの符号で表すのは、なんだかもったいない気がする。

これこそがハフマン符号化が解決しようとした問題だ：

出現頻度の高い文字にはより短い符号を、出現頻度の低い文字にはより長い符号を割り当てる。

この考え方はモールス信号とよく似ている。英語で最も頻繁に出現する文字「E」はわずか1つのドット . で表されるのに対し、めったに出てこない「Q」は --.- という4つの記号を必要とする。

情報量とエントロピー

圧縮について議論する前に、まずひとつの問題を考えてみよう。ある事象の「情報量」は一体どうやって測るべきだろうか？

もし誰かが「明日、太陽は東から昇る」と教えてくれたとしても、何か新しいことを知った気にはならないだろう——この出来事はほぼ確実だからだ。しかし誰かが「明日は雹（ひょう）が降る」と言ったら、とても驚くだろう。その出来事が起きる確率は極めて低いからだ。

クロード・シャノン（Claude Shannon）は1948年に情報量の数学的定義を提唱した。発生確率が $p$ である事象の情報量（information content）は次のようになる：

I = -\log_2(p)

確率が低いほど、情報量は大きくなる。これは非常に直感的だ——予想外の出来事ほど、もたらす情報が多い。ある情報源のエントロピー（entropy）とは、すべての記号の平均情報量のことだ：

H = -\sum_{i} p_i \log_2(p_i)

エントロピーが教えてくれるのは、その情報源において、理論上各記号を符号化するのに平均して最小で何ビット必要かということだ。ハフマン符号化の優れた点は、この理論的下限に極めて近づけることにある。

ハフマン符号化のアルゴリズム

デイビッド・A・ハフマン（David A. Huffman）が1952年にこのアルゴリズムを発表した。アルゴリズム自体はかなり理解しやすく、実装も非常にシンプルだが、その効果は驚くべきもので、現代に至るまでハフマン符号化の姿を目にすることができる。

ステップ

頻度を集計する：各文字の出現回数を数える
優先度付きキュー（Priority Queue）を作成する：すべての文字を頻度の昇順（小さい順）に並べる
マージを繰り返す：頻度が最小の2つのノードを取り出し、新しいノード（頻度は両者の合計）にマージしてキューに戻す
ノードが1つになるまで繰り返す：残った最後のノードがハフマン木のルート（根）になる
符号テーブルを生成する：ルートから探索し、左へ進む場合は 0、右へ進む場合は 1 を記録する

実際にトレースしてみる

文字列 "aabbbcccc" を例にしてみよう：

Step 1 — 頻度を集計する：

a: 2, b: 3, c: 4

Step 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符号化では、 $9 \times 8 = 72$ ビット。ハフマン符号化後は、 $4 \times 1 + 2 \times 2 + 3 \times 2 = 14$ ビットになる。

なぜハフマン符号化はこれほど優れているのか

ハフマン符号化は接頭辞符号（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
}

インタラクティブツール：ハフマンエンコーダー

以下の入力欄に任意のテキストを入力して、ハフマン符号化の結果をリアルタイムで観察してみてほしい。符号テーブルの特定の文字にカーソルを合わせると、符号化結果の中で対応するビットがハイライト表示される。

ハフマンエンコーダーを読み込み中…

いろいろなテキストを入力して、いくつかの興味深い現象を観察してみよう：

1種類の文字だけのテキスト（aaaa など）を入力すると、各文字はわずか1ビットしか必要としない
すべての文字の頻度が同じテキストを入力すると、符号長は固定長に近づく
出現頻度の差が大きいテキストほど、圧縮率が高くなる

ハフマン符号化の限界

ハフマン符号化は万能ではなく、実用上いくつかの限界が存在する：

各記号に最低1ビット必要であること。 たとえある文字の理論的な最適符号長が0.3ビットだったとしても、ハフマン符号化では最低でも1ビットを割り当てるしかない。これは特定の極端な分布において効率の低下を招く。

事前に頻度を知る必要があること。 符号化の前にデータを一度スキャンして頻度を集計するか、事前に定義された頻度テーブルを使用する必要がある。JPEGでは標準仕様でデフォルトのハフマンテーブルが定義されているほか、カスタム設定も可能になっている。

符号テーブルを一緒に送信する必要があること。 デコード側でデータを復元するには符号テーブルを知る必要があるため、テーブル自体も容量を消費する。小さなデータの場合、テーブルのオーバーヘッドが圧縮の効果を打ち消してしまうこともある。

ハフマン符号化はどこで使われているのか？

JPEG — 画像圧縮の最終ステップがハフマン符号化である
DEFLATE（ZIP、gzip）— LZ77とハフマン符号化を組み合わせている
MP3 — 音声圧縮でもハフマン符号化が使われている
HTTP/2 — HPACKヘッダー圧縮で静的ハフマンテーブルが使用されている

おわりに

ハフマン符号化は、「理解してしまえば当たり前のように思える」類のアルゴリズムだ。その核となるアイデアは極めてシンプルで——頻出するものは短く表し、滅多に出ないものは長く表す。だが、この発想を汎用的なアルゴリズムへと昇華させるには、設計上の多くの創意工夫が必要だった。

70年以上が経った今でも、このアルゴリズムは僕たちが日々使っているさまざまなフォーマットの中で息づいている。

当時の彼らがもしAIのサポートを受けていたら、一体どうなっていただろうね？

カテゴリー

ページ

その他