ハフマン符号化における貪欲法
1. 背景と導入
はじめて「貪欲法（たんよくほう）」という名前を聞くと、「なんだか賢くなさそうだな」と感じるかもしれません。
貪欲法では各ステップで「最も良さそうな」局所的な決定を行い、動的計画法のような広範囲の検討をしないからです。
しかし、ハフマン符号化（Huffman Coding）は、その貪欲な方法で最適解を得られる代表的な例として、とても有名です。
ここではまず「貪欲法とは何か」をかんたんに説明し、その後に「ハフマン符号化とは何か」を結びつけて、
「なぜ毎回、重みが最小の2つの部分木を合体すれば最適な符号化が得られるのか」を直感的に理解してもらいます。
2. 貪欲法（Greedy Algorithm）とは？
貪欲法（Greedy Algorithm） とは、問題を解く各段階で「最適と思われる」局所的な選択を行い続ける手法です。特徴は以下の2点です：
- 局所最適：問題を解く途中の小さなステップですべて、可能な限り最良の（＝局所的に最適な）選択を行う。
- 後戻りしない：いったん意思決定した内容を再度見直したり、修正したりしない。
このように貪欲法はシンプルに実装しやすい反面、問題によってはグローバルには最適解を得られない場合もあります。
しかし、たとえば「区間スケジューリング」「活動選択問題」やここで紹介する「ハフマン符号化」では、
貪欲法がグローバルに見ても最適解を与えることが証明されています。
3. ハフマン符号化（Huffman Coding）の復習
ハフマン符号化は、ファイル圧縮やデータ通信でよく使われる可変長符号化法です。目的は：
- 文字（シンボル）ごとに出現頻度が異なる場合、頻度の高い文字ほど短いビット列で符号化し、
頻度の低い文字はやや長いビット列を使うことで、全体の平均ビット長をできるだけ短くすること。 -
接頭辞コード（prefix-free code） を満たす：ある文字の符号列が、別の文字の符号列の先頭部分になってはいけない。
（そうでないとデコード時にあいまいさが生じる。） - 実際には、文字それぞれを葉ノードとする**ハフマン木（ハフマンツリー）**を構築し、
根から葉への0/1のパスが文字のビット列になるようにする。
たとえば、以下のような例を考えます：
- A … 出現頻度 40%
- T … 出現頻度 40%
- C … 出現頻度 10%
- G … 出現頻度 10%
直感的に、AやTなど頻度の高い文字には短いビット列を、
CやGのような頻度の低い文字は少し長いビット列を割り当てると、全体の符号長が減らせます。
4. ハフマン符号化の貪欲な発想──「最小の2つを合体」
ハフマン符号化のコアとなるステップは、以下のように説明できます：
- 各文字を単体ノードの木として用意する。ノードの「重み」は、その文字の出現頻度（または確率）。
-
重みが最小の2つの木を選び出し、それらを一つの木に合体する。
新しい木の根の重みは、2つの子木の重みの合計。合体した木を再び集合に戻す。 - これを繰り返し、最終的に集合に木が1本だけ残ったら、それがハフマン木になる。
ここが貪欲法の鍵です：「現時点で一番小さい（=あまり重要ではない）ノードどうしを先に合体させる」
つまり「頻度の低い文字ほど深い位置（長いビット列）になりやすく、
頻度の高い文字は深くならずに済む（短いビット列で表現できる）」という効果を狙っています。
これはまさに「局所最適を積み重ねる」アプローチであり、結果的に平均符号長を最小化します。
5. 具体例：Pythonコードで見るハフマン符号化
以下は、Pythonの heapq モジュール（最小ヒープ）を使って、
「ハフマン符号化」を貪欲法で実装する簡易サンプルです。
import heapq # Pythonの最小ヒープを扱うライブラリ
def huffman_encoding(freqs):
"""
freqs: {'A': 40, 'T': 40, 'C': 10, 'G': 10} のように、
文字とその出現頻度（あるいは確率）を持つ辞書。
戻り値: 例として {'A': '11', 'T': '0', 'C': '101', 'G': '100'} などを返す。
"""
# (1) 初期化：各文字を (重み, 一意ID, 文字/ノード) としてヒープにプッシュ
heap = []
unique_id = 0
for char, weight in freqs.items():
heapq.heappush(heap, (weight, unique_id, char))
unique_id += 1
# (2) ヒープから最小の2要素を取り出し、新しいノードにまとめて再びヒープへ
while len(heap) > 1:
w1, id1, left = heapq.heappop(heap)
w2, id2, right = heapq.heappop(heap)
new_node = (left, right) # 新しいノード（部分木）
new_weight = w1 + w2 # 合計重み
heapq.heappush(heap, (new_weight, unique_id, new_node))
unique_id += 1
# (3) ヒープに残った1つが全体のハフマン木
_, _, huffman_tree = heap[0]
# (4) 木を再帰的に探索して符号を割り当て
codes = {}
def traverse_tree(node, prefix):
if isinstance(node, str):
# node が文字であれば、葉ノード
codes[node] = prefix
return
left_subtree, right_subtree = node
traverse_tree(left_subtree, prefix + "0")
traverse_tree(right_subtree, prefix + "1")
traverse_tree(huffman_tree, "")
return codes
# 実行例
if __name__ == "__main__":
freqs = {'A': 40, 'T': 40, 'C': 10, 'G': 10}
result = huffman_encoding(freqs)
print("ハフマン符号:", result)
上記のコードでは「毎回、（重みが）最小の2ノードを取り出す → 新ノードでまとめる → 戻す」を繰り返して、
木を1本にまとめています。これが局所最適を積み重ねる、貪欲法の典型的なパターンです。
6. なぜ貪欲法で最適解が得られるのか？
ここでは、簡単なイメージとして以下の2点を押さえてください：
-
頻度が小さい（あまり使われない）文字ほど深い位置に置く方が、全体的にビット総数が減る。
頻度の低い文字が長いビット列になっても、出現回数が少ないため、全体への影響が小さい。
一方で、頻度の高い文字は木の上の方（深さが小さい位置）になり、短い符号を得られるようになる。 -
「交換引数法（Exchange argument）」や木の深さの議論などを用いた形式的な証明により、
「最小2ノードを繰り返し合体させる」戦略こそが平均符号長を最小にする**最適前置符号（prefix-free code）**を構築する方法であることが示されます。
7. どんな応用があるの？
- ファイル圧縮：テキストファイル内で頻繁に使われる文字を短い符号にし、ファイルサイズを小さくできる。
- ネットワーク通信：高頻度のシンボルを短いビット列で表すことで、送信量を減らし、通信効率を上げる。
- 画像・音声コーデック：JPEGやMP3などの変換処理の最後の段階で、ハフマン符号による可変長エンコードを使う場合がある。
8. まとめ
- 貪欲法：各ステップで最適そうな選択を行い、後からの修正はしない。
- ハフマン符号化：出現頻度の低い文字を深い位置に置き、高頻度文字は浅い位置に置くことで、全体のビット平均長を減らす。
- 証明の概略：ハフマン符号は「最も重みの小さい2つの要素を合体する」戦略で最適前置符号を構築できることが数学的に示されている。
結果として、ハフマン符号化は貪欲法で最適解を得られる典型例です。
「すべての問題に貪欲法が通用するわけではない」一方、このように問題の構造がうまく合致すると、
シンプルかつ効率的に最小の平均符号長を達成できるのです。