ハフマン符号

Facebookシェア Twitterツイート LINEで送る Googleシェア このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
Up
0
Down

要約

概要

ハフマン符号は、よく頻出するものの符号長を短くしてあまり現れないものに対する符号長を長くすることでデータ全体を小さくすることができる符号化.
ー 条件 ー
  • データの現れ方にばらつきのあるデータ(aとbは頻出だがeはほぼ出ない等)
ー 効果 ー
  • 情報を失うことなくデータをよりコンパクトに表現できる
ーポイントー
  • 頻出する順に短い符号を当てていく
  • 最小でも一つのデータで割り当てられる大きさは1bit.それより小さくするには算術符号化が必要
  • あらかじめ符号化する前に頻出具合を知っておく必要がある

解  説

ハフマン符号は、よく頻出するものの符号長を短くしてあまり現れないものに対する符号長を長くすることでデータ全体を小さくすることができる符号化. 例えば、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以下で表現することが可能です. しかし、ハフマン符号は単純であるため高速であり、また算術符号は以前特許で守られていたこともあってハフマン符号が実際に使われていることが多かったようです.
ハフマン符号化の特徴
この章を学んで新たに学べる
Comments

Reasons
>>隠す