ハフマン符号化における貪欲法

# ハフマン符号化における貪欲法

## 1. 背景と導入

はじめて「貪欲法（たんよくほう）」という名前を聞くと、「なんだか賢くなさそうだな」と感じるかもしれません。  
貪欲法では各ステップで「最も良さそうな」局所的な決定を行い、動的計画法のような広範囲の検討をしないからです。  
しかし、**ハフマン符号化（Huffman Coding）**は、その貪欲な方法で**最適解**を得られる代表的な例として、とても有名です。

ここではまず「**貪欲法とは何か**」をかんたんに説明し、その後に「**ハフマン符号化とは何か**」を結びつけて、  
「なぜ毎回、重みが最小の2つの部分木を合体すれば最適な符号化が得られるのか」を直感的に理解してもらいます。


## 2. 貪欲法（Greedy Algorithm）とは？

**貪欲法（Greedy Algorithm）** とは、問題を解く各段階で「最適と思われる」局所的な選択を行い続ける手法です。特徴は以下の2点です：

1. **局所最適**：問題を解く途中の小さなステップですべて、可能な限り最良の（＝局所的に最適な）選択を行う。  
2. **後戻りしない**：いったん意思決定した内容を再度見直したり、修正したりしない。

このように貪欲法はシンプルに実装しやすい反面、問題によってはグローバルには最適解を得られない場合もあります。  
しかし、たとえば「区間スケジューリング」「活動選択問題」やここで紹介する「ハフマン符号化」では、  
貪欲法がグローバルに見ても最適解を与えることが証明されています。


## 3. ハフマン符号化（Huffman Coding）の復習

**ハフマン符号化**は、ファイル圧縮やデータ通信でよく使われる可変長符号化法です。目的は：

- 文字（シンボル）ごとに出現頻度が異なる場合、頻度の高い文字ほど短いビット列で符号化し、  
  頻度の低い文字はやや長いビット列を使うことで、全体の平均ビット長をできるだけ短くすること。
- **接頭辞コード（prefix-free code）** を満たす：ある文字の符号列が、別の文字の符号列の先頭部分になってはいけない。  
  （そうでないとデコード時にあいまいさが生じる。）
- 実際には、文字それぞれを葉ノードとする**ハフマン木（ハフマンツリー）**を構築し、  
  根から葉への0/1のパスが文字のビット列になるようにする。

たとえば、以下のような例を考えます：

> - **A** … 出現頻度 40%  
> - **T** … 出現頻度 40%  
> - **C** … 出現頻度 10%  
> - **G** … 出現頻度 10%

直感的に、AやTなど頻度の高い文字には短いビット列を、  
CやGのような頻度の低い文字は少し長いビット列を割り当てると、全体の符号長が減らせます。

## 4. ハフマン符号化の貪欲な発想──「最小の2つを合体」

ハフマン符号化のコアとなるステップは、以下のように説明できます：

1. **各文字を単体ノードの木として用意する**。ノードの「重み」は、その文字の出現頻度（または確率）。  
2. **重みが最小の2つの木を選び出し、それらを一つの木に合体する**。  
   新しい木の根の重みは、2つの子木の重みの合計。合体した木を再び集合に戻す。  
3. これを繰り返し、最終的に集合に木が1本だけ残ったら、それが**ハフマン木**になる。

ここが**貪欲法の鍵**です：「現時点で一番小さい（=あまり重要ではない）ノードどうしを先に合体させる」  
つまり「頻度の低い文字ほど深い位置（長いビット列）になりやすく、  
頻度の高い文字は深くならずに済む（短いビット列で表現できる）」という効果を狙っています。  
これはまさに「局所最適を積み重ねる」アプローチであり、結果的に平均符号長を最小化します。


## 5. 具体例：Pythonコードで見るハフマン符号化

以下は、Pythonの `heapq` モジュール（最小ヒープ）を使って、  
「ハフマン符号化」を貪欲法で実装する簡易サンプルです。

```python
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点を押さえてください：

1. **頻度が小さい（あまり使われない）文字ほど深い位置に置く方が、全体的にビット総数が減る。**  
   頻度の低い文字が長いビット列になっても、出現回数が少ないため、全体への影響が小さい。  
   一方で、頻度の高い文字は木の上の方（深さが小さい位置）になり、短い符号を得られるようになる。

2. **「交換引数法（Exchange argument）」や木の深さの議論**などを用いた形式的な証明により、  
   「最小2ノードを繰り返し合体させる」戦略こそが平均符号長を最小にする**最適前置符号（prefix-free code）**を構築する方法であることが示されます。

---

## 7. どんな応用があるの？

- **ファイル圧縮**：テキストファイル内で頻繁に使われる文字を短い符号にし、ファイルサイズを小さくできる。  
- **ネットワーク通信**：高頻度のシンボルを短いビット列で表すことで、送信量を減らし、通信効率を上げる。  
- **画像・音声コーデック**：JPEGやMP3などの変換処理の最後の段階で、ハフマン符号による可変長エンコードを使う場合がある。

---

## 8. まとめ

- **貪欲法**：各ステップで最適そうな選択を行い、後からの修正はしない。  
- **ハフマン符号化**：出現頻度の低い文字を深い位置に置き、高頻度文字は浅い位置に置くことで、全体のビット平均長を減らす。  
- **証明の概略**：ハフマン符号は「最も重みの小さい2つの要素を合体する」戦略で最適前置符号を構築できることが数学的に示されている。

結果として、**ハフマン符号化は貪欲法で最適解を得られる典型例**です。  
「すべての問題に貪欲法が通用するわけではない」一方、このように問題の構造がうまく合致すると、  
シンプルかつ効率的に最小の平均符号長を達成できるのです。