符号化・・・一定のルールに基づき別の文字列に置き換えること。
複合化・・・ルールに基づき文字列に置き換えたものを元の文字列に戻すこと
たとえば、アのルールではaという文字は0に置き換えるといっているので
a→0 が複合化で、0→aに戻すのが複合化といえる。
符号化した結果、複合化する時に複数通りの解釈ができてしまう場合NGなので(複合可能であって と書かれているので）
まず、複合可能かどうか検証してみる。
■アのケース
□１文字の場合を考える
a→0、 0はaにしか変換できないので複合可能。
b→１、1はbにしか変換できないので複合可能。
c→00、00はcとaaの二通りに解釈ができるため複合可能ではない。
よって、アのケースは複合可能でないためこの時点でNG
■イのケース
□１文字の場合を考える
a→0、 0はaにしか変換できないので複合可能。
b→0１、01はbにしか変換できないので複合可能。
c→10、10はcにしか変換できないので複合可能。
d→11、11はdにしか変換できないので複合可能。
□２文字の場合を考える
aa→00、00はaaにしか変換できないので複合可能。
ab→001、001はabにしか変換できないので複合可能。
ac→010、010はacとbaの二通りの解釈ができるため複合可能ではない。
よって、イのケースは複合可能でないためこの時点でNG
■ウのケース
□１文字の場合を考える
a→0、 0はaにしか変換できないので複合可能。
b→10、10はbにしか変換できないので複合可能。
c→110、110はcにしか変換できないので複合可能。
d→111、111はdにしか変換できないので複合可能。
□２文字の場合を考える
aa→00、00はaaにしか変換できないので複合可能。
ab→010、010はabにしか変換できないので複合可能。
ac→0110、0110はacにしか変換できないので複合可能。
ad→0111、0111はadにしか変換できないので複合可能。
ba→100、00はbaにしか変換できないので複合可能。
bb→1010、1010はbbにしか変換できないので複合可能。
bc→10110、10110はbcにしか変換できないので複合可能。
bd→10111、10111はbdにしか変換できないので複合可能。
ca→1100、1100はcaにしか変換できないので複合可能。
cb→11010、11010はcbにしか変換できないので複合可能。
cc→110110、110110はccにしか変換できないので複合可能。
cd→110111、110111はcdにしか変換できないので複合可能。
da→1110、1110はdaにしか変換できないので複合可能。
db→11110、11110はdbにしか変換できないので複合可能。
dc→111110、111110はdcにしか変換できないので複合可能。
dd→111111、111111はddにしか変換できないので複合可能。
ウは複合に関しては問題なさそう。
■エのケース
□１文字の場合を考える
a→00、 00はaにしか変換できないので複合可能。
b→01、01はbにしか変換できないので複合可能。
c→10、10はcにしか変換できないので複合可能。
d→11、11はdにしか変換できないので複合可能。
□２文字の場合を考える
aa→0000、0000はaaにしか変換できないので複合可能。
ab→0001、0001はabにしか変換できないので複合可能。
ac→0010、0010はacにしか変換できないので複合可能。
ad→0011、0011はadにしか変換できないので複合可能。
ba→0100、0100はbaにしか変換できないので複合可能。
bb→0101、0101はbbにしか変換できないので複合可能。
bc→0110、0110はbcにしか変換できないので複合可能。
bd→0111、0111はbdにしか変換できないので複合可能。
ca→1000、1000はcaにしか変換できないので複合可能。
cb→1001、1001はcbにしか変換できないので複合可能。
cc→1010、1010はccにしか変換できないので複合可能。
cd→1011、1011はcdにしか変換できないので複合可能。
da→1100、1100はdaにしか変換できないので複合可能。
db→1101、1101はdbにしか変換できないので複合可能。
dc→1110、1110はdcにしか変換できないので複合可能。
dd→1111、1111はddにしか変換できないので複合可能。
エに関しても複合は問題なさそう。
次、a、b、c、dはそれぞれ50%、30%、10%、10%の確率で選択されるので
この確率とビット長さを掛け合わせると期待するビット長さが求まる。
ウ
aの時１ビット。これは50%で選択されるので１×０．５＝０．５
bの時2ビット。これは30%で選択されるので２×０．３＝０．６
cの時3ビット。これは10%で選択されるので３×０．１＝０．３
dの時3ビット。これは10%で選択されるので３×０．１＝０．３
０．５＋０．６＋０．３＋０．３＝１．７ビット
エ
aの時2ビット。これは50%で選択されるので２×０．５＝１．０
bの時2ビット。これは30%で選択されるので２×０．３＝０．６
cの時2ビット。これは10%で選択されるので２×０．１＝０．２
dの時2ビット。これは10%で選択されるので２×０．１＝０．２
１．０＋０．６＋０．２＋０．２＝２．０ビット
よって、ウの方式による符号化の方がビット長さが短くなる。
答え ウ
圧縮プログラムなどいかにしてよく出現するものを、短く表現するか？
にかかっているので、ウの方式は頻繁に出る部分を１ビットで表現し、
複合化可能にするために、やむをえず、出現頻度が小さいとこでビット長さを増やし
一意に変換できるようにしている。
エは何も考えずに全て２ビットで表現した場合。
という見方ができる。
戻る
0 件のコメント:
コメントを投稿
注: コメントを投稿できるのは、このブログのメンバーだけです。