算術符号化法1

自分用に算術符号化法についてまとめます。
自分用に書いているので、恐らく大雑把であったり間違えたりしているかも知れませんがご了承ください。

算術符号化法

算術符号化法とは、いくつかの出現確立が決まった文字列をある一定の0以上1以下のに直して、圧縮する方法です。
それでは、算術符号化法を具体例を挙げて学んでいきましょう。
・記憶のない情報源と各記号の出現確率を定めます。
A=50% B=30% C=20%とする。
A=0.5 B=0.3 C=0.2とする。
・連続したそれらの文字列は以下のような原理で数値で表せる。

例えば、
文字列が1桁の場合、0以上0.5未満の数値をAとする。0.5以上0.8未満の数値をBとする。0.8以上1未満の数値をCとする。
文字列が2桁の場合、0以上0.25未満の数値すべてをAAとする。また、0.25以上0.4未満の数値をABとする。0.4以上0.5未満の数値をACとする。
文字列が3桁の場合・・・
という風に文字列をいくつかの数値で表していく。
そして、その文字列になる確率が高ければ高いほど、その範囲を取る数値は大きい。

算術符号化法の具体例

例えば、累積確率をA=0.0、B=0.5、C=0.8とする。長さをA=0.5、B=0.3、C=0.2とする。そのような状態で、BCABのような出現を符号化すると、以下のような計算でその数値を出せます。
0.5+0.3*0.8+0.3*0.2*0.0+0.3*0.2*0.5*0.8=0.764
Bの初期位置+Bの長さ*Cの位置+BCの長さ*Aの位置+BCAの長さ*Bの位置
となります。

圧縮率の計算

本当に圧縮出来ているかを確かめるために、bitの長さを数えてみる。
元々は3通りのものが4文字連なっているので、3の4乗で81通りです。
6bit(64通り)<=81通り<=7bit(128通り)で表せますね。
つまり6bitから7bitの間で表せます。

一方、圧縮後のbit数は

うーん。あれ?循環小数になってしまう。
なので、何桁まで見れば最後の一桁の違いが分かるのかを確認していきましょう。
・BCAA
0.5+0.3*0.8+0.3*0.2*0.0+0.3*0.2*0.5*0.0=0.74
0000 0000 . 1011 1101 0111 0000 1010 0011
・BCAB
0.5+0.3*0.8+0.3*0.2*0.0+0.3*0.2*0.5*0.5=0.755
0000 0000 . 1100 0001 0100 0111 1010 1110
・BCAC
0.5+0.3*0.8+0.3*0.2*0.0+0.3*0.2*0.5*0.8=0.764
0000 0000 . 1100 0011 1001 0101 1000 0001

これらの違いは、小数点以下7桁見ればわかりますね。
7桁見ればよい。つまり7bit。。。128通り。。。

元が6bit以上7bit以下なのでちょっと多い気がする。。。
ほとんど圧縮出来てないやん。。。
と思いました?
でも実際に圧縮するものは、これ以外にもたくさんパターンがあります。
例えば、4桁の数値で言えば一番出現確立の高い数値はAAAAですね。

・AAAA
0.0+0.5*0.0+0.5*0.5*0+0.5*0.5*0.5*0=0
0000 0000 . 0000 0000 0000 0000 0000 0000
・AAAB
0.0+0.5*0.0+0.5*0.5*0+0.5*0.5*0.5*0.5=0.0625
0000 0000 . 0001 0000 0000 0000 0000 0000
なのでこれらの違いは、4桁見ればわかりますね。
出やすい確率の文字列はたくさん圧縮出来て、出にくい確率の文字列はあまり圧縮できないようになっております。
なので、総合的にみるとこれらは圧縮できることになります。(これらは後に証明します)

小数点の数値を2進数で表す

2進数の特性の話になりますが、0以上1未満の数値すべてをキリのいい数値に直せる訳ではありません。
0以上1未満の数値を2進数に直すと無限級数に陥ることがよくあります。
無限級数に陥るといくつかの有限桁数で打切りしなければならなくなり、その時に打切り誤差が発生します。
そうするとその2進数をもう1度10進数に戻した時に正確な数値ではなくなってしまいます。
なので、2進数の具体的な文字列を表す数値(AAAAは0以上0.0625未満など)の範囲を決めるためには、10進数で考えるのではなく、その前後の累計確率も2進数で考えて、その2進数特有の範囲の累計確率を出す必要があります。別の言い方をすると、10進数の累計確率の範囲と2進数の累計確率の範囲は打切り誤差がある為に、若干範囲が違ってくると言うことです。
つまり、10進数の理論の簡単さに反して、2進数で考えた時の実装の難しさが際立ちます。

実際に符号化し、2進数に直した後に10進数に直して、復号化してみます。
今回はBCAA、BCAB、BCACを例に符号化→2進数→10進数→復号化の手順を辿ってみましょう。

BCAAは0.7343750になり、0.740以上0.755未満ではないので、BCAAに復号できませんでした。
BCABは0.7578125になり、0.755以上0.764未満なので、BCABに復号できましたね。
BCACは0.7734375になり、0.764以上0.770未満ではないので、BCACに復号できませんでした。

このように、2進数を通した符号化は10進数に直す範囲が少しずれるので、気を付けなければなりません。

【10進数のみを考えて復号】
それでは10進数で復号してみましょう。
4文字と言う情報だけで、以下の数値を複合してみます。
0.0<0.5<0.8<1.0の範囲で最初の文字はBとわかります。
0.5を引いて、
 0.240
 0.255
 0.264
となります。
0.00<0.15<0.24<0.3の範囲ではCの位置に来るので、次の文字はCとわかります。
0.24を引いて、
 0.00
 0.015
 0.024
となります。
0.00<0.03<0.048<0.06の範囲ではAの位置に来るので、次の文字はAとわかります。
最後に、0.00を引いて、
 0.00
 0.015
 0.024
とります。
0<0.015<0.024<0.03の範囲では0.00、0.015、0.024はそれぞれA、B、Cとわかります。
つまりこれらは復号すると、
 BCAA
 BCAB
 BCAC
と直せる。
ちゃんと複合できましたね。
10進数の復号化は符号化の時の逆の手順を辿ればいいので簡単ですね!

2進数に直した時の理論値との打切り誤差の話などは後でやろうかなと思います!
以上で算術符号化法の話を終わろうと思います。

言語録

・冗長性、冗長度
あるデータを転送する際に無駄に使われている部分の量に相当する。
また、逆にノイズのある通信路容量が有限な通信路で誤り検出訂正を行う目的で冗長性を付与するのが、チェックサムやハミング符号などである。