ハフマン符号化とは？①

久しぶりに、この[研究]カテゴリーを書いたなぁ……。
前回最後に書いたのが、4月12日なので5ヶ月ぶりってことか。(笑)
前回までは、フーリエ変換の基礎シリーズを書いてたけど
今日は、情報理論で使われる「ハフマン符号化」について書こう。
(フーリエ変換の話も終わっていないけど、後日にちゃんと完結させるよ)


さて、このハフマン符号化、
JPEGの画像とか主に画像・映像・音声・文書等の圧縮ソフト等々
いろいろなところに使われているメディアの
データ圧縮手法の一つなんだけど、そもそもデータ圧縮って何かを説明しよう。


そもそも「デジタル化」ってのは、
すべてを「0」か「1」に置き換えてしまう事なんだけど、
わかりやすく例を出そう。
みんなが今見ている文字も、実はすべて「0」と「1」で処理されている。
つまり、
A→00
B→01
C→10
D→11
みたいに、それぞれの文字に対して何桁かの
「0」「1」が割り当てられているんだよ。
（今は例として、A〜Dの文字を2桁の「0」「1」で割り当てているけど
　実際は、半角文字は8桁、全角文字は16桁の
　「0」「1」が割り当てられている。）


だから例えば「ABADAACB」って文字列は、ＰＣ内部で
「00 01 00 11 00 00 10 01」って感じで、16個の「0」「1」で処理されている。
ただ、これをフロッピーディスクとかCD-Rに記録しようとした場合、
記録媒体に書き込める「0」「1」の量は決まっている。
しかしながら、もし同じ内容を少ない「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」の個数で、一意に解釈が定まるのだろうか？
次回は、この問いに対する一つの答えである「ハフマン符号化」と
呼ばれる手法を説明しよう。