レンジ符号
レンジ符号の仕組み > 例

例として、「AABA <EOM>」というメッセージを符号化する。ここで、<EOM>はメッセージの終わりの記号である。この例において、復号器は、確率分布 {A: .60; B: .20; <EOM>: .20} を使用して、基数10のシステム（[0, 100000) の範囲で105個の異なる組み合わせが可能）において、正確に5つのシンボルを符号化しようとしていることを知っていると仮定する。符号器は、次のように [0, 100000) の範囲を3つの部分範囲に分割する。
A:     [     0,  60000)
B:     [ 60000,  80000)
<EOM>: [ 80000, 100000)
最初のシンボルはAであるため、初期範囲は [0, 60000) に縮小される。2番目のシンボルの選択は、我々にこの範囲の3つの部分範囲を残す。我々はそれが、既に符号化された「A」に続くのを見る。
AA:     [     0,  36000)
AB:     [ 36000,  48000)
A<EOM>: [ 48000,  60000)
2つのシンボルが符号化されていれば、残る範囲は [0, 36000) であり、3番目のシンボルは次の選択肢につながる。
AAA:     [     0,  21600)
AAB:     [ 21600,  28800)
AA<EOM>: [ 28800,  36000)
ここで、符号化するメッセージを表す3つの選択肢のうち2番目のもので、範囲は [21600, 28800) になる。このケースでは、部分範囲を決定するのが難しくなるかもしれないが、実際にはそうではない。上界から下限を差し引いて、範囲内に7200個の数字があることを確認するだけである。最初の4320は0.60の合計を表し、次の1440は次の0.20を表し、残りの1440は合計の0.20を表す。下限を加えると、範囲がわかる。
AABA:     [21600, 25920)
AABB:     [25920, 27360)
AAB<EOM>: [27360, 28800)
最後に、範囲を [21600, 25920) に絞り込む。エンコードする記号がもう1つだけある。前と同じ手法を使用して、下限と上限の間の範囲を分割すると、3つの部分範囲は次のようになる。
AABAA:     [21600, 24192)
AABAB:     [24192, 25056)
AABA<EOM>: [25056, 25920)
<EOM>はメッセージの終わりの記号なので、最終的な範囲は [25056, 25920) である。"251" で始まる5桁の整数はすべて最終的な範囲に入るため、元のメッセージを明確に伝える3桁の接頭辞の1つである（実際には、このようなプレフィックスが8つもあるということは、非効率性があることを意味する。これは、基数2ではなく基数10を使用したために起こったものである）。
中心的な問題は、符号化しなければならないシンボルの数にかかわらず、ゼロ以外の部分範囲に分割するのに十分な大きさの現在の範囲を常に持つために、十分に大きな範囲の初期範囲を選択しているように見えることである。しかし、実際には、これは問題ではない。非常に大きな範囲から始めて徐々に狭くするのではなく、任意の時点でより小さな範囲の数値で動作するためである。いくつかの桁数が符号化された後、左端の桁は変更されない。3つのシンボルだけを符号化した後の例では、我々は最終結果が "2" で始まることを既に知っていた。左側の数字が送信されると、右側の数字がより多くシフトされる。これは次のコードで説明されている。
int low = 0;
int range = 100000;

void Run()
{
	Encode(0, 6, 10);	// A
	Encode(0, 6, 10);	// A
	Encode(6, 2, 10);	// B
	Encode(0, 6, 10);	// A
	Encode(8, 2, 10);	// <EOM>

	// 最後の数字を出力する - 下記を参照
	while (range < 10000)
		EmitDigit();

	low += 10000;
	EmitDigit();
}

void EmitDigit()
{
	Console.Write(low / 10000);
	low = (low % 10000) * 10;
	range *= 10;
}

