算術圧縮

生起確率を0〜1の小数で表わし、それを用いて全体を符号化する。

そもそも、ハフマン符号では木を用いて文字に符号を割り当てるが、木の枝は常に整数である。このため生起確率が1/3や1/5のように整数にならない符号に対しても整数ビット分の符号を割り当てざるをえない。この問題が、圧縮率の低下を招いていた。

一方、もしデータを生起確率を元に分数で表現したとすると、その分数を表現するために必要なビット数はエントロピー限界に漸近する。

そこで、確率を整数で扱うことをやめ浮動小数点数で扱うことで圧縮率を高めたのが、算術符号である。

浮動小数点数による計算はコストが高く、処理が遅い。

そこで、精度を多少犠牲にして、計算を整数のみ、つまり固定小数点で扱う方法が考えられた。これがJones符号であり、生起確率区間は0以上の整数とする。

また、このJones符号を変形したものとしてRangeCoderが作られた。算術圧縮は生起確率区間を下端〜上端で表わしたが、RangeCoderはこれを下端と区間幅で表わし、式を変更した。

RangeCoderは特許がとられておらず安全である。一応、算術符号とは式が違うため算術符号の特許には抵触しないとされているが、かなりグレーではある。