レンジコーダ講座その2

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


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

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

説明を簡単にするために、全体を符号なし7bit(負は無)
レンジの精度を7bitとし最低確保する精度は3bitととする。(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 , 128)とする。
この時128は含まないためレンジは127とする。下限値は0である。

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

以上を繰り返す。
low + rangeが5bit以下になった場合、レンジ拡大する。
通常7-5=2bitを作業領域とする。
拡大も下限値、幅とも2bit左シフト(4倍)する。lowの上位2bitは出力する。

low + rangeが5bit以下にならなくても、rangeが3bit以下になった場合はレンジ拡大する。
この時、rengeはlow下位5bitの2の補数とし、3bitより大きくなるまで拡大する。(桁上がりしないようにレンジ縮小)

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
初期値 127 1 1 1 1 1 1 1
127/7=18 a 0+18*0=0 0 0 0 0 0 0 0
18*3=54 0 1 1 0 1 1 0
54/7=7 b 0+7*3=21 0 0 1 0 1 0 1
7*2=14 0 0 0 1 1 1 0
14/7=2 c 21+2*5=31 0 0 1 1 1 1 1
2*1=2 0 0 0 0 0 1 0
Rを縮小

0 0 1 1 1 1 1
2の補数 0 0 0 0 0 0 1
Rを拡大

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

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

1 0 0 0 0 0 0 11
0 0 1 1 0 0 0
Rを拡大

0 0 0 0 0 0 0 10
1 1 0 0 0 0 0
96/7=13 b 0+13*3=39 0 1 0 0 1 1 1
13*2=26 0 0 1 1 0 1 0
26/7=3 a 39+3*0=39 0 1 0 0 1 1 1
3*3=9 0 0 0 1 0 0 1
Rを拡大

0 0 1 1 1 0 0 01
0 1 0 0 1 0 0
36/7=5 EOF 28+5*6=58 0 1 1 1 0 1 0
5*1=1 0 0 0 0 1 0 1

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

ページの上部へ

復号化

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

区間は[low , low + range)と表せる。

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

まず、現在のレンジを頻度総数で割り、一個あたりの幅を算出する。
(code - low)を一個あたりの幅で割り、どの文字の区間に入るか判定する。(桁上がり判定のためlowも記憶する)
入力文字の下限値に一個あたりの幅を掛け、増加した分の下限値を算出する。
入力文字の頻度に一個あたりの幅を掛け、新たなレンジを算出する。

符号化と同判定でレンジ拡大する。
符号化時と同様に2bit左シフトするが、この時codeの下位2bitに符号語の次の2bitを読み込む。

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

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

初期値 0 0 0 0 0 0 0 0 初期値 127 1 1 1 1 1 1 1 7bit 0 0 1 1 1 1 1
127/7=18 (31-0)/18=1 a 0+18*0=0 0 0 0 0 0 0 0 18*3=54 0 1 1 0 1 1 0







54/7=7 (31-0)/7=4 b 0+7*3=21 0 0 1 0 1 0 1 7*2=14 0 0 0 1 1 1 0







14/7=2 (31-21)/2=5 c 21+2*5=31 0 0 1 1 1 1 1 2*1=2 0 0 0 0 0 1 0







Rを縮小


0 0 1 1 1 1 1 2の補数 0 0 0 0 0 0 1







Rを拡大


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


1 1 1 0 0 0 0
0 0 1 0 0 0 0 10 1 1 1 0 0 1 0
16/7=2 (114-112)/2=1 a 112+2*0=112 1 1 1 0 0 0 0 2*3=6 0 0 0 0 1 1 0







Rを拡大


1 0 0 0 0 0 0
0 0 1 1 0 0 0 11 1 0 0 1 0 1 1
Rを拡大


0 0 0 0 0 0 0
1 1 0 0 0 0 0 10 0 1 0 1 1 1 0
96/7=13 (46-0)/13=3 b 0+13*3=39 0 1 0 0 1 1 1 13*2=26 0 0 1 1 0 1 0







26/7=3 (46-39)/3=2 a 39+3*0=39 0 1 0 0 1 1 1 3*3=9 0 0 0 1 0 0 1







Rを拡大


0 0 1 1 1 0 0
0 1 0 0 1 0 0 10 0 1 1 1 0 1 0
36/7=5 (58-28)/5=6 EOF























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

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