|
ハフマン符号 Huffman code |
|
ハフマン符号は情報圧縮における可逆符号（正確に復号できる符号）です。 画像や音声の情報圧縮では、まず非可逆圧縮を行い、残った規則的な（人間が理解可能な）対象に対して、可逆符号による圧縮を実施します（情報圧縮を参照）。 無記憶情報源のいかなる復号可能符号の平均符号長も、その情報源のエントロピー以下にすることはできないことは符号とエントロピーで説明しました。 では、復号可能な符号のなかで、 その符号は、瞬時復号可能な符号の中から見つかり、ハフマン (David.A.Huffman, 1925-1999) がその設計法を示しました。 どの符号語も他の符号語の接頭語になっていない符号は瞬時的に復号可能です。 このような符号は、視覚的に分かりやすい構造をもっています。 下図のように、２本の枝分かれを繰り返す木グラフ（tree graph）を見てください。 左端の根っこから、２本の分枝に“０”と“１”のビットを割り付けてゆきます。 そして、図のように枝の先端（右端の行き止まり）に符号語を割り付けてみます。 符号語は、根っこからその先端まで、枝のビット（０ か１ ）を順々に読み取ったものです。 このような符号語の集まりは、互いに接頭語になっていません。 すなわち、かならず瞬時復号可能です。
先端の符号語は根っこに近ければ近いほど符号長が短いので、できるだけ根っこに近いところで符号を割り付ければ能率の良い（平均符号長の短い）符号が設計できます。 もう少し具体的な例を設計してみましょう。 ４つのアルファベット（Ａ、Ｂ、Ｃ、Ｄ）を出力する無記憶情報源を考えてください。 それらの出現確率を
で与えられます。 ハフマンは、アルファベットとその出現確率が与えられたとき、もっとも平均符号長の短い瞬時復号可能符号の設計法を見つけました。 その方法を８つのアルファベットを出力する無記憶情報源で説明します。 下図を参照しながら、アルゴリズムをたどってみてください。左端（２分岐木グラフの端点）から右へ、合流操作を行います。
この手順によって作られた符号は瞬時復号可能になっていますが、実は非瞬時・瞬時を意識しないでも、このようにして作った符号の平均符号長は最短になっていることがいえるのです。 一般に復号可能な最短の符号をコンパクトであるといいますが、ハフマン符号はコンパクトなのです。 その理由は以下のように考えてみれば、すぐに分かります。 二つのアルファベットを合流するということは、そのどちらが発生しても一つの新しいアルファベットとして読むということですから、アルファベットが一つ減ります。合流にともない、符号長も１ビット減るので、平均符号長はそれぞれのアルファベットの確率を
上の例題を８つの会社を二つずつ合併してゆき、最後に一つの会社に統合する問題に置き換えて考えてみます。 合併によって合併損が生じ、全部を統合し終えたときに、合併損のトータルが最小になるようにしたいのです。 合併したときに出す損を確率の値とし、たとえばＡ社とＢ社を合併すると、それらの確率の和
０．５＋０．２＝０．７ なる損を発生するとします。 その結果、合併損 ０．７
をもつ新会社と、合併しなかった会社６つ、あわせて７つの会社が残ります。 これら７社から、また二つを選んで合併し、新会社を作ってゆきます。 どのような順序で合併しても、統合が終わるまでの合併の回数はちょうど７回です。 ただし、合併損のトータルは合併の順序によって異なります。下の例を見てください。 合併劇（１）：トーナメント試合のように合併する。 A+B=0.5+0.2=0.7 C+D=0.1+0.08=0.18 E+F=0.05+0.04=0.09 G+H=0.02+0.01=0.03 (A+B)+(C+D) =0.7+0.18=0.88 (E+F)+(G+H) =0.09+0.03=0.12 ((A+B)+(C+D))+((E+F)+(G+H)) =0.88+0.12=1.0 トータル合併損（平均符号長） =0.7+0.18+0.09+0.03+0.88+0.12+1.0= 3 合併劇（２）：ハフマンの手順にしたがった場合 H+G=0.02+0.01=0.03 (H+G)+F =0.03+0.04=0.07 ((H+G)+F)+E =0.07+0.05=0.12 C+D =0.1+0.08=0.18 ((((H+G)+F)+E)+(C+D) =0.12+0.18=0.3 ((((H+G)+F)+E)+(C+D))+B=0.3+0.2=0.5 (((((H+G)+F)+E)+(C+D)+B)+A =0.5+0.5=1.0 トータル合併損（平均符号長）＝0.03+0.07+0.12+0.18+0.3+0.5+1.0= 2.2 この例から分かるように、早めに合併損の小さな２社を選んで合併すれば、トータル合併損を最小にできます。 すなわち、A社に着目すると、A社が関わる合併の度にA社の確率がカウントされます。 したがって、A社の確率が大きいとき、A社が関わる合併の回数をできるだけ少なくする方が得策なわけです。 A社が関わる合併の回数はアルファベットA の符号長に相当しますから、合併劇のトータル合併損はまさに平均符号長に等しいわけです。 以上の符号化では、アルファベットごとにハフマン符号を割り付けました。 この平均符号長はまだエントロピーの限界に達していません。 上で得られたハフマン符号の平均符号長は 2.2 ビットです。 一方、この情報源のエントロピーは 2.17 ビットです。 両者の差は 0.03 ビットです。 この差をさらに縮めるには、情報源を拡大してハフマン符号を作ってゆきます。 たとえば、２次拡大情報源 （２文字綴りを出力すると見做す）のシンボルは、ＡＡ、ＡＢ，…、ＨＨ の全部で６４ 個です。 これら２文字綴りの出現確率はそれぞれ、
で計算されます。 このように拡大された情報源に対して、ハフマン符号を設計すると、その平均符号長はさらにエントロピーに近くなることがいえます。 そして、この拡大をどんどん行ってゆくと、最後にはエントロピーに無限に近い符号を作ることができます。 このことを保証する事実は、第１に、次の定理が成り立つこと、 定理 注１： i
番目のアルファベットの生起確率を 第２に、次の定理が成り立つこと、 定理 注２： ０と１を出力する２元情報源を考える。 生起確率を
から導くことができます。 すなわち、ｎ次拡大の平均符号長
を満たす瞬時復号可能な符号がかならず存在することがいえ、その中でハフマン符号がもっとも良い（コンパクトな）符号になっています。 このように、ｎ
を大きくしてハフマン符号を設計すれば、元の情報源の１アルファベット当りの平均符号長
実際に２値無記憶情報源を拡大してハフマン符号を設計し、上の不等式を構成する３つの項をプロットしてみよう。 二つのシンボル”１”と”０”が出力されるとし、”０”の生起確率が
p=0.1 と p=0.2 の場合についてプロットしてみます。 黒が
注３： 上の図から分かるように、ハフマン符号の圧縮率（ビット／シンボル）は、情報源の拡大に対して単調減少とは限りません。 注４： 音声や画像などの圧縮では、ハフマンを適用する前に、聴覚や視覚の特性を利用した不可逆圧縮を実行しています。その理由は、最初から音声にハフマンを適用しようとすると、ＰＣＭ信号（８ＫＨｚサンプリングで８ビットＡＤＣ）を１０ミリ秒ごとに切り取って処理するとして、のサンプル数＝８０、量子化レベル数＝２５６、なので、符号語の数は２５６の８０乗という膨大な数になります。というわけで、符号語数を音声の特徴を使って減らそうというわけです。不可逆圧縮によって残った符号語のエントロピーが大きい（規則性が小さい）と、ハフマンの圧縮効果は小さくなり、逆に小さい（規則性が大きい）と、ハフマンの圧縮効果は大きくなります。聴覚や視覚の特徴を当てにしないで、符号語をクラス分けして、階層的なハフマン符号を構成することができないのかなー？と疑問に思っていますが、私は専門ではないので、これ以上のコメントはできません。 |
そして割り付けられた符号語の長さを 
とします。 すると、この符号の平均符号長は
とすると、 
だけ減ることになります。どのような順序で合流しても、最終段階の合流ではかならず平均符号長の減少量は
１（確率の総和は１）です。ただし、平均符号長は各合流段階での平均符号長の減少をトータルした値になることを理解してください。 したがって、合流のたびに生ずる平均符号長の減少の総和がもっとも小さくなるように合流順序を選べばよいことが分かります。 ハフマン符号はこの合流順序を実現しますが、もう少し分かりやすい例で説明してみましょう。
とする。 
の少数点以下を切り上げた整数を i 番目のアルファベットの符号長とする。 この結果はクラフトの不等式を満たすので瞬時復号可能な符号が必ず見つかる（
で表すと、
および 
とする。 この２次拡大は、００、０１、１０、１１の４つを出力し、これらの確率は
である。 このエントロピーが元の情報源のエントロピーの２倍、すなわち 
になることを確認してみよう。 一般的証明は、この計算を一般化して得られる。
が
をかぎりなく真のエントロピー 
に近づけることができるというわけです。
、オレンジが
、紫が
を表しています。 横軸は拡大次数ですが、左端の n=1 は確率を考慮しない等長符号に相当します。 それぞれの図の下に、n=4
の場合のハフマン符号を示します。
