ハフマン符号（ハフマンふごう、Huffman coding）とは、1952年にによって開発された符号で、文字列をはじめとするデータの可逆圧縮などに使用される。ほかのエントロピー符号と同様、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることで、メッセージ全体の符号化に使われるデータ量を削減することを狙っている。例として DAEBCBACBBBC という12文字からなるメッセージを考える。このメッセージ中には5種類の文字が使われているので、もしそれぞれの文字を固定長のビット列で表すとすれば、1文字につき最低3ビット必要となる。文字とビット列の対応表として、を使い、それぞれの文字をビット列に置き換えたとすると、メッセージ全体は次のビット列で表される。12文字 x 3ビットで全体のビット数は36ビットとなる。もし、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることができれば、メッセージ全体の符号化に必要なビット数を抑えることが期待できる。そこで、文字とビット列の対応表として、を使ったとすると、メッセージ全体はとなり、全体のビット数は25ビットとなる。固定長の方式に比べると 70% ほどのデータ量に抑えられている。文字とビット列の対応表を作るには、まずデータに出現する文字の出現回数を求め、それをもとにハフマン木と呼ばれるバイナリツリーを構成するという手順を踏む。ハフマン木の構成の仕方は、次のようなアルゴリズムになる。以上を根節点に到達するまで繰り返すと、木が完成する。次に、根から順に左右に0と1の値を割り振っていく（左右のどちらに0と1を与えるかは任意）。すると、それぞれの葉（記号）に対して、一意にビット列が与えられる。この記号とビット列の関係をもとに、もとのデータの記号をビット列に変換していくことで符号化が行われる。入力 DAEBCBACBBBC に対して上記のアルゴリズムを適用すると、出現頻度と割り当てられた符号が得られ、個数の多い文字ほど短い符号が割り当てられていることがわかる。ハフマン符号は、接頭符号である。つまり、ある文字に対応するビット列が、他の文字に対応するビット列の接頭辞になることはない。この特徴のおかげで、デコーダはビット列を先頭から一度読むだけで元のメッセージを一意にデコードできる。算術符号やその他の高効率の符号化法と異なり、特許の問題が無い。 そのため、JPEGやZIPなどの圧縮フォーマットで使用されている。

出典:wikipedia