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

選択肢

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

正解と解説

正解：ウ a=0, b=10, c=110, d=111

一意に復号するには、ある符号語が他の符号語の先頭部分になっていない（語頭条件を満たす）必要がある。ア（0が00の先頭）とイ（0が01の先頭）は語頭条件を満たさず復号が一意に定まらない。残るウとエで平均符号長を計算すると、ウは0.5×1+0.3×2+0.1×3+0.1×3＝1.7ビット、エは一律2ビットなので、ウが最短となる。出現頻度の高い文字へ短い符号を割り当てるハフマン符号の考え方である。

選択肢ごとの解説

• アaの0がcの00の先頭になっており、語頭条件を満たさないため一意に復号できない。
• イaの0がbの01の先頭になっており、やはり一意に復号できない。
• ウ正しい。語頭条件を満たし、平均符号長は1.7ビットで4案中最短である。
• エ語頭条件は満たすが、全て2ビット固定なので平均符号長は2.0ビットとなりウに劣る。

同じ分野の他の問題

• AIにおける機械学習において、2クラス分類モデルの評価方法の一つであるROC曲線で用いられる偽陽性率の説明として、最も適…2025年度 秋期 問2
• コンピュータによる伝票処理システムがある。このシステムは、伝票データをためる待ち行列をもち、M/M/1の待ち行列モデルが…2018年度 秋期 問2
• AIにおける機械学習の過程において、過学習と疑われたときの解消方法として、最も適切なものはどれか。2025年度 春期 問2
• 0≦x≦1の範囲で単調に増加する連続関数f(x)がf(0)<0≦f(1)を満たすときに、区間内でf(x)=0であるxの値…2025年度 春期 問1
• 式A+B×Cの逆ポーランド表記法による表現として、適切なものはどれか。2020年度 10月試験 問1