語頭条件とは？

語頭条件の意味

ある符号語が、他のどの符号語の先頭部分にもなっていないという条件。これを満たす符号は、区切り記号なしでも先頭から順に一意に復号できる。

語頭条件の具体例

{0, 10, 110, 111} は語頭条件を満たす。一方 {0, 01} は「0」が「01」の先頭なので満たさず、復号が曖昧になる。

語頭条件は試験でどう引っ掛けられる？

条件は「ある符号語が他の符号語の先頭と一致しない」ことであって、「符号語の長さが全部違う」ことでも「全ビットが異なる」ことでもない。等長符号 {00,01,10,11} も語頭条件を満たす。またハフマン符号は必ず語頭条件を満たすので、「ハフマン符号だが語頭条件を満たさない」という選択肢は誤り。

語頭条件と関連する用語

• ハフマン符号

語頭条件が出た過去問

• a，b，c，dの4文字から成るメッセージを符号化してビット列にする方法として表のア～エの4通りを考えた。この表はa，b，c，dの各1文字を符号化するときのビット…

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

  要点：語頭条件を満たし出現頻度が高い文字ほど短い符号が最適

  一意に復号するには、どの符号語も他の符号語の先頭部分になっていない（語頭条件を満たす）必要がある。この条件を満たすのは0/10/110/111と2ビット固定長の2つで、平均符号長は前者が0.5×1+0.3×2+0.1×3+0.1×3=1.7ビット、後者が2ビットとなり、前者が短い。

  出典：平成28年度 春期 応用情報技術者試験 午前 問4（IPA）

• a, b, c, dの4文字から成るメッセージを符号化してビット列にする方法として表のア〜エの4通りを考えた。この表はa, b, c, dの各1文字を符号化する…

  正解：表ウの符号化方式（a:0, b:10, c:110, d:111）

  要点：語頭条件を満たしつつ高頻度文字を短く符号化すると最短

  一意に復号するには、ある符号語が他の符号語の先頭部分になっていない（語頭条件を満たす）必要がある。語頭条件を満たすのはウとエで、平均符号長はウが0.5×1＋0.3×2＋0.1×3＋0.1×3＝1.7ビット、エは一律2ビットである。したがってウが最も短くなる。

  出典：令和2年度 10月 応用情報技術者試験 午前 問4（IPA）