Range Coderの詳細
Range Coder（RC）は算術圧縮を高速に処理可能な符号法です。もともと1979年にMartinによって提唱され（算術圧縮とは独立に提案されたため、特許フリーだと言われている）、その後szipの開発者であるM. Schindlerが1998年に有効であると再提言しました。
RCはACと同様に内部状態でLとRを保持します。LとRはそれぞれ32bit整数です（64bit整数にしても良いが圧縮率はそれほど変わらない）。また、各文字xの出現確率p(x)は、文字xの出現回数c(x)と、すべての文字の出現回数の和 totalを用いてp(x) = c(x)/total と表されます（必ずしも出現回数でなくても良い）。Cum(x)をxより小さい文字の出現回数の和と定義します。この時、Cum(x) / total = cum(x) が成立します。
文字xを符号化する時を考えます。low := Cum(x), high := Cum(x+1)と定義すると、Cumの定義からc(x) = high-lowが成り立ちます。ACの更新式に従ってRを更新するときは次のとおりになります。
R := R * p(T[i]) = R * c(x) / total = R / total * (high-low)
R/totalを先に計算するのはR * c(x)を先に計算した場合、桁あふれが発生するためです。しかし、R/totalを計算した結果も整数除算のため打ち切り誤差が発生し、このまま使うと圧縮率の低下につながります。そこで、最も大きい文字kに残りの区間をすべて与えます。これより、Rの更新式は次のとおりになります。
uint r = R / total; if (high < total){ R = r * (high-low); } else { R -= r * low; }
次にLの更新です。これも更新式に従うと、
L := L + R * cum(x) = L + R * low / total = L + R / total * low
となります。
LとRを更新し終わった後、前章の最後で説明したようにVの上位が決まった順に出力し、RとLをシフトします。RCの場合、Vの上位8桁が決定し次第、出力します。これはRが TOP := (1U << 24)未満になった時です。なぜならR < TOPの時、S = L>>24 （Lの上位8桁）とおくと、L <= V < L+R <= L+TOP を満たすVの上位8桁はSもしくはS+1となるからです。S+1となる場合はLとRの下位24bit同士の和が繰り上がりを起こす場合です（注：R == TOPの場合も同様に上位8桁は決定されるが、シフト演算の際、桁あふれする）。よって、R < TOPの時、Lの上位8桁をそのまま出力せずにbufferに保存しておき、繰り上がりが発生した場合buffer+1、発生しなかった場合はそのままbufferを出力します。さらにbuffer=0xFF=(11111111)の時、下位に繰り上がりが発生した場合、bufferの上位に連鎖的に繰り上がりが伝播します。そのためbufferには最後の0xFFでは無かった値を保存しておき、carryNに0xFFが連続して何回出現回数を保存することにします。bufferとcarryNを用いて、現在出力待ちの符号は、
buffer 0xFF 0xFF ... （carryN回 0xFFの繰り返し） ... 0xFF
と表されます（carryN=0の場合もある）。繰り上がりが発生した場合は buffer+1 0x00 0x00 ... （carryN-1個の0の0x00の繰り返し）... 0x00、発生しなかった場合はbuffer 0xFF 0xFF ...（carryN回） ... 0xFF を出力します。前者で0x00の出力がcarryN回ではなくcarryN-1回なのは、最後の0x00はbufferに保存するためです。
下位（求める段階では最上位）で繰り上がりが発生したかの判定は次の式で求めます。
uint newL = L + r*low; if (newL < L){ //繰り上がりが発生した場合の処理 }
L + r*lowが繰り上がり（32bitのover flow）をおこした場合、2^32の余りがnewLに代入されます。この値は必ずLより小さいのでL < newLの判定を行うことでL + r*lowが繰り上がりをおこしたかどうかが判定できます。これらをまとめると、LとRが更新し終わった後の処理は次のようになります（「rc.hpp」中のencode()）。
uint newL = L + r*low; if (newL < L){ //繰り上がりが発生。buffer+1 0x00 0x00 ... 0x00を出力するようにし //最後の0x00をbufferに入れる buffer++; for (;carryN > 0; carryN--){ fputc(buffer,outfp); buffer = 0; } } L = newL; while (R < TOP){ const byte newBuffer = (L >> 24); if (start){ buffer = newBuffer; start = false; } else if (newBuffer == 0xFF){ carryN++; } else { //繰り上がりが発生せずに出力。buffer 0xFF 0xFF ... 0xFFを出力 fputc(buffer,outfp); for (; carryN != 0; carryN--){ fputc(0xFF,outfp); } buffer = newBuffer; } L <<= 8; R <<= 8; }
すべての文字をencodeで処理し終わったら最後に残っているbufferおよび、Lを出力する必要があります。そのためflush()で、bufferの内容と、およびLをすべて出力します。
void finish(){ fputc(buffer,outfp); for (; carryN != 0; carryN--){ fputc(0xFF,outfp); } for(int i = 0; i < 4; i++){ fputc(L >> 24,outfp); L <<= 8; } }
復元は符号と同じで、符号化時に出力が発生したときと同じタイミングでデータを読み込みます。Lを扱う代わりにD := V-L で定義されるDを扱います。これは文字を復元する際に、L + R*cum(s) <= V < L + R*cum(s+1)を満たすsを探索する部分でV-Lを扱うことで、R*cum(s) <= V-L < R*cum(s+1)を満たすsを探索する問題として処理を簡単にするためです。
Range Coderの使い方
RCは、付属のソースコード「rc.hpp」をincludeすることで利用できます。
RCは符号表を構築するために、最初に各文字がデータ中で何回出現したかを記録した表と出力先のファイルのポインタを渡す必要があります。文字xを符号化する場合はrcEncoder::encode(Cum(x),Cum(x+1),total)を呼び出して符号化します。ただし、Cumは累積出現回数です。また、totalは(1U << 24)以下であることが必要です。これは、Rの更新の際、最初にtotalで割るところでRが0になってしまわないようにです。もしtotalが大きい場合は、全体の出現回数を同じ数で割り正規化する必要があります（この時、c(x)>=1であった文字xの出現回数が割った後もc(x)>=1となるように調整する注意が必要です）。
逆に復元する場合はuint decode(const uint total, const uint* cumFreq, const uint alphaSize)を使って復元します。alphaSizeは文字の種類数であり、cumFreqはCum(0)...Cum(alphaSize)を保存したものです。この関数は符号化した文字を返します。実際に使用した例を「rcUnitTest.cpp」に載せましたので参照してください。
これをコンパイルしたものが「rc.exe」です。このプログラムは、
rc e inputfile
で、inputfile中の各文字の出現回数を求め、RCで符号化します。そして、「inputfile.rc」という名前で保存します。
rc d inputfile.rc
で、「inputfile.rc」から元のinputfileを復元します。ただし、元のファイルと比較ができるよう違う名前、「inputfile.rc.test」で復元した結果を保存します。
その他
ACは出現確率に大きな偏りがある場合にHuffman符号（HC）よりはるかに小さなサイズでデータを保存することができます。符号化する文字が2種類の場合は文字列の偏りが非常に大きくなる場合が多いのでACが使われる場合が多いようです。例えば、ファックスデータの白黒画像の符号化などがそうです。
ただし、出現確率に大きな偏りが無い場合はHCもACに近い性能を発揮します。具体的には、一番出現確率が大きい文字の確率をpとした場合、一文字当たりの平均符号長の最適長（ACが達成可能）との差は、pが0.5以上の場合p、pが0.5以下の場合はp + 0.086であることが解析的に示されています。これはpがそれほど大きくない場合はHCでも高い圧縮率が達成できることを意味しています。
圧縮率だけではなく確率モデルを動的に変更しやすい点もACの大きな特徴です。HCは出現確率が大きく変わった場合にHuffman木もしくは符号表を更新するのに大量の処理（と大変な実装）が必要ですが、ACは確率表の更新のみで済みます。ただ、ACは累積確率表の更新が必要で、これはアルファベット種類数に比例した計算量になります（高速な更新方法なども存在します）。現実的には一定ブロック（1kB以上など）ごとに確率表の更新を行う場合、確率表更新のコストは無視できます。
RCをさらに高速にする方法には、
totalが2のべき乗となるように確率表をスケーリングし、除算をシフト演算に置き換える- Approximate ACを用いる（参考資料1、2）
- 確率に大きな偏りがある場合、復元時の二分探索を出現確率の大きい順に並び替えた線形探索する
などが考えられます
まとめ
今回紹介したRCは最小冗長符号を実現する算術圧縮を高速に処理できるよう出力をバイト単位に変更したもので、文字の出現確率に大きな偏りがある場合、Huffman法などと比べ短い符号長で保存できます。今回はまた、算術圧縮の原理、およびそれを有限精度の整数の演算で実現する方法について述べました。
参考資料
- 『Compression and Coding Algorithms』 A. Moffat、A. Turpin 著、Kluwer Academic Publishers、2002年
- 『Piecewise integer mapping for arithmetic coding』 L. Stuiver、A. Moffat 著、1998年
