数学徘徊記

自由な数学ブログ。

ハフマン符号をExcelでやってみる

最近「なんでファイルが圧縮できるんだ?」って思ったので、
Wikipediaでいろいろ調べてみると、
「ハフマン符号」というものがあった。
ハフマン符号 - Wikipedia
どういうものかは上の記事を見てもらえばわかる。

やはり自分は
Excelでやってみたいなあ」
と思った。

しかしコードを組んでいったところ
バグが大量発生し本当に大変だった。

どんなアルゴリズムでやったのかをまず説明する。

まず1と0からできた文字を、4けたごとに区切ってまとめる(つまり16進法にする)。
そうすると0から15までの整数の数列になる。

そして、0はいくつか、1はいくつか…と、0から15までの整数が
それぞれいくつあるかをカウントする。

まあここまでは下ごしらえだ。

そしてここからハフマン符号をつけていくのだが、
これが意外とプログラムを組むのがムズい。

ハフマン符号のつけ方はWikiに書いてあるが、これを実装するのがきつかった。

努力の結果、VBAソースコードが出来上がった。
ソースコード

バグが次から次へとあらわれたので、意外と時間がかかった。
Excelファイルも上げておく。
HuffmanCording.xlsm

前述のとおりこれは圧縮するために用いるものだ。
このファイルでいろいろ実験してみると、
0と1の偏りが大きい場合によく圧縮されるということが分かった。