レンジコーダ講座その3

Revised : 2006/09/17
Since : 2006/07/31


Home  圧縮 | 算術符号 | RC(その1 2) ∥ 適応型 | 頻度表更新 | 圧縮率向上 | 二値

適応型(動的)レンジコーダ

これまで説明してきたレンジコーダを静的レンジコーダという。
静的レンジコーダとは、最初に頻度表を作成し、符号化・復号化中は頻度表を更新しないものである。
これに対し、符号化・復号化中は頻度表を更新するものを、適応型レンジコーダとか動的レンジコーダと言う。

長所
頻度表を埋め込む必要がない。(ヘッダを小さくできる)
前半と後半で出現率の偏りが異なる場合、頻度表の更新により圧縮率が向上する。

短所
頻度表がある程度更新されるまでは圧縮率が悪い。
頻度表更新分の計算量が増える。

ページの上部へ

頻度表更新

頻度表の初期状態は、出現可能性のある文字について頻度を各々1とする。(EOFも1とする)
(この頻度表において、頻度が1以上でない文字は符号化も復号化もできない)

符号化時、一文字符号化した後に、符号化した文字の頻度を+1する。
復号化時、一文字復号化した後に、復号化した文字の頻度を+1する。
この時、頻度総数がレンジの確保している最低精度を超えないこと。(符号・復号不能になる)

頻度総数が最低精度に達した場合
(1)頻度表の更新を止める
(2)頻度表を初期状態に戻す
(3)各文字の頻度を減らす
等がある。

(3)の簡単な実装方法
各文字の頻度を半分にする。頻度が0になる場合は1とする。

ページの上部へ

圧縮率向上にむけて

頻度表は一文字を符号化する時とそれに対応する符号を復号化する時において同じものであれば良い。
つまり、符号化する時に一文字一文字その文字に最適な頻度表を使用すれば高圧縮になる。
頻度表の更新方法を変更したり、複数の頻度表を切り替えたり、組み合わせることにより実装可能である。

頻度表の更新では、一文字毎の増分を2以上にするや最低精度に達する前に更新する等がある。
説明では、一文字符号化復号化する度にその文字の頻度を1増加させていた。
これを増分8とした場合、1の場合に比べてその文字の割合が大きくなり、次に同じ文字が出た場合、圧縮率が良くなる。
また、説明では最低頻度に達していた場合に、頻度表を更新していた。
これを、例えば最低精度を32,768とし、頻度表の更新を総数が1,024に達した場合とすると、
頻度表の更新回数が増え、前半と後半で出現確率が異なる場合などに圧縮率が良くなる。

頻度表を切り替えたり、組み合わせたりする方法では、
直前に出現した文字によって使用する頻度表を選択したり、複数の頻度表組み合わせて新たな頻度表を作成したりする等がある。
例えば、テキスト等で同じ単語や同じパターンが何度も繰り返される場合、
直前に出現した文字によって次に出現する文字に偏りができるため、圧縮率が良くなる。
実装にはPPMやCTW等を組み込むと良い。

ファイルによって最適な設定は異なるため、試行錯誤してみるのも面白いだろう。

ページの上部へ

二値レンジコーダ

二値レンジコーダは2種類の文字{0,1}のみで符号化する方法である。
そのため、0と1以外の数値(多値)を表すことができなが、
多値を各々が1対1に対応する0と1からなる文字列に変換することによって対応できる。

しかし、圧縮率は多値レンジコーダよりも悪くなるように思われる。
というのも、レンジコーダは整数で演算するため、計算の精度が問題になるからである。
二値レンジコーダは多値レンジコーダよりも計算回数が多くなるので、精度は劣化してしまう。

これは、二値レンジコーダ単体で符号化する場合である。
ブロックソートやMTFと組み合わせると、小さな数値が多くなり大きな数値は少なくなるので、
α符号等の可変長符号を利用することにより、圧縮率は向上する。

また、多値では別々の文字として扱っていたものも、上位ビットと下位ビット等に分割することにより、
同じグループとして扱い、頻度表の偏りを大きくすることができる。
例えばASCIIコードでは、英数字には連続する文字コードが割り当てられているため、
下位4bitは異なるが上位ビットは同じになることも多い。

実装方法は簡単で、これまで説明してきた多値レンジコーダを用い、
出現頻度表の文字を0と1のみに変更するだけである。

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