3 ハフマン木とハフマン符号

ハフマン木とハフマン符号を直感的に理解し、ハフマン符号が最適な可変長符号であることを証明します。

コース内容#

前提知識#

コードとは何か
- コードについて最初に聞いたのはどこですか？ASCII コード
  - 'a' = (97)10 = (0110 0001)2
  - '0' = (48)10 = (0011 0000)2
  - 8 ビットの二進数コード、一バイト
- 注意：コンピュータでは、すべての情報は二進数で保存されています
- コードの役割：人間の文字をコンピュータの文字にマッピングすること
例：コードの長さがもたらす影響
- コンピュータにある情報："aa00"、そのASCII コードは：01100001 01100001 00110000 00110000
- この時、その情報を一台のコンピュータから別のコンピュータに転送します
  - ネットワークでは、最小の転送単位はビット [bit] なので、"aa00" は 32 ビットを転送する必要があります
- 仮定：あるコンピュータのネット速度は 32bit/s なので、所要時間は：1s
- 👇
- 特殊なシナリオに変換：a、b、0、1 の 4 種類の文字のみを転送する必要があります
- 新しい符号化方式を設計できます [海賊班符号 - 定長符号]
  - 2 ビットの二進数で区別します ——a: 00、b: 01、0: 10、1: 11
- この時、"aa00" の表現は 8 ビットのみで済みます
- したがって、ネット速度が変わらない場合、現在の転送にかかる時間はわずか：0.25s
- [PS] テンセント会議と比較して、Zoom の符号化と復号化はより精密で、同じネット速度で Zoom の体験がより良いです。

定長と可変長符号#

定長符号 —— 各文字の符号長が同じ
- ASCII コードと特定のシナリオでの海賊班符号は、どちらも定長符号に属します
- [PS] UTF-8— 可変長符号；UTF-16— 定長符号 [独学]
可変長符号 —— 各文字の符号長が異なる
可変長符号は、必ず定長符号よりも劣らない
- 定長符号は可変長符号の特例です
【引き延ばし理解】
- 可変長符号は定長符号であることもあります
- 可変長符号は特定のシナリオに対して最適化する必要があります [転送文字の出現確率は事前に統計を取る必要があります]
- コードはプロトコルと見なすことができ、事前に規定されており、動的に変化することはできません
- 符号化と復号化は一貫している必要があります

可変長符号の適用シナリオ#

特定のシナリオ
- 4 種類の文字のみ：ab01
- 各文字の出現確率が異なる ——a: 0.8、b: 0.05；0: 0.1；1: 0.05
平均符号長
- avg(l) = ∑ li × pi
- li：第 i 種の文字の符号長
- pi：第 i 種の文字の出現確率
- 実際には符号長の期待値です
- 例
  - 平均符号長が 1.16 と仮定すると、100 文字を転送するには 116 ビットを転送する必要があります [推定]
  - 海賊班符号 [上記参照] の平均符号長：avg (l) = 2 × ∑ pi = 2
    - 定長符号の平均符号長は定長です
新しい・海賊班符号
- a：1
- b：01 [注意：1 で始めることはできません、なぜなら復号化時に a と衝突するからです、❌接頭辞の重複]
- 0：000
- 1：001
- この時、平均符号長：1 * 0.8 + 2 * 0.05 + 3 * 0.1 + 3 * 0.05 = 1.35
- したがって、100 文字を転送するには 135 ビットを転送するだけで済みます [推定]
[PS] 確率が大きい文字は、より短い符号長に対応します

ハフマン符号#

各文字の確率を統計的に取得します
n 個の文字を使ってハフマン木を構築します
各文字は葉ノードに配置されます [接頭辞の重複はありません]
左 0、右 1 の形式で符号を読み取ります

木の構築の例
- 木の構築プロセスの口訣：毎回確率が最小の 2 つの文字をノードとして取り出し、1 つのサブツリーを合成します [新しいノードを生成]
- ⭐すべての文字が葉ノードに配置されるため、他の文字の符号の接頭辞にはなりません
  - 衝突はありません
- この時、平均符号長は 1 * 0.8 + 3 * 0.05 + 2 * 0.1 + 3 * 0.05 = 1.3 です
結論：ハフマン符号は最適な可変長符号です [以下に証明を示します]
[PS]
- 主に長さに注目し、01 の左右にはあまり注目しません
  - 注目する場合は、0 と 1 の転送コストのどちらが高いかを考慮します
- ハフマン木は一意ではなく、確率が等しい場合は順序は自由です
- ハフマン符号も定長符号に退化することがあります [同様に、例えば 4 つの等確率 (0.25) の文字を符号化する場合]

ハフマンの最適性の証明#

[可変長符号の大御所、最適とは平均符号長が最小であることを指します]

