はじめに
本記事では、全体のサイズが最小となる算術圧縮を高速に実現するRange Coder（以下RC）を紹介します。
算術圧縮は、各文字の出現確率が分かっている場合にそのデータを最小長で表現可能な符号法です。各文字に固定の符号を割り当てるHuffman法とは違い、符号化を状態更新とみなし、すべての文字を符号し終わった後の状態を保存することで符号化を実現します。これにより1文字単位の符号長を1bitより細かく調整することが可能となります。
算術符号は圧縮率が高い反面、ビット単位の演算処理が大量に発生するため、符号化、復号化ともにHuffman符号に比べ遅いという問題点があります。今回紹介するRCは、算術符号の処理をバイト単位で行うことで高速な処理を可能にします。
また、算術圧縮については概要から説明します。
対象読者
C++の利用者を対象としています。データ圧縮の基礎を知っていることが望ましいです。
必要な環境
C++、32bit環境を想定しています（Windows XP上のVisual Studio C++ 2005、gcc 3.2.2で動作確認済みです）。
データ圧縮とRC
データ圧縮は、必要な情報を残したままデータをコンパクトに保存・伝送する技術であり、テキストや画像・動画情報の圧縮など、多くの場面で使われる不可欠なものとなっています。
データ圧縮の中身は大きく分けてモデル化と符号化の2種類に分けられます。前者はデータをどのように表現するかを求める部分であり、後者はその表現したものをコンピュータ上でどう保存するかという部分です。今回扱うRCは、この後者のための代表的な技術であり、モデルが分かっているデータを最も短い符号長で保存する技術です。
以前紹介したCanonical Huffman Code（CHC）は、各文字に固定符号を割り当てる場合に最も全体が短くなる符号であることが知られていますが、最適な符号長が整数で無い場合には符号に無駄が生じます。例えばこれから符号化したい文字がa、bの2種類で、出現する確率がそれぞれ0.99と0.01であると分かっている場合、最適な符号長はそれぞれ-lg(0.99) = 0.01 bit、-lg(0.01) = 6.64 bitと求められ（lgは底が2の自然対数）、1文字あたりの平均符号長は0.99*0.01+0.01*6.64 = 0.08 bitとなります。しかし、CHCでは1bit未満の符号長を扱えないため1bit/文字以上の圧縮率は達成できません。
RCの基である算術符号は、各文字を最小の符号長で符号化できる符号法です。算術符号は1bitより短い符号を扱うために各文字を符号化した時の状態を保持し、次の文字を処理する時にその状態を影響させることで、1bit単位より細かい符号を実現します。
算術圧縮の概要
はじめに算術圧縮（Arithmetic Code、AC）について説明します。
データ中に出現する各文字の出現確率が既に分かっている、もしくは予測できる場合に、多く出現する文字に対し短い符号を割り当て、あまり出現しない文字に対し長い符号を割り当てることで、データ全体の符号長を短くすることができます。前回、CHC法を紹介しました。これは各文字に対し固定の符号を割り当てた場合に、全体の長さを最も短くできる方法であることが知られています。
これに対し、ACは各文字に符号を割り当てるのではなく、各文字の符号化を状態の更新として表現し、すべての文字を符号化し終わった後の最終状態を出力することで、全体の文字列を符号化します。また復号時には、この最終状態を読み取り、どの文字が順に符号化されていたかを調べることで文字を復元します。ACはHuffman法とは違い、符号化した後のサイズを最小（そのモデルから求められるエントロピー）にすることが可能なことが知られています*1。
ACが扱う状態とは0以上1未満の区間です。この区間を2つの変数L（Lower end：下限）とR（Range：幅）で[L,L+R)と表現することにします。LとRは無限精度の実数だとし、初期状態を L=0, R=1とします。これから符号化する文字の種類を1...kとし、各文字1<=x<=kの出現確率p(x)が与えられているとします（Σ_i=1...k p(x) = 1）。また、累積出現確率cum(x)を導入します。これはcum(x) := Σ_j=1...x-1 p(j) と定義され、自分より小さい文字の確率の和を意味します。このcum(x)によって、[0,1)の区間が各文字の確率に比例するように[cum(0),cum(1))、[cum(1),cum(2))、...、[cum(σ),cum(σ+1))と分割されていると考えられます。
今から符号化する文字列T[0...n]を次のようにして順に処理していき状態を更新します。
for i = 0...n
L := L + R * cum(T[i])
R := R * p(T[i])
end
この状態更新は、現在の状態を0から1までの区間とみなしたうえで現在の文字に対応する区間に従って、区間を再帰的に狭めていくことに相当します。各文字を符号化するたびにLは増加し、Rは減少していきます。図1にp(a)=0.5, p(b)=0.3, p(c)=0.2である文字列をacbまで符号化している様子を示します。
最終状態を出力する場合は、L <= V < L+R を満たす小数V中で最も少ないbit数で表現できるVを出力します。
Vに必要な精度はRの大きさによります。Rが0.1と0.00001の場合、Vに必要な精度はそれぞれ小数点第1位と第5位となり、Rが小さければVを保存するのに必要なサイズも大きくなります。出現確率が大きい文字を符号化した場合は、Rは状態更新時にあまり小さくならないので最後にVを保存する時の精度は小さくて済み、また逆に出現確率が小さい文字を符号化した場合は最後にVを保存する時の精度を大きくしなければなりません。
詳しく説明すると、L <= V < L+R を満たすVを保存するのに最も少ないbit数は、Rの精度-lg(R)となります。最終状態でのRはその更新式より、出現した各文字の出現確率を順にかけた結果なので、R = p(T[0]) * p(T[1]) * ... * p(T[n]) です。これより、-lg(R) = -lg(p(T[0]) * p(T[1]) * ... * p(T[n])) = (-lg(p(T[0]))) + (-lg(p(T[1]))) + ... + (-lg(p(T[n]))) となります。これは各文字xを-lg(p(x)) bitで表現できていることになるため、最適な符号長で表現できていることになります。
復元時はVを読み取り、符号化された文字が何であったかを調べていきます。はじめに符号のときと同じように状態をL=0, R=1として初期化します。各ステップでどの文字が符号化されたかを最終状態（V）から求め、符号化と同じように状態を更新していきます。
for i = 0...n
L + R*cum(s) <= V < L + R*cum(s+1) を満たすsを求める。このsがT[i]。
L = L + R * cum(s)
R = R * p(s)
end
最終状態Vだけから、どの文字が符号化されたかが分かる理由は、（長さが同じ）すべての文字列集合と区間が一対一対応していて重複していないからです。文字列Sを符号化した後の状態（区間）を[L(S),L(S)+R(S))とすると、Sの後に文字列Uを符号化した後の区間[L(SU),L(SU)+R(SU))（SUはSとUを連結した文字列）について、L(S)<=L(SU)、L(SU)+R(SU)<=R(S)が成リ立ちます。そのため、L(SU)<= V' < L(SU)+R(SU)を満たすV'であれば、L(S)<= L(SU) <= V' < L(SU)+R(SU) <= L(S)+R(S)、つまりL(S) <= V' < L(S)+R(S)も成り立ちます。
ここまでの話では、LとRを無限精度の実数として扱っていましたが、実装ではLとRを有限精度（32bitなど）の整数として実現します。区間の精度を32bitとし、0 <= L, R < 2^32 が成り立つように区間を2^32倍したものを状態として扱います。そして、すべての文字を符号化した後に最終的な状態Vを出力するのではなく、Vを上位の桁から決定した順に出力し、LとRの不必要になった桁をシフトで移動させます。詳細については次の節で説明します。
