ハフマン符号 - 通信用語の基礎知識

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)として使われている。