06/03/01 04:02:46
>>456 >>459
Schalkwijk の数え上げ符号
長さ n のバイナリ文字列中に 1 の個数が w 個あるものを考える
このとき、インデクス i
i = Σj=1,n x[j] n-j C w[j]
を用いて1対1に対応付けすることができる。ただし、w[j] = Σi=j, n x[i]
符号化は、まず、1 の個数 w を ceil(log n) ビットの2進数で出力する
次に、インデクス i を ceil(log k C w) ビットの2進数で出力する
なお、ceil() は切り上げ
この符号化は、1記号あたりエントロピーまで漸近的に圧縮可能