ステップ：① 平均符号長の表現を変換する；② 最適解を求める公式を解く

思考の変換#

ハフマン符号化プロセスにおいて、赤いノードが文字に対応している場合、下の 4 つの葉ノードはすべて切り落とされる必要があります
そうでなければ、衝突が発生します
[直感的にも事実です] ハフマン符号はすべての葉ノードをカバーします
4 つの文字があると仮定し、その符号化結果は以下の通りです [赤いノード]
- 高さが H [0 から始まる] の木において、第 l 層のノードがカバーする葉ノードの数は 2 ^ (H - l) です
  - 第 l 層の l は実際には符号長を表しています
  - 上に行くほどカバーするノードの数が多く、下に行くほどその逆です
👇
第 i 文字の符号長 [左] と対応するノードがカバーする葉ノードの数 [右] との間にはマッピングがあります：
- li → 2 ^ (H - li)

隠れた制約条件#

2 番目の式の左右を同時に 2 ^ H で割ります
[PS] ハフマン木の 2 行目の式は必ず等号ですが、急いではいけません

証明目標の変換#

平均符号長 Σ pi * li を最小にする、li = -li'
制約は上記の木構造から来ます [つまり隠れた制約条件]
さらに Ⅰi = 2 ^ li' とします
つまり、目標と制約を再度変換します
【変換結果】
- 目標：-(p1logⅠ1 + p2logⅠ2 + p3logⅠ3 + ... + pnlogⅠn) を最小にする
- 制約：Ⅰ1 + Ⅰ2 + Ⅰ3 + ... + Ⅰn <= 1
[PS]
- エントロピーに似ていますか？実際にはエントロピーの観点から証明し、交差エントロピーの概念を引き出すこともできます
- 変換は何のためですか？
  - 制約条件の等号成立と目標最小の関係を導き出すため
  - もう一つの制約条件：確率の合計は 1 です

制約条件の再縮小#

証明：目標関数が最小に達するとき、制約条件は必ず = 1 です
反証法：つまり制約条件 < 1
- 1 - ∑Ⅰi = Ⅰx' とし、これは負でない [制約条件を見て]
- Ⅰx' は任意の項に加えることができます
- Ⅰx' が 0 でない限り、目標関数は必ず最小ではなく、さらに小さくできます
- したがって、制約条件は必ず = 1 です

偏導関数が 0 になると極値を得る#

未知数を 1 つ減らします：Ⅰn = 1 - Ⅱ
目標が最小値に達するのはいつか：偏導関数を求めます
- 偏導関数を求めると左側の式が得られます
- つまり右上の式が成立する時、目標は最小値に達することができます
- p1/Ⅰ1 = ... = k とし、制約条件と確率の合計が 1 であることから 2 つの条件が得られ、k = 1 が得られます
- ⭐したがって pi = Ⅰi です

❗ 考察#

平均符号長とエントロピー、交差エントロピーの関係

pi = Ⅰi
- Ⅰi は符号長 li に関連しており、確率と長さは密接に関連しています
  - 確率が大きいほど、符号長は短くなります
- 等式を代入すると、【エントロピー】の公式が得られます
  - 実際、エントロピーはシステム内で情報を表現するために必要な最小の平均表現単位を表します
  - 同様に、平均符号長として理解することもできます [⭐思想がつながっています]
  - 平均符号長が長くなるほど → システム内の文字数が増える → システムの状態が増える → システムがより混乱する
  - エントロピーが大きいほど、システムの符号化がより混乱します
- 【交差エントロピー】
  - pi と Ⅰi を一組の確率と見なします
  - これは 2 つの確率ベクトルの類似度を表します
実際、証明はまだあまり厳密ではありません
- なぜなら、ハフマンプロセスは実際には離散的であり、この証明プロセスは連続的だからです
- 例えば：pi = Ⅰi、Ⅰi から算出された符号長 li は小数かもしれませんが、符号長 li は実際には整数であることが確実です。

コードデモ#

ハフマン木#

構造は木に基づいています
【重要な操作】
- ノードを結合し、ノード間の関係を構築できます [配列とノードの関係の変換]
- 最小の 2 つの確率を見つけます [優先キューを利用して最適化可能]
- 符号を再帰的に抽出します [葉ノードのみが文字の符号に対応します]
- データを読み込む際は、文字配列を使用して文字を保存することをお勧めします。これにより、エラー率を減少させることができます。

追加知識#

コンピュータにおける最も基本的 [最小] な保存単位はバイトであり、最も基本的 [最小] なデータ表現単位はビットです。

考察点#

ハフマンが最適符号である他の証明方法は？
- 058 ハフマンアルゴリズムの正しさの証明——Coursera
- 最も簡単なハフマン木が最適な二分木である証明方法——Zhihu

ヒント#

数学的知識がコンピュータの方向性の上限を決定します