ハフマン符号

ハフマン符号は、よく頻出するものの符号長を短くしてあまり現れないものに対する符号長を長くすることでデータ全体を小さくすることができる符号化. 例えば、aが最も文章中に現れhが全く現れないような文字列があるとし、aからhにつれて出る回数が少ないとする. そのとき以下のような文字列がある場合に $$aacaabbbcafg$$ 通常の場合は、8種類あるので3bitを割り当てるとすると $$a = 000 \\ b = 001 \\ c = 010 \\ d = 011 \\ e = 100 \\ f = 101 \\ g = 110 \\ h = 111 \\$$ のような表現になり、先ほどの文字列は12文字なので $$3bit \times 12 = 36 bit$$ となる. しかしハフマン符号では、以下のように割り当てをする $$a = 0 \\ b = 01 \\ c = 011 \\ d = 0111 \\ e = 01111 \\ f = 011111 \\ g = 0111111 \\ h = 01111111 \\$$ 基本的にいくつ1が連続するかで文字を見分けることになる. このようにすると全てのbit数を足し合わせれば $$1bit \times 5 (a)+ 2bit\times 2 (b) + 3bit \times 2(c) \\ + 6bit \times 1 (f)+ 7bit \times 1 (g) = 28bit $$ 実際に先ほどより\(8bit\)少ないデータ量で表現できていることがわかる.

上記のようなハフマン符号化するには以下の手順が必要. エンコード(符号化)も至って簡単. 1. 各データ(文字)の頻出具合を算出 2. 頻出具合の高い順で符号を割り当てる 3. 実際に文字列を置き換えていく. デコードするときも容易に可能. 1. エンコードで使用していた文字とコードの対応表を用意 2. 得られた文字列から0が出るたびにそこまでを文字列として置換.

ここで紹介したものはいわゆる静的ハフマン符号でエンコード中に対応関係が変わることはない. ハフマン符号は一つ文字列に対して最小でも1bitの表現を要しますが、算術符号においては1bit以下で表現することが可能です. しかし、ハフマン符号は単純であるため高速であり、また算術符号は以前特許で守られていたこともあってハフマン符号が実際に使われていることが多かったようです.