レンジ符号
レンジ符号は、各シンボルにビットパターンを割り当て全てのビットパターンを一緒に連結するハフマン符号とは異なり、メッセージの全てのシンボルを概念的に1つの数に符号化する。これにより、レンジ符号は、ハフマン符号のシンボル当たり1ビットの下限より大きな圧縮率を達成することができ、正確に2の累乗ではない確率を扱う場合にハフマン符号で発生する非効率性が起こることもない。
レンジ符号の背後にある中心的な概念は、次の通りである。十分な範囲の整数とシンボルの確率推定が与えられた場合、初期範囲は、それらが表す記号の確率に比例したサイズの部分範囲に容易に分割することができる。次に、メッセージの各シンボルは、現在の範囲を、符号化される次のシンボルに対応するその部分範囲だけに縮小することによって、順に符号化することができる。デコーダは、エンコーダが使用したのと同じ確率推定を有さなければならない。それは、事前に送付するか、既に転送されたデータから導出するか、圧縮器と復元器の一部として組み込んでおく必要がある。
全てのシンボルが符号化されている場合、部分範囲を識別するだけでメッセージ全体を通信することができる(もちろん、デコーダがメッセージ全体を抽出したときに何らかの形で通知されると仮定する)。部分範囲を識別するのに実際には1つの整数で十分であり、整数全体を送信する必要はない場合もある。全ての整数が部分範囲内に入るプレフィックスで始まる一連の数字がある場合、プレフィックスだけが、部分範囲を識別してメッセージを送信するために必要な全てである。