ハフマン符号

読み：ハフマンふごう
外語：Huffman coding

品詞：名詞

1952(昭和27)年にDavid Albert Huffmanにより考案された符号法であり、圧縮アルゴリズムの一つ。

概要

ハフマン符号と言うと圧縮法の事を指す場合が多くあるが、ハフマンが考案したものは「符号検索」のみであるため、本来は符号法のみを指す。

生起確率を求めるところまではシャノン・ファノ法と変わらないが、符号化の検索をかける方向が葉から枝になっており、逆である。

{ebcedadecabd}が元である場合、各生起確率は、a=1/6、b=1/6、c=1/6、d=1/4、e=1/4となる。

ここで生起確率が最も低い情報を二つ選び、a:0、b:1のように符号化し、二つの生起確率を足した1/3を{a,b}の生起確率として再度同じ計算を行なう。

c:0、d:1、{c,d}=5/12、e:0、{a,b}:1、{e,{a,b}}=7/12、{c,d}:0、{e,{a,b}}:1と尽きるまで計算する。これによりa:110、b:111、c:00、d:01、e:10という符号が導き出される。

ハフマン符号でより短い符号をはじき出すには、より多くのデータをまとめて一つの要素とすれば良い。

しかし、要素の大きさが増える毎に指数関数的にメモリーと時間を消費する事になる。

ハフマン符号は、常にシャノン・ファノ法以上に短い符号を算出することが証明され、それによりシャノン・ファノ法を駆逐した。

データ圧縮の基本的方法として各種方面に使われており、LHAではLZ法で圧縮した後、さらにハフマン符号で圧縮する手法を採っている。

G3での圧縮でも、ランレングス圧縮と組み合わせてMH符号(Modified Huffman)として使われている。