算術符号化

トップページ研究分野と周辺パターン情報処理

算術符号化もデータの可逆圧縮技術で、一連の情報を0~1の間の何らかの数字に変換する(ここでは、x~yはx以上y未満を示す事とする。数学的には半開区間を示す記号[x,y)に相当する)事で、データを短くする。

符号化(エンコード)の過程

ハフマン符号化の所で用いた「AAABBCCDBBAAAABCBA」の例で考える。ここに登場する文字はA、B、C、Dの4種類だった。
仮にA=0、B=0.25、C=0.5、D=0.75の数字を割り当てる。0~1を4当分し、その境目に一つのアルファベットを割り当てた形とする。
次にA~Bの区間(0~0.25)を4等分してみる。AA=0、AB=0.0625、AC=0.125、AD=0.1875と割り当てる。
これを同様に、B~Cの区間(0.25~0.5)でも行い、BA、BB、BC、BDの位置を4等分の所に置く。C~Dの区間、D~1の区間でも同様にする。
今度はさらに、AA~ABの区間を4等分し、AAA、AAB、AAC、AADの位置を決める。以下同様に繰り返す。
これにより、登場する文字がA、B、C、Dしかない並び(情報)は、例えば「AAABBCCDBBAAAABCBA」でも、全て0~1の間の何らかの数字が割り当てられる事になる。

ここでは、三段目は0~0.25の範囲を拡大して示し、その右側も同様に対応する細分化を行っているものとする(赤い矢印)。
さらに、四段目以降も同様に細かく再分化してく事を示している(青い矢印)。
ここで、例えば0.125という数字には、B、BA、BAA、等の複数の文字列が割り当てられる事になり、このままでは一意には決まらない。
後述する復号化(デコード)のアルゴリズムだけでは、Aがいくつも繋がって処理が終わらないという問題が起きる。
この欠点を補うため、算術符号化では、予め圧縮するデータ長等を調べておいて、対応する長さで止める、等の処理をしている。

上記の例では、登場する文字が4種類であれば、単純に4等分していた。実際の算術符号化では、ハフマン符号化と同様に、各情報の登場頻度を求めておき、その割合の長さで分割する。
これにより、小数点以下の桁数が等分割する場合よりも短くて済むようになる。
仮に、登場する文字がA、B、Cの3種類しかない、簡単な場合を考える。登場頻度は、全体を100%としたとき、A=50%、B=30%、C=20%だったとする。
この場合、以下のように対応する割合の所に数字を割り当て、細分化においても同様の比率に従って、配置していく。

上記の条件で、例えばbcabを符号化するとどうなるだろうか。最初はbなので、0.5以上である事は間違いない。
次はcであるが、この位置は最初のbの区間(0.5~0.8)の中で80%の位置にある。それを先ほどの0.5に足す必要がある訳だ。
この操作は、n番目の文字の場合は、n-1番目までの文字列後の範囲内で、その文字の位置を調べる事になる。
n-1番目までの文字列後の範囲の長さは、結局、それまでの文字の範囲の積となる。例えば、bcaと来たa以降の範囲は、0.3×0.2×0.5=0.03となる。
その範囲の中で、次のbの位置は50%なので、0.03×0.5=0.15を、それまでの和に足していく。
bcabの位置を決める式は、以下のようになる。0.755がbcabの符号化後の値となる。

復号化(デコード)の過程

逆に、0.755という数字から元のbcabを復号する過程は以下のようになる。
0.755は、0.5~0.8の範囲にあるので、最初の文字はbとわかる。そこで、0.5を引く。符号化の最後に得られた0.5+0.24+0.0+0.015を逆に辿る形となる。
0.755-0.5=0.255は、最初のbの範囲長0.3の中では、0.3×0.8~0.3×1.0の範囲にあるので次の数字はcだと分かる。
0.3×0.8=0.24を引く。0.255-0.24=0.015は、bcの範囲長0.06の中では、0.06×0.0~0.06×0.5の間にあるため、次はaと分かる。
0.06×0.0=0.0を引く。そのまま、0.015となるが、bcaの範囲長0.03の中では、0.03×0.5と一致するので、最後はbとなる。
0.03×0.5=0.015を引く。0.015-0.015=0となって、後は同様の処理を繰り返すと、ずっとaがくっつく事になる。
元データがbcabは分からなくても、文字4つという情報を残しておけば、bcabが出たところで処理を終了する事が出来る。以上が算術符号化における復号の原理である。