4-7.通信に関する理論

データ圧縮


★符号理論

情報を符号化して通信を行う際の効率と信頼性についての理論のこと

★ランレングス

ある連続したデータをそのデータ一つ分と連続した長さで表現することで圧縮する方法のこと

つまり
⇒文字列中で同じ文字が繰り返される場合、繰り返し部分をその反復回数と文字の組に置き換えて文字列を短くする方法

AAAAABBBBAAA
⇒A5B4A3

★ハフマン符号

出現度の高い文字を短いビット列で、出現率が低い文字を長いビット列で表現することで、1文字を表現するのに使用する平均ビット長を最小とする圧縮技術のこと

例:それぞれの出現頻度a(50%),b(30%),c(10%),d(10%)であるとき、下記のパターンのうちどれがもっともも短くなるか

  a b c d
0 1 00 11
0 01 10 11
0 10 110 111
00 01 10 11

アの場合はbb(11)とd(11)の区別がつかない
イの場合はabc(00110)とaada(00110)の区別がつかない
ウの場合は一意の復号が可能
(1×0.5)+(2×0.3)+(3×0.1)+(3×0.1)
=0.5+0.6+0.3+0.3=1.7
エの場合も一意の復号が可能
(2×0.5)+(2×0.3)+(2×0.1)+(2×0.1)
=2.0

結果ウが一番短い長さであることがわかる




  • 最終更新:2017-08-20 20:33:36

このWIKIを編集するにはパスワード入力が必要です

認証パスワード