void Encode(int start, int size, int total)
{
	// シンボルの間隔に基づいて範囲を調整する
	range /= total;
	low += start * range;
	range *= size;

	// 一番左の数字が範囲全体で同じかどうかを調べる
	while (low / 10000 == (low + range) / 10000)
		EmitDigit();

	// 範囲を再調整する - 以下の理由を参照
	if (range < 1000)
	{
		EmitDigit();
		EmitDigit();
		range = 100000 - low;
	}
}
終了するには、いくつかの桁を追加する必要がある。low の最上位はおそらく小さすぎるので、それを増やす必要があるが、low+range は増やさないようにする必要がある。最初に、range が十分に大きいことを確認する必要がある。
// 最後の数字を出力する
while (range < 10000)
	EmitDigit();

low += 10000;
EmitDigit();
上記の Encode 関数で発生する可能性のある問題の1つは、range が非常に小さいのに、low と low+range が依然として1桁目が異なる可能性があることである。これは、アルファベット中のすべてのシンボルを区別するのに不十分な精度を有する間隔をもたらす可能性がある。これが起こったとき、我々は、少し離れているにもかかわらず、最初の2桁の数字を出力し、可能な限り多くのスペースを与えるために範囲を再調整する必要がある。復号器は同じ手順に従うので、いつ同期をとる必要があるかを知ることができる。
// これは上記のEncode()の終わりの直前である
if (range < 1000)
{
	EmitDigit();
	EmitDigit();
	range = 100000 - low;
}
この例では基数10を使用したが、実際の実装では、完全な範囲のネイティブ整数データ型で二進数を使用する。10000 や 1000 の代わりに、0x1000000 や 0x10000 のような十六進数の定数を使用する。十進数の数字を出力するのではなくバイトを出力し、10を掛けるのではなくバイトシフトを使用する。
復号では、圧縮器から読み取った数字で構成される現在の code の値を記録し続けることで、全く同じアルゴリズムを使用する。先頭の low 桁を出力する代わりに、先頭の code 桁をシフトして、圧縮器から読み取った新しい桁をシフトする。EmitDigit ではなく AppendDigit を使用する。
int code = 0;
int low = 0;
int range = 1;

void InitializeDecoder()
{
        AppendDigit();  // このサンプルコードでは、これらのうちの1つだけが実際に必要となる
        AppendDigit();
        AppendDigit();
        AppendDigit();
        AppendDigit();
}

void AppendDigit()
{
	code = (code % 10000) * 10 + ReadNextDigit();
	low = (low % 10000) * 10;
	range *= 10;
}

void Decode(int start, int size, int total)  // 復号は EmitDigit が Encend と同じで、AppendDigit に置き換えられる
{
	// シンボルの間隔に基づいて範囲を調整する
	range /= total;
	low += start * range;
	range *= size;

	// 一番左の数字が範囲全体で同じかどうかを調べる
	while (low / 10000 == (low + range) / 10000)
		AppendDigit();

	// 範囲を再調整する - 以下の理由を参照
	if (range < 1000)
	{
		AppendDigit();
		AppendDigit();
		range = 100000 - low;
	}
}
どの確率区間を適用するかを決定するために、復号器は区間 [low, low+range) 内の code の現在の値を調べ、これがどのシンボルを表すかを決定する必要がある。
void Run()
{
	int start = 0;
	int size;
	int total = 10;
	AppendDigit();                    // need to get range/total >0
	while (start < 8)                 // EOM受信時に停止する
	{
		int v = GetValue(total);  // 符号がどのシンボルの範囲にあるか?
		switch (v)                // 値をシンボルに変換する
		{
			case 0:
			case 1:
			case 2:
			case 3:
			case 4:
			case 5: start=0; size=6; Console.Write("A"); break;
			case 6:
			case 7: start=6; size=2; Console.Write("B"); break;
			default: start=8; size=2; Console.WriteLine("");
		}
		Decode(start, size, total);
	}
}

int GetValue(int total)
{
        return (code - low) / (range / total);
}
上記の「AABA<EOM>」の例では、0から9の範囲の値が返される。値0から5はA、6と7はB、8と9は<EOM>を表す。