ハフマン符号化のアルゴリズムとエントロピーを学ぶ

ハフマン符号とは1952年にデビッド・ハフマンという人が考え出したアルゴリズムです。
文字列をはじめとするデータの可逆圧縮に使われます。
よく使われる文字には短いビットを、あまり使われない文字には長いビットを割り当てることで全体としてサイズが削減されることを狙ったアルゴリズムです。

符号化の原理

実際にアルゴリズムを確認していきます。

DAEBCBACBBBC という12文字のメッセージをハフマン符号化します。

このメッセージでは、ABCDEという5種類の文字が使われているため、それぞれの文字を固有のビット長で表す場合は、3ビットが必要です。

1
2
3
4
5
A: 000
B: 001
C: 010
D: 011
E: 100

上記の対応表をもとに、文字列をビットに変換します。

1
2
DAEBCBACBBBC
011 000 100 001 010 001 000 010 001 001 001 010

1文字3ビットで12文字あることから全体のビット数は36ビットとなります。

ここで、よく出てくる文字には短いビットを、あまりでてこない文字には短いビットを与えます。
対応表を以下のように作ります。

1
2
3
4
5
A: 110
B: 0
C: 10
D: 1110
E: 1111

メッセージ全体では以下のようになります。

1
2
DAEBCBACBBBC
1110 110 1111 0 10 0 110 10 0 0 0 10

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

対応表をつくる

以下の手順で文字とビット列の対応表をつくります。

  • データに出現する文字の出現回数を求める
  • それをもとにハフマン木とよばれる二分木(バイナリツリー)を構成する

ハフマン木の構成の仕方は次のアルゴリズムとなります。

  1. 各記号に対応する葉を作成する。この葉には、記号の出現頻度をあらかじめ格納しておく。
  2. 出現頻度の最も少ない2つの葉をとりだす。取り出した2つの葉を格納する節をつくり、左右の枝に記号0と1を割り当てる。この節には2つの葉の出現頻度を足した値を格納し、新しい葉として追加する
  3. 葉が1つになるまで手順2を繰り返す。

DAEBCBACBBBC を題材に、ハフマン木を作ります。

1. 各記号に対応する葉を作成する

まずは、各記号に対応する葉を作成し、データの出現回数をあらかじめ格納しておきます。

1
{"B"=>5, "C"=>3, "A"=>2, "D"=>1, "E"=>1}

2.出現頻度が少ない2つの葉をとりだす

DとEが1番小さいので、この2つを取り出します。
そして、DとEの葉を足し合わせた節を1つ作ります。
この手順を最終的に葉が1つになるまで繰り返します。

ハフマン木が作られる工程

DAEBCBACBBBC を作成した対応表で符号化します。

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

データ圧縮アルゴリズムについて

一般的にデータ圧縮アルゴリズムは「モデル化」と「符号化」の2つにわけて考えることができます。
「モデル化」は入力された記号(データ)から各記号の出現確率を求めます。
「符号化」は出現確率に基づいて符号語を割り当て、入力されたデータを各符号語に変換して出力します。
モデル化についてはいろいろな方法がありますが、ハフマン符号のように記号の出現確率を求めそれに基づいて符号語を割り当てるモデルを「無記憶情報源モデル」といいます。
「情報源」は記号を生成する基となるデータのことです。
情報源が記号を生成するとき、以前に生成した記号との間に関連性がないことを「無記憶」といいます。
記号aの次は記号bが生成されるといった関係性はなく、確率でのみ記号が作成されるということです。

データ圧縮アルゴリズムを評価する場合、圧縮率のほかに「平均符号長」という尺度があります。
これは、符号化された記号列のビット長を入力された記号数で割った値として定義されます。

たとえば DAEBCBACBBBC をハフマン符号化すると1110110111101001101000010となります。
符号化された記号列のビット長(1110110111101001101000010)を入力された記号数(DAEBCBACBBBC)で割ると平均符号長は 25 / 12 = 2.0833333 となります。

無記憶情報源モデルの場合、各記号 $$ a_i $$ の出現確率 $$ p(a_i) $$ がわかると、次の式で平均符号長の下限値を求めることができます。

$$ H=-\sum_{i=1}^n p(a_i) \log _2 p(a_i) $$

$$ H $$ を平均情報量、またはエントロピー(Entropy)と呼びます。

情報源符号化定理によると、平均符号長はエントロピーより短くすることができません。

情報源符号化定理

意復号可能な平均符号長 L は、無記憶情報源のエントロピー H よりも小さくすることができない。すなわち不等式 H <= L が成り立つ。また、平均符号長 L が H <= L < H + 1 を満足する瞬時に復号可能な符号が構成できる。

先ほどの記号列のエントロピーを求めてみます。

1
2
3
4
5
6
7
8
9
10
11
記号列: DAEBCBACBBBC
記号: 確率: -p(ai) / log2 p(ai)
------------------------------------------
D: 1 / 12: 0.29874687506009634
A: 2 / 12: 0.430827083453526
E: 1 / 12: 0.29874687506009634
B: 5 / 12: 0.5262643357640807
C: 3 / 12: 0.5
------------------------------------------
エントロピー = 2.054585169337799
12 * 2.054585169337799 = 24.65502203205359 bit

したがって、この記号列では平均符号長を 2.05 ビット以下にすることはできません。
いいかえると、この記号列を表すには少なくても 12 * 2.054585169337799 = 24.65502203205359 ビット以上が必要になる、ということです。

エントロピーの算出コード

エントロピーを算出するコードをRubyで書きました。

以下のように使います。

1
2
$ ./entropy file.txt
2.054585169337799

文字列を渡す場合はパイプで繋ぎます。

1
2
$ echo "DAEBCBACBBBC" | ./entropy
2.054585169337799

また、 -v オプションで詳細を表示できます。

1
2
3
4
5
6
7
8
9
10
$ ./entropy -v file.txt
記号: 確率 : 値
D: 1 / 12: 0.29874687506009634
A: 2 / 12: 0.430827083453526
E: 1 / 12: 0.29874687506009634
B: 5 / 12: 0.5262643357640807
C: 3 / 12: 0.5

サイズ エントロピー 下限値
12 2.054585169337799 3

ファイルサイズ * エントロピー で圧縮の下限値を計算することができます。
上記の場合は3バイトよりも圧縮することはできないということです。

ただし、この結果は無記憶情報源モデルの場合であり、モデル化によってエントロピーの値は異なることに注意してください。エントロピーをより小さくするモデルを作成することがでれきば、これよりも高い圧縮率を達成することができます。

参考リンク

最近の投稿