2009年08月01日

情報理論 データ圧縮の基礎〜ハフマン符号とは?〜

【情報理論 誤り訂正符号とは?!】
http://kiracchi-serendipity.sblo.jp/article/29807541.html

前回は、↑のエントリーで誤り訂正符号の概念を書いた。これは、通信中に「0」「1」のデジタル信号にノイズが混じって、「0」「1」が反転してしまった場合にも正しく復元できるような事を目的とするものであった。


さて、今日は同じ符号関係の話なんだけど、誤り訂正符号の話ではなく「データ圧縮」の代表的な手法である「ハフマン符号」について述べる。今「ABADAACB」という文字列をデジタル化して通信する事を考えよう。すると、まずはA,B,C,Dにどのような「0」「1」を割り振るかをかんがえなければいけない。
通常、普通に考えると
A→00
B→01
C→10
D→11
と割り振るのが自然だと思うのだけど、この時は「ABADAACB」という文字列は「00 01 00 11 00 00 10 01」という16個の「0」「1」に置き換えられる。ただ、これをUSBメモリ等に記録しようとした場合やデジタル通信しようとする場合に、16個の「0」「1」で記録/通信するよりも、より少ない個数の「0」「1」で記録/通信する方が、コスト削減かつ記録や通信資源の有効利用ができるので、「0」「1」の量を少なくする事は、非常に意義がある。
よって、「同じ内容を、いかに少ない「0」「1」にデジタル化するか?」っていう研究が、「データ圧縮」って呼ばれる分野となっている。

ちなみに上記の例の「ABADAACB」の場合、本当に16個の「0」「1」も必要なのだろうか?「ひょっとしたら16個の「0」「1」よりも、もっと少ない個数でデジタル化できるんじゃない?」と思う人もいるかもしれない。まぁちょっくら、考えてみようか?とりあえず、以下のような規則でデジタル化しよう。
A→0
B→1
C→01
D→10
そうすると、「ABADAACB」って文字列は、「0 1 0 10 0 0 01 1」となって、10個の「0」「1」で表せるけれど、この「0」「1」の並びだと「CCAAACB」(01 01 0 0 0 01 1)とも解釈できるよね。この「0」「1」の割り当て方法だと、記録や通信内容が一意に戻せない事になるので、実際には全然実用にならない。


実は、これから説明するハフマン符号と呼ばれる手法は、上記とは違って「一意に戻せて、なおかつ「0」「1」の量を少なくする」とても良い「0」「1」割り当て方法なんですよ。
んで、その基本的なアプローチなんだけど、
1.出現確率の高い文字には、短い「0」「1」を割り振り
2.出現確率の低い文字には、長い「0」「1」を割り振る
という事で、全体の「0」「1」の個数を削減しようってことなんだな。

例えば以下の割り当て規則を考えてみよう。
A→0
B→10
C→110
D→111
この時「ABADAACB」は「0 10 0 111 0 0 110 10」と、14個の「0」「1」で表せて、最初の16個の例から2個の圧縮が可能になる。さらにこの割り当て規則であれば、上記の「0」「1」からきちんと一意に「ABADAACB」に戻せるのが確認できるだろう。


それじゃ、どうやってこの「0」「1」の割り当て規則を自動的に生成すればいいのか?とりあえず、さっきも書いたけど、それぞれの文字の「出現確率」に注目してみましょう。
「ABADAACB」で各アルファベットの出現確率は以下のようになる。
A:4/8、B:2/8、C:1/8、D:1/8。

huffman-coding.jpg
ここからは、↑の画像を使わないと説明が難しくなるのだが、ハフマン符号とは基本的に「一番小さい二つの確率を結びつける作業を繰り返す」という事に集約される。今の例の場合だと、C,Dの出現確率が一番小さいので、CD連合を作る。この場合の出現確率は、
A:4/8、B:2/8、CD:2/8となるわけだ。次に再び、一番小さい二つの確率を結びつけるわけで、A:4/8、BCD:4/8となり、最後にABCD:8/8となった時点で、結びつける作業は終了する。
この時、↑の画像みたいに結び付けを図に表したときに、各分岐に対する「0」「1」を決める事によって、A(0)、B(10)、C(110)、D(111)の符号割り当てが自動的に決まるわけだ。

今は、送るべき文字がABCDの4種類しかなかったのだけど、これが100種類とか200種類になっても、この方法は汎用的に使えるので、データ圧縮の世界では一種の金字塔的な手法になっている。
もっとも、今は元々送るべき「0」「1」の数が16個から14個になるだけなので圧縮効果としては大したことないかもしれないけど、もっと長い文字列を扱う場合、圧縮率はどんどん上がっていきます。

ちなみに、圧縮率限界に対しては「情報エントロピー」という確固たる指標があるのだけど、実はこの情報エントロピーの概念はデータ圧縮だけではなく、以前の↓エントリーにも書いた天気予報の話にも密接に関係してくる事になります。これまた数学的には非常に面白い話なのですが、またいつか時間のある時にでも詳細を書くことになるでしょう。

【天気予報 的中率だけで予報性能を判断していいのか?】
http://kiracchi-serendipity.sblo.jp/article/29287395.html




今日のエントリーで、「なるほど」「ふむふむ」「面白い」などと思ってくれた方で、一票を頂ける方は是非ともお願いします。↓
人気ブログランキングへ
posted by きらっち at 08:56| Comment(2) | TrackBack(0) | 科学
この記事へのコメント
ややこしいので、最初は読む気なかったけれど、少し読みはじめると面白くて、圧縮技術を垣間見る事が出来ました。
Posted by ゆきちゃん at 2009年08月01日 17:00
>ゆきちゃんさん
やはり、理学系や工学系のエントリーになると、私の説明力不足でゆきちゃんさんを混乱させて申し訳ありません。なるべく平易に書くよう心がけていきたいと思っております。

なるべく「へぇ〜」とか「面白いなぁ」と思ってもらえるように、様々なジャンルの話を出して行きたいとは思っているんです。
Posted by きらっち at 2009年08月03日 21:01
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

この記事へのトラックバックURL
http://blog.sakura.ne.jp/tb/30974209

この記事へのトラックバック