レンジコーダ講座その1

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


Home  圧縮 | 算術符号 | RangeCoder(その2 3) ∥ RangeCoder | 桁上有 | 符号化 | 復号化

レンジコーダ(Range Coder)

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

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

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

ページの上部へ

レンジコーダ(桁上がりあり)

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

ページの上部へ

符号化

例としてabcabaを考える。
まず頻度表を作る。

出現頻度表
文字 頻度
EOF
総数

これをレンジで表す。
R:幅
L:下限値

EOF:end of file

対応表
文字 Low Range 備考
EOF [6 , 7)
[5 , 6)
[3 , 5)
[0 , 3)

総数は7であり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を出力する。

abcabaの符号化について下表に示す。

R拡大 入力 L算出 low 出力 R算出 range
R/総数 L+R*入力のL 7 6 5 4 3 2 1 上位2bit R*入力のR 7 6 5 4 3 2 1
初期値
初期値 0 0 0 0 0 0 0 0
初期値 31 0 0 1 1 1 1 1
31/7=4 a 0+4*0=0 0 0 0 0 0 0 0
4*3=12 0 0 0 1 1 0 0
12/7=1 b 0+1*3=3 0 0 0 0 0 1 1
1*2=2 0 0 0 0 0 1 0
Rを拡大

0 0 0 1 1 0 0 00
0 0 0 1 0 0 0
8/7=1 c 12+1*5=17 0 0 1 0 0 0 1
1*1=1 0 0 0 0 0 0 1
Rを拡大

1 0 0 0 1 0 0 00
0 0 0 0 1 0 0
Rを拡大

0 0 1 0 0 0 0 10
0 0 1 0 0 0 0
16/7=2 a 16+2*0=16 0 0 1 0 0 0 0
2*3=6 0 0 0 0 1 1 0
Rを拡大

1 0 0 0 0 0 0 00
0 0 1 1 0 0 0
24/7=3 b 64+3*3=73 1 0 0 1 0 0 1
3*2=6 0 0 0 0 1 1 0
Rを拡大

0 1 0 0 1 0 0 10
0 0 1 1 0 0 0
24/7=3 a 36+3*0=36 0 1 0 0 1 0 0
3*3=9 0 0 0 1 0 0 1
9/7=1 EOF 36+1*6=42 0 1 0 1 0 1 0
1*1=1 0 0 0 0 0 0 1

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

ページの上部へ

復号化

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

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

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

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

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

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

R拡大 区間算出 出力 入力 L算出 low R算出 range
R/総数 L/R 文字 2bit L-R*入力のL 7 6 5 4 3 2 1 R*入力のR 7 6 5 4 3 2 1
初期値


初期値 7bit 0 0 0 0 1 0 0 初期値 31 0 0 1 1 1 1 1
31/7=4 4/4=1 a
4-4*0=4 0 0 0 0 1 0 0 4*3=12 0 0 0 1 1 0 0
12/7=1 4/1=4 b
4-1*3=1 0 0 0 0 0 0 1 1*2=2 0 0 0 0 0 1 0
Rを拡大

01
0 0 0 0 1 0 1
0 0 0 1 0 0 0
8/7=1 5/1=5 c
5-1*5=0 0 0 0 0 0 0 0 1*1=1 0 0 0 0 0 0 1
Rを拡大

00
0 0 0 0 0 0 0
0 0 0 0 1 0 0
Rを拡大

10
0 0 0 0 0 1 0
0 0 1 0 0 0 0
16/7=2 2/2=1 a
2-2*0=2 0 0 0 0 0 1 0 2*3=6 0 0 0 0 1 1 0
Rを拡大

10
0 0 0 1 0 1 0
0 0 1 1 0 0 0
24/7=3 10/3=3 b
10-3*3=1 0 0 0 0 0 0 1 3*2=6 0 0 0 0 1 1 0
Rを拡大

10
0 0 0 0 1 1 0
0 0 1 1 0 0 0
24/7=3 6/3=2 a
6-3*0=6 0 0 0 0 1 1 0 3*3=9 0 0 0 1 0 0 1
9/7=1 6/1=6 EOF
















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

ページの上部へ
容量300MB、月額125円、高性能なサーバが日本最大級のバックボーンに直結。
さくらのレンタルサーバ
ロリポップのドメインが65種類 → 85種類に!!
きっとお好みのドメインが見つかるはず!
アフィリエイトならリンクシェア