ハフマン符号
例として DAEBCBACBBBC という12文字からなるメッセージを考える。
このメッセージ中には5種類の文字が使われているので、もしそれぞれの文字を固定長のビット列で表すとすれば、1文字につき最低3ビット必要となる。
文字とビット列の対応表として、
を使い、それぞれの文字をビット列に置き換えたとすると、メッセージ全体は次のビット列で表される。
12文字 x 3ビットで全体のビット数は36ビットとなる。
もし、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることができれば、メッセージ全体の符号化に必要なビット数を抑えることが期待できる。そこで、文字とビット列の対応表として、
を使ったとすると、メッセージ全体は
となり、全体のビット数は25ビットとなる。 固定長の方式に比べると 70% ほどのデータ量に抑えられている。