範囲コーディング

範囲コーディング（または範囲エンコーディング）は、G. Nigel N. Martinが1979年の論文^{[1]で定義した}エントロピーコーディング方式であり、 1976年にRichard Clark Pascoが初めて導入したFIFO算術コードを事実上再発見しました^[2]。シンボルのストリームとその確率が与えられると、範囲コーダはこれらのシンボルを表すスペース効率の高いビットストリームを生成し、ストリームと確率が与えられると、範囲デコーダはそのプロセスを逆にします。

範囲符号化は算術符号化と非常によく似ていますが、符号化がビットではなく任意の基数の数字で行われる点が異なります。そのため、より大きな基数（バイトなど）を使用すると圧縮効率がわずかに低下するだけで高速になります。^[3]最初の（1978年）算術符号化の特許の期限が切れた後、^[4]範囲符号化は明らかに特許の制約から解放されたように見えました。これは特にオープンソースコミュニティでこの技術への関心を高めました。それ以来、さまざまなよく知られた算術符号化技術の特許も期限が切れています。

範囲コーディングは、各シンボルにビットパターンを割り当て、すべてのビットパターンを連結するハフマンコーディングとは異なり、概念的にはメッセージのすべてのシンボルを 1 つの数値にエンコードします。したがって、範囲コーディングは、ハフマンコーディングの 1 シンボルあたり 1 ビットの下限よりも高い圧縮率を達成でき、2 の累乗ではない確率を扱うときにハフマンが抱える非効率性に悩まされることはありません。

範囲コーディングの中心的な概念は次のとおりです。十分に大きい整数の範囲とシンボルの確率推定が与えられれば、初期範囲は、サイズがそれらが表すシンボルの確率に比例するサブ範囲に簡単に分割できます。次に、現在の範囲を、次にエンコードするシンボルに対応するサブ範囲にまで縮小することで、メッセージの各シンボルを順番にエンコードできます。デコーダーは、エンコーダーが使用したのと同じ確率推定を持っている必要があります。これは、事前に送信することも、すでに転送されたデータから導出することも、コンプレッサーとデコンプレッサーの一部にすることもできます。

すべてのシンボルがエンコードされると、サブ範囲を識別するだけでメッセージ全体を伝達できます (もちろん、デコーダーがメッセージ全体を抽出したときに何らかの方法で通知されることを前提としています)。サブ範囲を識別するには実際には 1 つの整数で十分であり、整数全体を送信する必要すらない場合もあります。プレフィックスで始まるすべての整数がサブ範囲内に含まれるような数字のシーケンスがある場合、プレフィックスだけでサブ範囲を識別し、メッセージを送信できます。

メッセージ「AABA<EOM>」をエンコードするとします。ここで、<EOM> はメッセージ終了シンボルです。この例では、確率分布{A: .60; B: .20; <EOM>: .20} を使用して、10 進数システムで正確に 5 つのシンボルをエンコードする(範囲 [0, 100000) の10 ⁵通りのシンボルの組み合わせを許可)ことをデコーダーが認識していると想定しています。エンコーダーは、範囲 [0, 100000) を 3 つのサブ範囲に分割します。

答え: [ 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下限= 0 ; int範囲= 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 ();	   
		

	低+= 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 ();   
	

低+= 10000 ; EmitDigit ();  

Encode上記の関数で発生する可能性がある問題の 1 つは、range非常に小さくなってlowもlow+range最初の桁が異なる可能性があることです。これにより、間隔の精度が不十分になり、アルファベットのすべての記号を区別できなくなる可能性があります。このような状況が発生した場合は、少し調整して、1 桁ずれていても最初の 2 桁を出力し、範囲を再調整して可能な限り多くの余裕を持たせる必要があります。

たとえば、入力ストリームがエンコーダーを右開きの区間 [59888, 60188)、つまりlow = 59888およびに導いたとします。秘訣は、区間を [59888, 60000) = [ 59 888, 59range = 300 999]に狭め、これによりエンコーダーが の左端の 2 桁を出力し、区間を [88800, 99999] = [88800, 100000)、つまりおよびに再調整することです。 lowlow = 88800range = 100000 - low

デコーダーは同じ手順を実行するため、同期を維持するためにいつこれを行う必要があるかがわかります。

// これは上記の Encode() の終了直前に行われます
if ( range < 1000 ) { EmitDigit (); EmitDigit (); range = 100000 - low ; }   

	
	
	    

この例では 10 進数が使用されていますが、実際の実装では、ネイティブ整数データ型の全範囲を持つバイナリが使用されます。10000との代わりに、や1000などの 16 進定数を使用することになります。一度に 1 桁を出力する代わりに、一度に 1 バイトを出力し、10 倍する代わりにバイト シフト演算を使用します。 0x10000000x10000

codeデコードでは、コンプレッサーから読み取った数字で構成される現在の値を追跡する点を除いて、まったく同じアルゴリズムを使用します。 の上位の数字を出力する代わりにlow、それを単に破棄しますが、 の上位の数字をシフトアウトし、コンプレッサーから読み取った新しい数字をシフトインします。の代わりに以下をcode使用します。 AppendDigitEmitDigit

intコード= 0 ; int下限= 0 ; int範囲= 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 ) // Decode は、EmitDigit を AppendDigit に置き換えた Encode と同じです{ // シンボル間隔に基づいて範囲を調整しますrange /= total ; low += start * range ; range *= size ;        

	
	  
	    
	  

	// 左端の数字が範囲全体で同じかどうかを確認します
while ( low / 10000 == ( low + range ) / 10000 ) AppendDigit ();	         
		

	// 範囲を再調整します - 理由は以下を参照してください
if ( range < 1000 ) { AppendDigit (); AppendDigit (); range = 100000 - low ; } }	   
	
		
		
		    
	

どの確率間隔を適用するかを決定するために、デコーダーはcode間隔 [low、low+range) 内の現在の値を確認し、これがどのシンボルを表すかを決定する必要があります。

void Run () { int start = 0 ; int size ; int total = 10 ; InitializeDecoder (); // 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 つのわずかに異なる方法にすぎません。

しかし実際には、いわゆるレンジエンコーダはMartin の論文^[1]で説明されているとおりに実装される傾向があり、算術コーダは一般的にレンジ エンコーダとは呼ばれない傾向があります。このようなレンジ エンコーダでよく注目される特徴は、(通常は 1 ビットずつ) 再正規化を実行するのではなく、1 バイトずつ再正規化を実行する傾向があることです。言い換えると、レンジ エンコーダはビットではなくバイトをコーディング ディジットとして使用する傾向があります。これにより、達成できる圧縮量はごくわずかですが、各ビットの再正規化を実行する場合よりも高速になります。

• 算術符号化
• 非対称の数字体系
• データ圧縮
• エントロピー符号化
• ハフマン符号化
• マルチスケール電気生理学フォーマット
• シャノン・ファノ符号

• レンジエンコーダ
• 「レンジコーダー」Arturo Campos
• 「レンジエンコーダの解剖学」Andrew Polar 著
• James K. Bonfield による範囲コーディングと rANS の高速実装
• 24 ビット SSE 4.1 インターリーブ レンジ コーダの高速オープン ソース実装