レンジコーダ講座その1

Revised : 2006/07/31
Since : 2006/07/31

レンジコーダ（Range Coder）

算術符号は区間 [0, 1) を分割したが、レンジコーダは最初に大きな幅（range）たとえば区間 [0, 10000) を設定し、分割していくことで符号化する。
レンジコーダは整数で演算するので、データが多くなるとレンジが小さくなり、分割不可能となる。その時はレンジを拡大する。

レンジ拡大のタイミングを定めることにより、区間全体の大きさを覚えておく必要はない。また、区間の下限値と幅だけで符号化が可能である。
復号化も、符号化と同タイミングでレンジ拡大することにより可能である。
レンジコーダでは区間の下限値を符号語とする。

レンジコーダには大きく分けて、「桁上がりあり」と「桁上がりなし」がある。

ページの上部へ

レンジコーダ（桁上がりあり）

説明を簡単にするために、全体を符号なし７bit（負は無）、レンジの精度を５bitとし最低確保する精度は ３bitととする。
上位２bitは桁上がりに対応するためのバッファに使用する。（JAVAのbyte型を想定）
（通常はＣＰＵが高速にあつかえる最大サイズがよい）
最低確保する精度とは、両隣と区別可能であること。つまり、頻度総数の最大値を保証するものである。

ページの上部へ

符号化

例としてａｂｃaｂaを考える。
まず頻度表を作る。

総数は７であり3bitで表せるから、ここから符号化を開始する。
区間は[low , low + range)と表せる。

初期の区間は[0 , 32)とする。
この時32は含まないためレンジは31とする。下限値は0である。

まず、現在のレンジを頻度総数で割り、一個あたりの幅を算出する。
入力文字の下限値に一個あたりの幅を掛け、増加分の下限値を算出し、現在の下限値に加算する。（新たな下限値）
入力文字の頻度に一個あたりの幅を掛け、新たなレンジを算出する。

以上を繰り返す。
幅が最低の精度を確保できなくなった場合、レンジ拡大する。（頻度総数が7で幅が4の場合、一個当たり1bit未満となり符号化できない）
今、精度5bit最低3bitで作業しているため、5-3=2bitが作業領域である。
拡大も下限値、幅とも2bit左シフト（4倍）する。lowの上位2bitは出力する。
ただし、lowの5,4bitがともに1の場合、出力せずに一時保存する。
またバッファ桁上がり回数を+1する。シフト後の上位2bitを0とする。
（シフトすると7,6bitがともに1となりバッファでも桁上がりの可能性があるため）

次の出力時もバッファが桁上がりする可能性がある場合は、バッファ桁上がり回数を+1し、シフト後の上位2bitを0とする。
バッファの桁上がりの可能性がない場合は、バッファが桁上がりしたかを判定する。
lowの上位2bitが01の場合、桁上がりしているので、一時保存+1を出力し、バッファ桁上がり回数分00を出力する。
lowの上位2bitが00の場合、桁上がりしていないので、一時保存をそのまま出力し、バッファ桁上がり回数分11を出力する。

ａｂｃaｂaの符号化について下表に示す。

よって出力符号は出力済み+最終下限値となる。
2進数表記すると00001000100101010となる。

ページの上部へ

復号化

次はこの00001000100101010を復号化する。
頻度表は符号化時と同じである。

区間は[low , low + range)と表せるが、lowをともに減算すれば
区間は[0 , range)とも表せる。

初期のレンジは符号時と同じ31とする。
下限値は符号語の上位7bitを読み込む。

まず、現在のレンジを頻度総数で割り、一個あたりの幅を算出する。
下限値を一個あたりの幅で割り、どの文字の区間に入るか判定する。
入力文字の下限値に一個あたりの幅を掛け、増加した分の下限値を算出し、現在の下限値から減算する。（出力文字の影響排除）
入力文字の頻度に一個あたりの幅を掛け、新たなレンジを算出する。

幅が精度を確保できなくなった場合、レンジ拡大する。
符号化時と同様に2bit左シフトするが、この時lowの下位2bitに符号語の次の2bitを読み込む。

以上を繰り返す。
上で符号化した00001000100101010について復号化を下表に示す。

よってabcabaが復号できた。
（当然であるが）符号化と復号化では幅とレンジ拡大のタイミングがおなじである。