ハフマン符号

ハフマン符号とは、1952年にデビット・ハフマンによって開発された符号である。 コンパクト符号やエントロピー符号の一つ。 シャノン符号化が最適ではない場合が存在する不完全な符号であったのに対し、ハフマン符号は（整数の符号語長という制約のもとでは、）常に最適な符号を構成できる。 擬似的に実数の符号語長を割り振る算術符号と比較すれば、データ圧縮効率は劣る。

算術符号やその他の高効率の符号化法と異なり、特許の問題が無い。 そのため、JPEGやLHAなどの圧縮フォーマットで使用されている。

符号化の原理上、木を構成する前に各記号の出現頻度をあらかじめ知っておく必要がある。 1度目の読み込みで、データのすべての記号を調べておき、2度目に符号化を行う方法を、静的ハフマン符号と呼ぶ。 一方、1記号を読み込むごとに木を作り直し、1度の読み込みで符号化を行う方法を動的ハフマン符号と呼ぶ。

符号化の原理

データに出現する記号の個数を求める。 それが木構造の葉に相当すると見なし、ボトムアップで木を構成する。

まず、葉を含むすべての節点のうち、親を持たないものを集める。 その中から、最小の値をもつものと2番目に小さい値をもつものを取り出す。 それらを子供にもつ新しい節点を作る。 このとき、新しい節点の値は、両方の子供の値の和とする。

以上を繰り返して根節点まで到達して木が完成される。 次に、根から順に左右に0と1の値を割り振っていく（左右のどちらに0と1を与えるかは任意）。 すると、それぞれの葉（記号）に対して、一意にビット列が与えられる。 この記号とビット列の関係をもとに、もとのデータの記号をビット列に変換していくことで符号化が行われる。

例

ハフマン木

入力DAEBCBACBBBC に対して上記のアルゴリズムを適用すると、

出現頻度と割り当てられた符号

が得られ、個数の多い文字ほど短い符号が割り当てられていることがわかる。

関連項目

• シャノン符号化
• 接頭符号