（基本情報・応用情報学習メモ）ハフマン符号化　一意に識別 - （移行済み）胡瓜のプログラミング日記

　そろそろ応用情報技術者試験に向けて勉強せねば、ということでようやく始めました。

　が、基本情報の知識も曖昧で、なかなか進まず……

　とりあえず、つまづいたところが解決したら記事にしてまとめておこうと思います。かなり基本的なところでもつまづきそうで、ブログでさらすのはなぁ…とも思ったのですが、やらない理由を考えるときりがないので、書いちゃいます。

・ハフマン符号化

　ハフマン符号化というのは、伝達する情報を短くする情報源符号化の手法の一つです。

　例えば、４種類の文字A、B、C、Dからなる文字列DBBCAAAAを送るとします。４種類の文字それぞれを一意に表現するには、そのままでは

「00」「01」「10」「11」

のように、1文字あたり2ビットのデータ量が必要となり、上に示した8文字だと、

1101011000000000

となります。その大きさは

2 × 8 = 16 bit

となります。

　上の例では、すべての文字について同じ長さのビット列を与えましたが、これを文字列に出現する確率によって変えようというのがハフマン符号化になります。
　上の文字列における、各文字の出現確率をまとめると、次の表のようになります。

文字	出現確率
A	50%
B	25%
C	12.5%
D	12.5%

　出現確率の大きいものには短いビット列、小さいものには長いビット列を与えると、このようになります。

文字	ビット列
A	0
B	10
C	110
D	111

こうすると文字列は

11110101100000

となり、

14 bit

の大きさとなります。

・「一意に識別」

　上の表で各文字に与えたビット列は、ハフマン木を用いたものです。A～Dの文字を葉、出現確率を木の重みとして作成します。作成方法はここでは割愛。
　ここでの私の疑問は、「なんでそんなの作るの？『0』『1』『10』『11』じゃだめなの？」でした（当たり前の話なのかもしれませんが、「0と1で伝えるんだ。へ～」くらいの認識しかない私にはすぐにはわからなかった……）。

　検索しても、基本的すぎるせいか、解決しなかったので、実際に文字列を符号化してみることにしました。
　まず、「『0』『1』『10』『11』」。この場合、文字列DBBCAAAAは

1111100000

となります。見ればすぐに気づきますが、どこが文字の切れ目か全くわかりません笑
「BBBBBAAAAA」とか「DDCAAAA」とか、いろんな文字列が考えられますね。
　一方、ハフマン木による方は

11110101100000

（もう一度対応表を）

文字	ビット列
A	0
B	10
C	110
D	111

となります。こちらも、1と0だけでよくわからんとなりそうですが、よく見ると、文字列はひとつに決まります。
　まず、先頭が「1」なので、最初の文字としてあり得るのはB、C、Dのどれか。次の文字も「1」なので、C、Dのどちらか。さらに見ていくと3番目の数字は「1」なので、先頭の文字は「C」に決まります。
　つぎの数字は「10」と続くので、その時点であり得る文字は「B」だけになります。
　こんな感じで、ちゃんと元の文字列に戻せちゃいました。

　なんでだろう？と考えたんですが、ハフマン木での符号化の方法から考えれば当然でした。
　文字を符号化する際には、各節がもつ2つの経路に0と1を割り当てて、それを葉にたどり着くまで続けます。上で「11110101100000」から「DBBCAAAA」に戻した作業は、この符号化を上から順になぞっただけなんですよね。根から葉までの経路は、葉それぞれに一本しかありません。つまり、根から葉まで一本道でたどるようにビット列を与えれば、文字が一意に決まることになります（こんなことにも気づけないなんて……）。

　
　
　以上、「ハフマン符号化」とその符号化における「一意に識別」についてのメモでした。
　「一意に識別」については、ハフマン符号化に限らず、いろんなところで必要な視点な気がしました。というか、情報系に限らない話ですよね、これ。よくこれで基本情報技術者試験に合格したなと笑
先が思いやられるなという感じですが、やれるところまではやろうかと思います……

　ではでは。