算術圧縮のしくみ

算術圧縮とは、文字の出現率の偏りを利用したデータ圧縮方法の1つである。

この図の上半分には、一本の棒を3:1という不均等な割合で分割していった様子が描かれている。
下半分には1:1で、均等に分割していった様子が描かれている。
棒上のある1点を示すには、上半分のように不均等に分割してゆくよりも、下半分のように均等に分割していった方が効率が良い。
もし上半分のような形で表されているデータがあったなら、それを下半分のような形に書き直せば、より少ない文字で効率よく記述できそうだ。

例えば、
 0010
というデータがあったとする。
このデータに出現する 0 は3個、1 は1個。
両者の比は 3:1 となる。(なので、上の3:1の図が使える)

図に示した赤い矢印を上から順にたどって、0→0→1→0 という区間にたどり着く。
この区間を、下半分の均等な分割の方で指定することを考えてみる。
この区間に含まれている、最も短い2進数を探すと、棒の中央を表す"0"が1個だけで事足りる。
つまり、元データ"0010"は、1個の"0"に圧縮できてしまうのだ。
ただし、データを復元するには1個の"0"だけでは不十分で、
 ・0と1の比率(ここでは3:1)
 ・元データのサイズ(ここでは4)
も必要となる。

では、1個の"0"だけから、どのようにして元の"0010"を復元するのだろうか。
まず1個の"0"から、棒の中央という位置を割り出す。
そして図の上半分の、ちょうど中央にある区画の数を、上から順に読み上げるだけである。
それは確かに 0→0→1→0 となっているだろう。(図中のオレンジ色の点線)

実際には0,1という2種類の文字だけでなく、アルファベット26文字とか、Byte単位でのデータ出現頻度などについて、上と同じ考え方で圧縮を行う。

このように算術圧縮は非常に美しいアルゴリズムなのだが、残念なことに特許が取られており、自由に使えないようである。
けち。