基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

令和3年 問6について質問です。

https://www.fe-siken.com/kakomon/03_menjo/q6.html

解説では、イの選択肢について、「符号化後のビット列に"00110"があった場合、abc(00110)とaada(00110)の区別がつかないので、元のメッセージに一意に復号することができません。」と書いてあります。
このように「復元することができない」ことを示すには例を一つ挙げれば良いですが、「復元することができる」ことはどうやって示すことができますか？
エの場合は「各文字が2ビットずつなので一意の復号が可能です。」という解説で納得できましたが、ウについては分かりませんでした。

先頭からビット列を見ていき、
①1ビット目が0であれば"a"と判断、1であれば②へ進む
②2ビット目が0であれば2ビットあわせて"b"と判断、1であれば③へ進む
③3ビット目が0であれば3ビットあわせて"c"と判断、1であれば3ビットあわせて"d"と判断
を繰り返すことで復元可能です。

選択肢エは元の文字列1文字あたりのビット数が全て同じなので、ビット列の途中や後ろから処理することも可能ですが、選択肢ウの場合は必ず先頭から順に処理する必要があります。

ありがとうございます。

新たな質問になってしまうのですが、同様の方法でイについても判別可能でしょうか？
自分で試してみましたが、途中でわからなくなってしまいました。

①1ビット目が0であれば②へ進み、1であれば③へ進む
②2ビット目が0であれば対応する文字はない（？）、1であれば2ビットあわせて"b"と判断
③2ビット目が0であれば2ビットあわせて"c"と判断、1であれば2ビットあわせて"d"と判断

aが判断できないから、復元不可能と考えて良いのでしょうか？

選択肢イは「一意に復号可能」ではない方法です。
例えば、"010"というビット列があった場合、"0 / 10"と見れば"ac"、"01 / 0"と見れば"ba"と復号されます。ビット列に変換したことにより、元の文字列が何であったか分からなくなってしまいました。
このように1つのビット列から複数通りの文字列に復号できてしまう方法は「一意に復号可能」ではない、ということになります。

キーワード「ハフマン木」でネット検索して解説記事を見つけてください。
問題文で提示されたビット列がどのように作られているか分かります。

> nsさん

すみません。聞き方が悪かったかもしれません。
「一意に復号可能ではない」ことを示すには、そのような例を頑張って見つけるしか方法はない、ということで良いでしょうか？

> 「一意に復号可能ではない」ことを示す
これもNo.5の木を描くことによって示すことができます。

> jjon-comさん

すみません。問題のa,b,c,dについてハフマン木を描いてウが導かれることはわかりましたが、イについて木を描くやり方がよく分からず...

ハフマン符号の性質として、ある文字に対応するビット列が、他の文字に対応するビット列の接頭辞になることはない(wikipediaより)、ということなので、これに反しているイは、ハフマン符号ではない => 一意に復元できない、という考え方でも良いでしょうか？

（No.8に対して）
はい，その考え方で大丈夫です。

2値符号化のための木は二分木であり，一方の枝に０を，他方の枝に１を割り当てます。そして符号化したい文字を「葉(leaf)」に対応付けることができればそれは「一意に復号可能」です。

この問題の選択肢ウはこんな感じ。二分木のイラストを描くことができないので，文字位置がズレるようなら等幅フォントのテキストエディタなどに貼り付けてください。

それに対して，選択肢イはこうなります。
文字ａに対応する「０」は「葉(leaf)」ではないので，一意に復号できません。

No.8でおっしゃっているとおり，文字ａに対応するビット列「０」が、他の文字ｂに対応するビット列「０１」の接頭辞になっているので，一意に復号できません。

> jjon-comさん

ありがとうございます。