符号化

符号化とは簡単に言うとデータを別の形式に変換することです。
例えば、ビット列というのは、"0"と"1"で構成されています。
aを00
bを01
cを10
dを11
と符号化したとします。
"11011000"というデータを受け取った場合、2ビットずつ読み取って、"dbca"と解釈することができます。
『aは00ではなく、0。bは01ではなく、1じゃダメなのか？』
上記の方式の場合ダメですね。
例えば、10という情報があった場合、"c"なのか"ba"なのかわからなくなってしまいます。
符号化する場合、こういったことも考えてつくらないとダメです。

【平成22年・秋】

Q.

a,b,c,dの4文字からなるメッセージを符号化してビット列にする方法として表のア～エを考えた。この表はa,b,c,dの出現頻度は、それぞれ50%、30%、10%、10%であることが分かっている。符号化されたビット列から元のメッセージが一意に複合可能であって、ビット列の長さが最も短くなるものはどれか？

	a	b	c	d
ア	0	1	00	11
イ	0	01	10	11
ウ	0	10	110	111
エ	00	01	10	11

A.
・まず復元可能な符号化かどうかを検証する。
ア・・・符号化に問題がある。例えば、"00"というデータの場合、"aa"か"c"かわからない。
イ・・・符号化に問題がある。例えば、""01010"の場合、"bba"か"acc"かわからない。
ウ・・・復元可能
エ・・・復元可能

・ビット列の長さが短くなるものはどれか？
１文字取得した場合、平均ビットを求める。
ウ・・・(1×0.5) + (2×0.3) + (3 × 0.1) + (3×0.1) = 1.7ビット
エ・・・(2×0.5) + (2×0.3) + (2 × 0.1) + (2×0.1) = 2ビット

答えは、ウとなる。