レンジ符号

レンジ符号（レンジふごう、range encoding）は、エントロピー符号の一種である。 G. Nigel N. Martinが1979年の論文で定義した。これは、1976年にRichard Clark Pascoによって最初に導入されたFIFO算術符号を効果的に再発見したものである。シンボルのストリームとそれらの確率が与えられると、レンジコーダ (Range Coder) は、これらのシンボルを表す空間効率のよいビットストリームを生成し、ストリームと確率が与えられると、レンジデコーダ (range decoder) はその逆のプロセスを行う。 レンジ符号は算術符号と非常によく似ているが、符号化をビットではなく任意の基数の数字で行う点が異なる。従って、より大きな基数（例えばバイト）を圧縮効率をわずかに犠牲にして使用する方が高速である。レンジ符号自体についてアルゴリズム考案者が特許を取らなかったため、最初の算術符号の特許（1978年）の満了後は、レンジ符号は明らかに特許の制限から解放された。このため、特に、オープンソースコミュニティにおいてこの技術への関心が高まった。その時以降、様々な周知の算術符号技術に関する特許も失効している。1998年のMichael Schindlerの発表によって注目を集め、1999年には、Дмитрий Субботин (Dmitry Subbotin) が「русский народный rangecoder（Russian people's rangecoder/ロシア人民のレンジコーダ）」という名称で桁上がりのないレンジコーダを発表した。 レンジコーダは、と呼ばれる、整数で算術符号を実現したアルゴリズムをもとに確率空間を下端と区間範囲で表すようにしたものである。精度の面では算術符号に劣るが、出力単位が1bitである算術符号に対して8bit単位で処理するため高速である。