Hatena::ブログ(Diary)

小人さんの妄想 このページをアンテナに追加 RSSフィード Twitter

2008-06-07

算術圧縮のしくみ

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

f:id:rikunora:20080608005302p:image

この図の上半分には、一本の棒を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単位でのデータ出現頻度などについて、上と同じ考え方で圧縮を行う。


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

けち。


スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/rikunora/20080607/p1