算術符号講座

Revised : 2011/10/01
Since : 2006/03/18


Home  圧縮 | RangeCoder(その1  3) ∥ Elias符号 | 算術符号

Elias(エライアス)符号

元の区間を出現頻度によって分割する。データ列上の値によって区間を選択する。
選択した区間を出現頻度によって再分割する。これを繰り返し、最終的に選択された区間がデータを表す情報となる。

例としてabacを考えると、
出現頻度はa:2 b:1 c:1 であり、出現確率は、a:1/2 b:1/4 c:1/4 である。
ここで区間 [0 , 1) を考える。(区間[ ]:両端を含む、区間( ):両端を含まない、区間[ ):下端を含み上端を含まない)
区間 [0 , 1) を出現確率によって区間a,b,cに分割する。
最初のデータはaなので区間a [0 , 1/2) を選択する。
区間aを再分割する。次のデータはbなので区間ab [1/4 , 3/8) を選択する。
区間abを再分割する。次のデータはaなので区間aba [1/4 , 5/16) を選択する。
区間abaを再分割する。次のデータはcなので区間abac [19/64 , 5/16) を選択する。
次のデータはないので区間 [19/64 , 5/16) がabacを表すデータとなる。
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

ページの上部へ

算術符号

では、符号に無限精度の実数を扱っているが、コンピュータでは扱えない。
つまり、Elias符号ではデータを符号化する度に区間が小さくなっていくので、データが多くなると計算できなくなる。
そこで算術符号では、随時区間を拡大することによって、無限精度の実数を扱えるようにした。

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