語頭条件とは？

語頭条件の意味

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

語頭条件の具体例

{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の割当てだけで、平均符号長は1×0.5＋2×0.3＋3×0.1＋3×0.1＝1.7ビットとなる。固定長2ビットの割当てより短く、これが最短となる。

  出典：平成28年度 春期 高度共通_午前I試験 am1 問2（IPA）

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

  正解：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ビットなので、ウが最短となる。出現頻度の高い文字へ短い符号を割り当てるハフマン符号の考え方である。

  出典：令和2年度 10月 高度共通_午前I試験 am1 問2（IPA）