レンジ符号
レンジ符号自体についてアルゴリズム考案者が特許を取らなかったため、最初の算術符号の特許(1978年)の満了後は、レンジ符号は明らかに特許の制限から解放された。このため、特に、オープンソースコミュニティにおいてこの技術への関心が高まった。その時以降、様々な周知の算術符号技術に関する特許も失効している。1998年のMichael Schindlerの発表によって注目を集め、1999年には、Дмитрий Субботин (Dmitry Subbotin) が「русский народный rangecoder(Russian people's rangecoder/ロシア人民のレンジコーダ)」という名称で桁上がりのないレンジコーダを発表した。
レンジコーダは、Jones符号と呼ばれる、整数で算術符号を実現したアルゴリズムをもとに確率空間を下端と区間範囲で表すようにしたものである。精度の面では算術符号に劣るが、出力単位が1bitである算術符号に対して8bit単位で処理するため高速である。
上記の Encode 関数で発生する可能性のある問題の1つは、range が非常に小さいのに、low と low+range が依然として1桁目が異なる可能性があることである。これは、アルファベット中のすべてのシンボルを区別するのに不十分な精度を有する間隔をもたらす可能性がある。これが起こったとき、我々は、少し離れているにもかかわらず、最初の2桁の数字を出力し、可能な限り多くのスペースを与えるために範囲を再調整する必要がある。復号器は同じ手順に従うので、いつ同期をとる必要があるかを知ることができる。
この例では基数10を使用したが、実際の実装では、完全な範囲のネイティブ整数データ型で二進数を使用する。10000 や 1000 の代わりに、0x1000000 や 0x10000 のような十六進数の定数を使用する。十進数の数字を出力するのではなくバイトを出力し、10を掛けるのではなくバイトシフトを使用する。
復号では、圧縮器から読み取った数字で構成される現在の code の値を記録し続けることで、全く同じアルゴリズムを使用する。先頭の low 桁を出力する代わりに、先頭の code 桁をシフトして、圧縮器から読み取った新しい桁をシフトする。EmitDigit ではなく AppendDigit を使用する。
どの確率区間を適用するかを決定するために、復号器は区間 [low, low+range) 内の code の現在の値を調べ、これがどのシンボルを表すかを決定する必要がある。
上記の「AABA<EOM>」の例では、0から9の範囲の値が返される。値0から5はA、6と7はB、8と9は<EOM>を表す。
算術符号はレンジ符号と同じだが、整数は分数の分子とみなされる。これらの分数は、すべての分数が [0,1) の範囲に入るような暗黙の共通分母を有する。従って、算術符号は、暗黙の「0」で始まると解釈される。これらは同じ符号化方法の異なる解釈であり、算術符号とレンジ符号は同一であるため、算術符号器は対応するレンジコーダであり、その逆も同様である。言い換えれば、算術符号とレンジ符号は、同じことを理解するわずかに異なる2つの方法である。
実際には、いわゆる「レンジエンコーダ」はマーティンの論文に記載されているように実装される傾向があるが、算術コーダは一般的にレンジエンコーダと呼ばれがちである。このようなレンジエンコーダの多くの特徴は、(一般的にそうであるように)一度に1ビットではなく、一度に1バイトずつ再正規化を実行する傾向があることである。言い換えれば、レンジエンコーダは、ビットではなくエンコード数字としてバイトを使用する傾向がある。これにより、達成可能な圧縮量は非常に小さい量だけ減るが、ビットごとに再正規化を行うよりも高速である。