ハフマン符号

InformationTheory

Excel でハフマン符号を生成する(Huffman Coding by Excel Without VBA macro) †

概要 †

• 文字の羅列により情報を表す場合、その文字や文字の組み合わせにより、出現頻度が異なる場合があります。例えばアルファベット26文字で構成される英文ですが、アルファベットそのものは一文字あたり、-log_2(1/26)=約4.7bit で表すことができます。しかしながら英文になると一文字あたり、約1.3bit の情報量しかありません。これは、英文をアルファベットとは別の記号をうまく当てはめることにより、文の量を約 1.3/4.7　に圧縮できることを表しています。
• このように元の文字を別の記号等に割り当て直すことを符号化と呼びます。
• 一定の通信容量を持つ通信路を有効に使ったり、データ圧縮を行ったりする時、符号化が行われます。
• ハフマン符号は、ハフマン符号の符号列を前から読みながら、後戻りすることなく、元の文字列に複合可能な、「最適な」符号化を行います。JPEGなどの画像の圧縮など、様々な場面で利用されています。
• ここでは、VBAマクロを使わずに、元の符号のセットとそれぞれの出現確率の表から、ハフマン符号の生成の一部（木の生成まで）を半自動的に行う表について説明します。

ハフマン符号の生成アルゴリズム †

• 1. 元の文字（符号）を出現確率の大きなものから降順にならべる。
• 2. 確率の最も小さな文字同士を２つ、つないで2分木を作る。その２分木の出現確率の和を、その、２分木の確率とする。
• 3. ２の２分木を新しい文字系列として、1 に戻る。
• 4. 1-3 を、すべての２分木がつながるまで繰り返す。
• 5. 4 でできた木を根からたどって、枝分かれに0と1を付け、符号を作る。

ハフマン符号の生成アルゴリズムを実現するExcelシート(VBAマクロなし) †

説明 †

• 入力として、A8:A15 の範囲に元の記号、B8:B15の範囲に、その記号に付ける番号、C8:C15の範囲に、元の記号の出現頻度を記述します。元の記号は８文字限定です。
• 入力が行われると、自動的に、AY8 にハフマン符号を表す2分木が現れます。この２分木は、(0-<0の側の２分木> 1-<1の側の２分木>)で表されています。

Excel の表 †

• 06-haffman-coding-02.xlsx

参考 †

• https://en.wikipedia.org/wiki/Huffman_coding
• https://www.cs.helsinki.fi/research/aaps/excel/
• ハフマン符号をExcelでやってみる...http://su-hai.hatenablog.com/entry/5804296