レンジ符号

レンジ符号（レンジふごう、range encoding）は、エントロピー符号の一種である。

G. Nigel N. Martinが1979年の論文で定義した^[1]。これは、1976年にRichard Clark Pascoによって最初に導入されたFIFO算術符号を効果的に再発見したものである^[2]。シンボルのストリームとそれらの確率が与えられると、レンジコーダ (Range Coder) は、これらのシンボルを表す空間効率のよいビットストリームを生成し、ストリームと確率が与えられると、レンジデコーダ (range decoder) はその逆のプロセスを行う。

レンジ符号は算術符号と非常によく似ているが、符号化をビットではなく任意の基数の数字で行う点が異なる。従って、より大きな基数（例えばバイト）を圧縮効率をわずかに犠牲にして使用する方が高速である^[3]。レンジ符号自体についてアルゴリズム考案者が特許を取らなかったため、最初の算術符号の特許（1978年）^[4]の満了後は、レンジ符号は明らかに特許の制限から解放された。このため、特に、オープンソースコミュニティにおいてこの技術への関心が高まった。その時以降、様々な周知の算術符号技術に関する特許も失効している。1998年のMichael Schindlerの発表によって注目を集め、1999年には、Дмитрий Субботин (Dmitry Subbotin) が「русский народный rangecoder（Russian people's rangecoder/ロシア人民のレンジコーダ）」という名称で桁上がりのないレンジコーダを発表した。

レンジコーダは、Jones符号と呼ばれる、整数で算術符号を実現したアルゴリズムをもとに確率空間を下端と区間範囲で表すようにしたものである。精度の面では算術符号に劣るが、出力単位が1bitである算術符号に対して8bit単位で処理するため高速である。

レンジ符号の仕組み

レンジ符号は、各シンボルにビットパターンを割り当て全てのビットパターンを一緒に連結するハフマン符号とは異なり、メッセージの全てのシンボルを概念的に1つの数に符号化する。これにより、レンジ符号は、ハフマン符号のシンボル当たり1ビットの下限より大きな圧縮率を達成することができ、正確に2の累乗ではない確率を扱う場合にハフマン符号で発生する非効率性が起こることもない。

レンジ符号の背後にある中心的な概念は、次の通りである。十分な範囲の整数とシンボルの確率推定が与えられた場合、初期範囲は、それらが表す記号の確率に比例したサイズの部分範囲に容易に分割することができる。次に、メッセージの各シンボルは、現在の範囲を、符号化される次のシンボルに対応するその部分範囲だけに縮小することによって、順に符号化することができる。デコーダは、エンコーダが使用したのと同じ確率推定を有さなければならない。それは、事前に送付するか、既に転送されたデータから導出するか、圧縮器と復元器の一部として組み込んでおく必要がある。

全てのシンボルが符号化されている場合、部分範囲を識別するだけでメッセージ全体を通信することができる（もちろん、デコーダがメッセージ全体を抽出したときに何らかの形で通知されると仮定する）。部分範囲を識別するのに実際には1つの整数で十分であり、整数全体を送信する必要はない場合もある。全ての整数が部分範囲内に入るプレフィックスで始まる一連の数字がある場合、プレフィックスだけが、部分範囲を識別してメッセージを送信するために必要な全てである。

例

例として、「AABA <EOM>」というメッセージを符号化する。ここで、<EOM>はメッセージの終わりの記号である。この例において、復号器は、確率分布 {A: .60; B: .20; <EOM>: .20} を使用して、基数10のシステム（[0, 100000) の範囲で10⁵個の異なる組み合わせが可能）において、正確に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>を表す。

算術符号との関係

算術符号はレンジ符号と同じだが、整数は分数の分子とみなされる。これらの分数は、すべての分数が [0,1) の範囲に入るような暗黙の共通分母を有する。従って、算術符号は、暗黙の「0」で始まると解釈される。これらは同じ符号化方法の異なる解釈であり、算術符号とレンジ符号は同一であるため、算術符号器は対応するレンジコーダであり、その逆も同様である。言い換えれば、算術符号とレンジ符号は、同じことを理解するわずかに異なる2つの方法である。

実際には、いわゆる「レンジエンコーダ」はマーティンの論文^[1]に記載されているように実装される傾向があるが、算術コーダは一般的にレンジエンコーダと呼ばれがちである。このようなレンジエンコーダの多くの特徴は、（一般的にそうであるように）一度に1ビットではなく、一度に1バイトずつ再正規化を実行する傾向があることである。言い換えれば、レンジエンコーダは、ビットではなくエンコード数字としてバイトを使用する傾向がある。これにより、達成可能な圧縮量は非常に小さい量だけ減るが、ビットごとに再正規化を行うよりも高速である。

脚注

1 2 G. Nigel N. Martin, Range encoding: An algorithm for removing redundancy from a digitized message, Video & Data Recording Conference, Southampton, UK, July 24–27, 1979.
↑ "Source coding algorithms for fast data compression" Richard Clark Pasco, Stanford, CA 1976
↑ "On the Overhead of Range Coders", Timothy B. Terriberry, Technical Note 2008
↑ アメリカ合衆国特許第 4,122,440号 — (IBM) Filed March 4, 1977, Granted 24 October 1978 (Now expired)

外部リンク

[compressconsult-1] 1 2 G. Nigel N. Martin, Range encoding: An algorithm for removing redundancy from a digitized message, Video & Data Recording Conference, Southampton, UK, July 24–27, 1979.

[2] "Source coding algorithms for fast data compression" Richard Clark Pasco, Stanford, CA 1976

[3] "On the Overhead of Range Coders", Timothy B. Terriberry, Technical Note 2008

[4] アメリカ合衆国特許第 4,122,440号 — (IBM) Filed March 4, 1977, Granted 24 October 1978 (Now expired)

[1]

[2]

[3]

[4]

レンジ符号の仕組み

例

算術符号との関係

関連項目

脚注

外部リンク