p20190513a

レンジコーダ

• (by K, 2019.05.13)

(1)

• 予測確率が1:1のとき、レンジコーダは当たっても外れても1ビットを出力する。
• 予測確率が3:1のとき、レンジコーダは外れた時に2ビットを出力する。当たった時には0.4150ビットを出力する（1/2.410）。
• 予測確率が7:1のとき、レンジコーダは外れた時に3ビットを出力する。当たった時には0.1926ビットを出力する（1/5.192）。
• 予測確率が15:1のとき、レンジコーダは外れた時に4ビットを出力する。当たった時には0.09311ビットを出力する（1/10.74）。
• 予測確率が31:1のとき、レンジコーダは外れた時に5ビットを出力する。当たった時には0.04580ビットを出力する（1/21.83）。
• 予測確率が63:1のとき、レンジコーダは外れた時に6ビットを出力する。当たった時には0.02272ビットを出力する（1/44.01）。
• 予測確率が127:1のとき、レンジコーダは外れた時に7ビットを出力する。当たった時には0.01132ビットを出力する（1/88.38）。
• 予測確率が255:1のとき、レンジコーダは外れた時に8ビットを出力する。当たった時には0.005647ビットを出力する（1/177.1）。

(2)

• 古すぎる統計はたぶん捨てるべき。とすると、カウンタはどのくらいがいいのだろうか？
• 仮に256ビットの履歴があれば最大で1/177.1までは行くのだから、まあそれで十分なのではないか。
• どこまでさかのぼれるのか？
• いやそんなに遠くの統計があってもかえってノイズになるだけなのでは？基本的に統計は16ビット分くらいあれば十分で、オール0とかオール1のときにだけ、特別な扱いをすればいいのではないかと思う。
• まあゼロを回避するのなら、"0"と"1"をそれぞれ加算すればいい。でも加算量が1とは限らないな・・・。
• やっぱり一方に偏った時だけ特別な確率にするほうがよさそう。

(3)

• n-グラム的にする。バイト区切りかニブル区切りかは、まあデータによるかな。
  • 0バイト+0〜7ビット。
  • 1バイト+0〜7ビット。
  • 2バイト+0〜7ビット。
  • 3バイト+0〜7ビット。
  • 4バイト+0〜7ビット。
• これでかなりスパースな配列になる。ハッシュテーブルにすれば結構いけそうではある。