Revised : 2011/10/01
Since : 2006/03/18
元の区間を出現頻度によって分割する。データ列上の値によって区間を選択する。
選択した区間を出現頻度によって再分割する。これを繰り返し、最終的に選択された区間がデータを表す情報となる。
例としてａｂａｃを考えると、
出現頻度はａ：２ ｂ：１ ｃ：１ であり、出現確率は、ａ：1/2 ｂ：1/4 ｃ：1/4 である。
ここで区間 [0 , 1) を考える。（区間[ ]：両端を含む、区間( )：両端を含まない、区間[ )：下端を含み上端を含まない）
区間 [0 , 1) を出現確率によって区間ａ，ｂ，ｃに分割する。
最初のデータはａなので区間ａ [0 , 1/2) を選択する。
区間ａを再分割する。次のデータはｂなので区間ａｂ [1/4 , 3/8) を選択する。
区間ａｂを再分割する。次のデータはａなので区間ａｂａ [1/4 , 5/16) を選択する。
区間ａｂａを再分割する。次のデータはｃなので区間ａｂａｃ [19/64 , 5/16) を選択する。
次のデータはないので区間 [19/64 , 5/16) がａｂａｃを表すデータとなる。
19/64 = 0.296875
5/16 = 0.3125
この区間内にある値で桁数が最小の0.3を選べば符号となる。
復号は0.3がどの区間にあるかを調べることによって可能である。ただし無限に復号できるので・・・
データの総数もしくは終端コードを利用する必要がある。
0 1/2 3/4 1
|-------------------------------------------------+------------------------+------------------------|
区間a 区間b 区間c
0 1/4 3/8 1/2
|-----------------------+------------+------------+
区間aa 区間ab 区間ac
1/4 5/16 11/32 3/8
+------+--+--+
aba abb abc
1/4 9/32 19/64 5/16
+--+-+-+
abaa abab abac
では、符号に無限精度の実数を扱っているが、コンピュータでは扱えない。
つまり、Ｅｌｉａｓ符号ではデータを符号化する度に区間が小さくなっていくので、データが多くなると計算できなくなる。
そこで算術符号では、随時区間を拡大することによって、無限精度の実数を扱えるようにした。
例としてabbbabbbcbを考えると、abbbabを符号化した後は区間[0.09 ,
0.09995)内になり、0.09は不変となる。
そこで09を出力し、100倍して区間[0 , 0.995)と拡大する。以後随時区間を拡大することによって計算を可能とする。
1- +---->0.2- +-->0.18- +-->0.166- +-->0.1562- +-->0.10132- +->0.099948 c | | | | | | | | | | | | 0.9+ | 0.18+---- 0.166+--- 0.1562+---- 0.14934+ | 0.099948+--- | | | | | | | | | | | | | | | | b | | | | | | | | | | | | | | | | | | | | | | | | 0.2+-- 0.04+---- 0.068+--- 0.0876+---- 0.10132+---- 0.090344+--- | | | | | | | | | | a | | | | | | | | | | 0---------> 0- +-->0.04- +-->0.068- +-->0.0876--------> 0.0876- +->0.090344ページの上部へ
記号 a ab abb abbb abbba abbbab 続き +--->0.099948 0.9948- +-->0.89876- +-->... c | | | | | --- 0.0989876 0.89876+--- 0.831532+---- | | | | b | | | | | | -- 0.0922648 0.22648+--- 0.360936+---- | | | | | a | | | | | +--->0.090344 0.0344- +-->0.22648- +-->... 以後0.09は不変だから09を出力して100倍 記号 abbbab abbbabb abbbabbb
