大学のテストが終わりました＾＾
四捨五入して小数点以下2桁で答えよ、とか書いてあるのにバッチリ全部計算しました。終わりました＾ｐ＾

私の通っているコースは情報系のコースなのですが、主に勉強するのは画像処理などソフト的な分野と通信の分野になります。

今回のテストは情報理論という通信分野のテストでした。

情報理論は情報量だとか通信における誤りだとかについて勉強します。

正直苦手です＾ｐ＾
通信よりソフトの勉強の方が好きです＾ｐ＾ｐ＾

ですが勉強している中で、いくつか面白いなーと思うものがいくつかありました。

今回はその中の一つである、「ハフマン符号化」についてのお話です＾＾

例として、ある手紙をデータとして送信することを考えます。

データはすべて｛0、1｝に変換されて送信されます。

ハフマン符号化は｛0、1｝の平均的な長さを短くする手法です。

ある手紙は「い」「ぱ」「つ」「お」の4文字で構成されているとし、
それぞれの出現確率は｛い、ぱ、つ、お｝=｛0.4、0.１，0.2、0.3｝とします。

ハフマン符号化をするにあたって、まずは文字を出現確率が昇順になるように並べ替えます。
（絶対ではない。並べ替えたほうがやりやすいだけ）

ここから木を作っていきます。
文字を木の根とします。

出現確率が一番小さい根と次に小さい根を結んで木を作ります。
結ばれた2つの根は葉になり、新しく根が一つできます。
新しくできた根の出現確率は結んだ2つの根の出現確率の和になります。

根が一つになるまで繰り返せば、あら不思議＾ｐ＾
ハフマン木の出来上がりです。

木はできたけどここからどうやって符号化するのか。
木の枝に｛0、1｝をつけるのです＾ｐ＾

左側の枝には0、右側の枝には1をつけます。
（終始一貫していれば別に逆でもいい）

これで符号化完了＾ｐ＾
たのしい＾ｐ＾ｐ＾

「ぱ」を表すのは｛000｝、「い」を表すのは｛1｝になります。
matlabなんかだとハフマン符号化の関数があるみたいですが、自分で実際に作ってみるのも楽しそうです。

文字列データの中からそれぞれの文字と出現確率のペアを返す関数
文字を出現確率が昇順になるように並べ替える関数
ハフマン木を作る関数
ハフマン木からそれぞれの文字に対する符号を返す関数
符号から文字を復元する関数

ここら辺まで作ってみたいですね＾＾
（作るとは言ってない＾ｐ＾）

私の座右の書で『アルゴリズムC++』(ロバート・セジウィック著)というのがあります。
クヌースの方がメジャーだろうし、かなり古い本ですが、私でもどうにか手に負える本です。
ハフマン符号化のような古典的な概念は丁寧に説明されてますよ。


座右の書と言いながら、座右に置いてあるだけで10年ぶり位で手にしたみたい。埃まみれ。
この本でなくても、アルゴリズムの本は好きな人ならとても面白いので、
一冊購入を検討してはいかがでしょうか。

ありがとうございます＾＾

アルゴリズムは理解するまでは嫌いで理解してからは好きになります＾＾；

クイックソートなんかはその最たる例で、「関数用意されてるんだから中身なんて理解する必要ないじゃん＾ｐ＾」と思っていました＾＾；
授業で無理やりクイックソートを作らされたときにやっとクイックソートの面白さに気づきました。

それ以来、暇な時には適当な数列をいろいろな方法でソートして遊んでいます。
情報理論の授業中なんかはソートしまくってました＾ｐ＾