ハフマン符号

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ハフマン符号(ハフマンふごう、Huffman coding)とは、1952年デビット・ハフマン英語版によって開発された符号で、文字列をはじめとするデータの可逆圧縮などに使用される。[1]

ほかのエントロピー符号と同様、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることで、メッセージ全体の符号化に使われるデータ量を削減することを狙っている。


符号化の原理[編集]

例として DAEBCBACBBBC という12文字からなるメッセージを考える。

このメッセージ中には5種類の文字が使われているので、もしそれぞれの文字を固定長のビット列で表すとすれば、1文字につき最低3ビット必要となる。

文字とビット列の対応表として、

  A   B   C   D   E
 000 001 010 011 100

を使い、それぞれの文字をビット列に置き換えたとすると、メッセージ全体は次のビット列で表される。

  D   A   E   B   C   B   A   C   B   B   B   C
 011 000 100 001 010 001 000 010 001 001 001 010

12文字 x 3ビットで全体のビット数は36ビットとなる。

もし、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることができれば、メッセージ全体の符号化に必要なビット数を抑えることが期待できる。そこで、文字とビット列の対応表として、

   A   B   C   D    E
  110  0  10  1110 1110

を使ったとすると、メッセージ全体は

   D   A   E   B  C B  A   C B B B  C
 1110 110 1110 0 10 0 110 10 0 0 0 10

となり、全体のビット数は25ビットとなる。 固定長の方式に比べると 70% ほどのデータ量に抑えられている。

ハフマン符号の構成[編集]

文字とビット列の対応表を作るには、まずデータに出現する文字の出現回数を求め、それをもとにハフマン木と呼ばれるバイナリツリーを構成するという手順を踏む。

ハフマン木の構成の仕方は次のようなアルゴリズムになる。

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

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

[編集]

ハフマン木

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

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

文字 個数 符号
B 5 0
C 3 10
A 2 110
D 1 1110
E 1 1111

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

接頭符号[編集]

ハフマン符号は接頭符号である。つまり、ある文字に対応するビット列が、他の文字に対応するビット列の接頭辞になることはない。この特徴のおかげで、デコーダはビット列を先頭から一度読むだけで元のメッセージを一意にデコードできる。

利用例[編集]

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

関連項目[編集]


  1. ^ .A. Huffman, "A method for the construction of minimum-redundancy codes" (PDF), Proceedings of the I.R.E., Sept. 1952, pp. 1098-1102 (ハフマンのオリジナル論文)