Problem 219 のバックアップ(No.1)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Problem 219 へ行く。
  • 1 (2009-02-28 (土) 11:33:46)

Problem 219 「非対称コスト符号化」 †

AとBをビット列(0と1の連続列)とする.
Bの左端から"Aの長さ"ビットがAと一致する時, AをBの"接頭部"(prefix)と呼ぶ.
例えば 00110 は 001101001 の接頭部だが, 00111 や 100110 の接頭部ではない.

サイズnの"接頭符号"(prefix-free code)とは, 次の条件を満たす n 個の異なるビット列の集合である: どのビット列も他のビット列の接頭部ではない. 下の例はサイズ6の接頭符号である.

ここでビット0を送るのに1ペニー, ビット1を送るのに4ペンスかかると仮定する.
上で挙げた接頭符号にかかる総計は35ペンスとなる. この例は非対称なコスト分布となるが, なんと(同じサイズの中で)もっとも安い符号の１つである. 短く書くと, Cost(6)=35 となる.

Cost(10&sup{9};)を求めよ.

[訳注 ペンス: ペニーの複数形]