レンジコーダの続きです。今回は「バイナリレンジコーダ (Binary Range Coder) 」を取り上げます。
記号 {0, 1} だけを符号化する方法に「二値算術符号」があります。これに対し、3 つ以上の記号を符号化する方法を「多値算術符号」と呼びます。一般に、二値算術符号は多値算術符号よりも簡単にプログラムできるため、画像の圧縮などで使われることがあります。ちょっと古い話ですが、Interface 1997 1996 年 9 月号の『特集 ファイル&画像 圧縮技術の原理と応用』によると、画像の圧縮ツール PIC2 では 『エントロピー符号化として二値算術符号を採用しています』 とのことです。
レンジコーダの場合、二値でも多値でも簡単にプログラムできますが、モデル化によっては、バイナリレンジコーダ (Binary Range Coder) を用いた方が効率的にデータを圧縮することができる場合があります。今回はバイナリレンジコーダを用いていくつかのモデルを作成して、実際にファイルを圧縮してみましょう。
バイナリレンジコーダは 2 種類の記号 {0, 1} しか扱うことができないので、このままでは 0 と 1 以外の数値(多値)を表すことができません。このため、バイナリレンジコーダで多値を表す方法を考えなければいけません。
一番簡単な方法は、0 から N までの数値を表すのに N 個の「コンテキスト (context) 」を用意することです。コンテキストはバイナリレンジコーダで使用する記号 {0, 1} の出現頻度表と考えてください。たとえば、0 から 7 までの数値を符号化する場合を考えてみましょう。次の図を見てください。
Context\ N | 0 1 2 3 4 5 6 7 ------------+-------------------------- [Context 0] | 1 0 0 0 0 0 0 0 [Context 1] | 1 0 0 0 0 0 0 [Context 2] | 1 0 0 0 0 0 [Context 3] | 1 0 0 0 0 [Context 4] | 1 0 0 0 [Context 5] | 1 0 0 [Context 6] | 1 0 図 : バイナリレンジコーダによる数値の符号化
符号化する数値とコンテキストの番号を対応させるところがポイントです。数値 N を符号化する場合、0 から N - 1 までのコンテキストでは 0 を符号化し、N 番目のコンテキストで 1 を符号化します。そして、1 を符号化した時点で処理を終了します。復号も簡単です。0 番目のコンテキストから順番に復号していき、1 を復号したときのコンテキストの番号が復号する数値になります。
たとえば 0 を符号化する場合、Context 0 で 1 を符号化して終了します。6 を符号化する場合は、Context 0 から 5 までは 0 を符号化し、Context 6 で 1 を符号化します。7 を符号化する場合、Context 7 は必要ありません。数値は 0 から 7 までなので、すべてのコンテキストが 0 であれば、数値は 7 であることがわかるからです。つまり、復号するときに Context 6 が 1 であれば 6 に、0 であれば 7 に復号します。
この方法は拙作のページ 正整数の符号化 で説明した Elias 符号 (α符号) と呼ばれる符号と同じ考え方です。Elias 符号は「小さな正整数ほど短い符号語が割り当てられる」という特徴があります。バイナリレンジコーダを用いる場合、これらの Elias 符号に基づいて符号化を行うモデルを考えることができます。このページでは、α符号に基づくモデルを「αモデル」、γ符号に基づくモデルを「γモデル」と呼ぶことにします。
αモデルでファイルを圧縮する場合、記号の種類は 256 個 (0 - 255) あるので、255 個のコンテキストを用意します。多数のコンテキストを使いますが、静的符号化の場合、各記号の出現確率は多値レンジコーダと変わらないことに注意してください。次の図を見てください。
頻度 記号 頻度 確率 記号 0 1 確率 -------------- ---------------------------------- a 1 1/8 a 7 1 1/8 b 1 1/8 b 6 1 7/8 * 1/7 = 1/8 c 2 1/4 c 4 2 7/8 * 6/7 * 2/6 = 1/4 d 4 1/2 d 7/8 * 6/7 * 4/6 = 1/2 (A) 多値の場合 (B) αモデルの場合 図 : 静的符号化の出現頻度表
たとえば、静的符号化で記号 {a, b, c, d} の出現頻度が {1, 1, 2, 4} だったとしましょう。多値レンジコーダの場合、出現確率は上図 (A) のようになります。αモデルの場合、記号 a のコンテキストは、0 が a 以外の記号の個数を表すので 7 になり、1 が a の個数になるので 1 なります。したがって、確率は 1/8 になります。記号 b の場合、0 が a, b 以外の記号の個数 (6) で、1 が b の個数 (1) になるので、確率は 7/8 * 1/7 = 1/8 になります。このように計算していくと上図 (B) のようになり、記号の出現確率は (A) と同じになります。
このように、複数のコンテキストを使っても、記号の出現確率は多値レンジコーダの場合と変わりありません。それでは、多値レンジコーダと同様に圧縮できるかといえば、実はそうではないのです。レンジコーダは整数で演算するので、計算の精度が問題になるからです。αモデルの場合、大きな記号ほど計算回数が多くなるので、多値レンジコーダよりも精度は劣化してしまいます。このため、圧縮率は多値レンジコーダよりも悪くなると思われます。
ただし、適応型符号化でαモデルを実装する場合、出現頻度表を 1 に初期化すると多値レンジコーダとは異なる出現確率になります。次の図を見てください。
頻度 記号 頻度 確率 記号 0 1 確率 -------------- ---------------------------------- a 1 1/4 a 1 1 1/2 b 1 1/4 b 1 1 1/2 * 1/1 = 1/4 c 1 1/4 c 1 1 1/2 * 1/2 * 1/2 = 1/8 d 1 1/4 d 1/2 * 1/2 * 1/2 = 1/8 (A) 多値の場合 (B) αモデルの場合 図 : 適応型符号化の出現頻度表
多値レンジコーダの場合、記号 {a, b, c, d} の出現頻度を 1 に初期化するので、出現確率は上図 (A) のように、どの記号でも 1/4 になります。ところがαモデルの場合、各コンテキストの出現頻度を 1 に初期化すると、各記号の出現確率は同じになりません。上図 (B) を見てください。記号 a の出現確率は 1/2 になりますが、記号 b の出現確率は 1/2 * 1/2 = 1/4 になります。つまり、小さな記号は出現確率が大きく、大きな記号になるほど出現確率は小さくなるのです。
αモデルの特徴はこれだけではありません。出現頻度の更新をコンテキストごとに行うことも特徴のひとつです。たとえば、初期状態から記号 a の個数を +1 してみましょう。多値レンジコーダの場合、記号 a の出現確率は 2/5 になりますが、αモデルでは記号 a のコンテキストを更新するだけなので、出現確率は 2/3 になります。さらに +1 すると、αモデルでは出現確率が 3/4 になりますが、多値レンジコーダの場合は 3/6 = 1/2 にしかなりません。出現確率はαモデルの方が大きくなりますね。
このように、αモデルを適応型符号化で実装すると、入力された記号数が少ない状態でも、小さな記号の出現確率が大きくなり、大きな記号の出現確率は小さくなる特徴があります。この特徴はγモデルでも同じです。αモデルとγモデルは、小さな整数値ほど出現確率が高い場合に適しているモデルといえます。
それから、もう一つ簡単な方法として「符号木」に基づいたモデルを考えることができます。次の図を見てください。
○0 / \ / \ / \ / \ / \ ○1 ○2 / \ / \ / \ / \ ○3 ○4 ○5 ○6 / \ / \ / \ / \ ● ● ● ● ● ● ● ● 7 8 9 10 11 12 13 14 記号:0 1 2 3 4 5 6 7 ○:内部ノード(節) ●:外部ノード(葉) 図 : 符号木
0 から 7 の記号は上図に示す符号木(二分木)で表すことができます。左の枝には符号 0 を、右の枝には符号 1 を割り当てます。葉に記号を割り当て、木のルートから葉までの経路が符号語になります。木を配列で表すと、節の親子関係は次に示す式で表すことができるので、木をたどる処理は簡単です。
節 N : 左の子 : 2 * N + 1 右の子 : 2 * N + 2 親 : (N - 1) / 2
記号数を N とすると、葉の番号は記号に N - 1 を足した値になります。図 7 の場合、記号 4 は葉 11 に対応し、その親は (14 - 1) (11 - 1) / 2 = 5 になります。節 5 の親は 2 で、節 2 の親はルートの 0 になります。
ルートから葉までの経路は 0 - 2 - 5 - 11 になるので、符号語は "1 0 0" になります。節ごとにコンテキストを用意し、経路に沿ってバイナリレンジコーダで符号化を行えば、0 から 7 までの記号を符号化することができます。
復号も簡単です。ルートからバイナリレンジコーダで復号を行い、0 ならば左の子を、1 ならば右の子をたどります。そして、葉に到達したら復号を終了します。葉に対応する記号が求める記号になります。
このページでは、符号木に基づくモデルを「バイナリモデル (Binary Model) 」と呼ぶことにします。Elias 符号に基づくモデルは、小さな整数値ほど出現確率が高い場合に適しています。一般的なテキストファイルの場合は、バイナリモデルの方が適しています。
それではプログラムを作りましょう。最初に、記号 {0, 1} の出現頻度表を表すクラス Context を定義します。
リスト : Context の定義 B_INC = 4 B_LIMIT = 0x200 # コンテキスト class Context: def __init__(self): self.c0 = 1 self.c1 = 1 # 更新 def update(self, bit): if bit > 0: self.c1 += B_INC else: self.c0 += B_INC if self.c0 + self.c1 >= B_LIMIT: self.c0 = (self.c0 >> 1) | 1 self.c1 = (self.c1 >> 1) | 1
インスタンス変数 c0 は記号 0 の出現頻度、c1 は記号 1 の出現頻度を表します。なお、今回のバイナリレンジコーダは適応型符号化です。メソッド update は Context を更新します。bit が 0 より大きい場合は c1 に B_INC (4) を加算します。そうでなければ c0 に B_INC を加算します。c0 + c1 が B_LIMIT 以上になったら、c0 と c1 の値を半分にします。
次はビットを符号化するメソッド encode を作ります。
リスト : ビットの符号化 def encode(self, rc, bit): temp = rc.range / (self.c0 + self.c1) if bit > 0: rc.low += temp * self.c0 rc.range = temp * self.c1 else: rc.range = temp * self.c0 rc.encode_normalize() self.update(bit)
引数 bit が符号化する記号を表します。記号 0 の出現確率は c0 / (c0 + c1) で、記号 1 の出現確率は c1 / (c0 + c1) で求めることができます。bit が 1 の場合は、low と range の値を更新し、0 の場合は range の値だけ更新します。あとは、正規化を行って出現頻度表を更新します。バイナリレンジコーダの場合、記号が 2 種類 {0, 1} しかないので、多値レンジコーダのように累積度数を求める処理は不要になります。このため、プログラムはとても簡単になります。
次はビットの復号を行うメソッド decode を作ります。
リスト : ビットの復号 def decode(self, rc): temp = rc.range / (self.c0 + self.c1) if rc.low / temp < self.c0: bit = 0 rc.range = temp * self.c0 else: bit = 1 rc.low -= temp * self.c0 rc.range = temp * self.c1 rc.decode_normalize() self.update(bit) return bit
復号処理も簡単です。low の値が range * c0 / (c0 + c1) よりも小さい場合は記号 0 を復号し、そうでなければ 1 を復号します。1 を復号した場合は low と range の値を更新し、0 を復号した場合は range の値だけを更新します。あとは、正規化と出現頻度表の更新を行って、return で復号した bit を返します。
次はバイナリモデルを表すクラスを作成します。次のリストを見てください。
リスト : バイナリモデル # 出現頻度表 class Freq2: def __init__(self, size): self.size = size self.context = [Context() for _ in xrange(size - 1)]
クラス名は Freq2 としました。引数 size は記号の種類を表します。この値をインスタンス変数 size に格納します。この場合、size - 1 個の節が必要になるので、節に対応する Context のオブジェクトを size - 1 個用意します。
次は符号化を行うメソッド encode を作ります。
リスト : バイナリモデルの符号化 def encode(self, rc, code): def encode_sub(node): if node > 0: p = (node - 1) / 2 encode_sub(p) # 奇数は左の子 (1), 偶数は右の子 (0) bit = node & 1 self.context[p].encode(rc, bit) # encode_sub(code + self.size - 1)
引数 rc は RangeCoder のオブジェクト、code は符号化する記号です。実際の処理は内部関数 encode_sub で行います。引数 node は節の番号を表します。最初に呼び出すときは、葉の番号 code + size - 1 を渡します。ここから再帰呼び出しでルート方向に木をたどります。
符号化を行う場合、node が親節の左の子ならば 1 を符号化し、右の子ならば 0 を符号化します。説明とは逆になっていることに注意してください。奇数の節は左の子、偶数の節は右の子になります。あとは、親節のコンテキスト context[p] で bit を符号化します。
次は復号を行うメソッド decode を作ります。
リスト : バイナリモデルの復号 def decode(self, rc): node = 0 node_size = self.size - 1 while node < node_size: bit = self.context[node].decode(rc) if bit > 0: # 1 は左の子 node = 2 * node + 1 else: # 0 は右の子 node = 2 * node + 2 return node - node_size
変数 node はルート (0) に初期化します。そして、節 node のコンテキストcontext[node] でビットを復号します。bit が 1 ならば左の子を、0 ならば右の子をたどります。node が node_size よりも大きくなったならば、node は葉に到達したので復号を終了します。記号の値は node - node_size になります。
最後に、バイナリモデルを使って符号化・復号を行う関数 encode と decode を作ります。
リスト : バイナリレンジコーダの符号化と復号 # 符号化 def encode(fin, fout): rc = RangeCoder(fout, ENCODE) freq = Freq2(256) for x in read_file(fin): freq.encode(rc, x) rc.finish() # 復号 def decode(fin, fout, size): rc = RangeCoder(fin, DECODE) freq = Freq2(256) for _ in xrange(size): putc(fout, freq.decode(rc))
RangeCoder と Freq2 のオブジェクトを生成して、変数 rc と freq にセットします。あとは適応型レンジコーダと同様に、メソッド enocde を呼び出して符号化を行い、メソッド decode を呼び出して記号を復号するだけです。
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。
表 : バイナリモデルの結果 (増分値 = +4) 上限値 B_LIMIT ファイル名 サイズ 0x800 0x400 0x200 符号化 復号 -------------------------------------------------------------------- alice29.txt 152,089 86,692 86,692 86,843 10.01 9.53 asyoulik.txt 125,179 75,183 75,143 75,172 8.31 7.78 cp.html 24,603 16,140 16,143 16,162 1.66 1.54 fields.c 11,150 6,946 6,905 6,866 0.77 0.71 grammar.lsp 3,721 2,194 2,189 2,185 0.27 0.24 kennedy.xls 1,029,744 421,926 412,162 405,032 68.12 65.54 lcet10.txt 426,754 246,311 245,719 245,213 28.10 26.70 plrabn12.txt 481,861 273,321 273,817 274,908 31.66 29.82 ptt5 513,216 68,403 68,118 68,126 32.67 31.74 sum 38,240 22,179 21,643 21,188 2.60 2.43 xargs.1 4,227 2,636 2,630 2,623 0.30 0.27 -------------------------------------------------------------------- 合計 2,810,784 1,221,931 1,211,161 1,204,318 184.47 176.30 # 符号化と復号の単位 : 秒 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
圧縮率は多値レンジコーダ (適応型) よりも少しですが高くなっています。今回のテストでは、累積度数の上限値 B_LIMIT は 0x400 から 0x200 くらいで良さそうです。そのかわり、実行時間はとても遅くなりました。バイナリレンジコーダは 1 ビットずつ処理しているので、符号化・復号ともに時間がかかるのは仕方がないでしょう。
ところで、バイナリモデルは有限文脈モデルと組み合わせると高い圧縮率を達成することができます。order-1, order-2 の実行結果を示します。
表 : 有限文脈モデルの結果 (B_LIMIT=0x200, 増分値=+4) ファイル名 サイズ order-0 order-1 order-2 ----------------------------------------------------- alice29.txt 152,089 86,843 65,576 52,826 asyoulik.txt 125,179 75,172 54,472 45,191 cp.html 24,603 16,162 11,618 9,431 fields.c 11,150 6,866 4,699 3,885 grammar.lsp 3,721 2,185 1,657 1,540 kennedy.xls 1,029,744 405,032 293,327 167,050 lcet10.txt 426,754 245,213 185,359 147,885 plrabn12.txt 481,861 274,908 204,406 171,054 ptt5 513,216 68,126 53,384 56,933 sum 38,240 21,188 17,635 16,570 xargs.1 4,227 2,623 2,131 2,083 ----------------------------------------------------- 合計 2,810,784 1,204,318 894,300 674,448
order-2 の場合、エスケープ記号を使ったモデルにはかないませんが、order-1 と order-2 のどちらでも多値レンジコーダより高い圧縮率になります。バイナリレンジコーダを使う場合は、有限文脈モデルと組み合わせるとよいのかもしれません。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
今回のバイナリレンジコーダでは、記号 {0, 1} の出現頻度を Context のインスタンス変数 c0 と c1 に格納しています。このほかに、記号 0 の出現頻度 c0 と記号 {0, 1} の合計値 sum を使って記号を符号化する方法もあります。この方法は June さんに教えてもらいました。June さんに感謝いたします。
プログラムは次のようになります。
リスト : Context の定義 (その2) class Context: def __init__(self): self.sum = 2 self.c0 = 1 # 更新 def update(self, bit): self.sum += B_INC if bit == 0: self.c0 += B_INC if self.sum >= B_LIMIT: self.c0 = (self.c0 >> 1) | 1 self.sum = (self.sum >> 1) | 1 if self.sum <= self.c0: self.sum = self.c0 + 1 # ビットの符号化 def encode(self, rc, bit): temp = rc.range / self.sum if bit > 0: rc.low += temp * self.c0 rc.range -= temp * self.c0 else: rc.range = temp * self.c0 rc.encode_normalize() self.update(bit) # ビットの復号 def decode(self, rc): temp = rc.range / self.sum if rc.low / temp < self.c0: bit = 0 rc.range = temp * self.c0 else: bit = 1 rc.low -= temp * self.c0 rc.range -= temp * self.c0 rc.decode_normalize() self.update(bit) return bit
Context のインスタンス変数 c0 には記号 0 の出現頻度を、sum には記号 {0, 1} の出現頻度の合計値を格納します。ポイントは記号 1 の符号化・復号の処理です。range の幅を狭めるとき、今までは range = range * c1 / (c0 + c1) としましたが、この式は次のように変形することができます。
range * c1 / (c0 + c1) = range * (1 - c0/(c0 + c1)) = range - range * c0 / (c0 + c1)
したがって、range = range * c1 / (c0 + c1) は range -= range * c0 / (c0 + c1) と表すことができます。レンジコーダは整数で演算しているので、range0 = range * c0 / (c0 + c1) と range1 = range * c1 / (c0 + c1) の値を足しても range になるとは限りません。記号 1 で range の値を更新するとき、c1 を使って range1 を計算するよりも、range から range0 を引いた残り全てを range1 に割り当てたほうが、圧縮率が向上する場合があります。
実際にバイナリモデルで試してみたところ、数バイトから数十バイトほど圧縮率が高くなるファイルがありました。ご参考までに、Context を改良したバイナリモデルの評価結果を示します。
表 : バイナリモデルの結果 (B_LIMIT=0x200, 増分値=+4) ファイル名 サイズ Binary 改良版 ------------------------------------------- alice29.txt 152,089 86,843 86,830 asyoulik.txt 125,179 75,172 75,167 cp.html 24,603 16,162 16,161 fields.c 11,150 6,866 6,866 grammar.lsp 3,721 2,185 2,185 kennedy.xls 1,029,744 405,032 404,990 lcet10.txt 426,754 245,213 245,166 plrabn12.txt 481,861 274,908 274,882 ptt5 513,216 68,126 68,112 sum 38,240 21,188 21,188 xargs.1 4,227 2,623 2,623 ------------------------------------------- 合計 2,810,784 1,204,318 1,204,170
興味のある方は他のモデルでも試してみてください。
次は Elias 符号の中のα符号に基づくモデル(αモデル)を作ります。
リスト : αモデル class AlphaFreq: def __init__(self, size): self.size = size - 1 self.context = [Context() for _ in xrange(size - 1)]
クラス AlphaFreq はαモデルで用いる記号の出現頻度表です。引数 size は記号の種類を表します。この場合、インスタンス変数 size に size - 1 をセットして、size - 1 個のコンテキストを用意します。
次は符号化を行うメソッド encode を作ります。
リスト : αモデルの符号化 def encode(self, rc, c): for x in xrange(self.size): if x < c: bit = 0 else: bit = 1 self.context[x].encode(rc, bit) if bit: break
引数 rc は RangeCoder のオブジェクト、c は符号化する記号です。0 から c - 1 番目のコンテキストでは 0 を符号化して、c 番目のコンテキストで 1 を符号化します。記号が size の場合は、すべてのコンテキストで 0 を符号化して終了します。
次は復号を行うメソッド decode を作ります。
リスト : αモデルの復号 def decode(self, rc): c = 0 while c < self.size: bit = self.context[c].decode(rc) if bit: break c += 1 return c
for ループで 0 番目のコンテキストから順番に復号していき、1 を復号したコンテキストの番号が復号する記号になります。復号した記号 bit が 1 ならば、while ループを脱出します。このときの変数 c の値が、復号する記号になります。すべてのコンテキストで 0 を復号したら for ループを終了します。この場合、復号する記号は size (記号の種類 - 1) になります。
次はγ符号に基づくモデル(γモデル)を作成しましょう。γ符号はα符号とビット列の 2 つの部分から構成されます。α符号の部分はαモデルを使えばいいので、ビット列を符号化・復号するモデル(ビット列モデル)が必要になります。次のリストを見てください。
リスト : ビット列のモデル class BitsFreq: def __init__(self, size): self.size = size self.context = [Context() for _ in xrange(size)] def encode(self, rc, c): for x in xrange(self.size): bit = (c >> x) & 1 self.context[x].encode(rc, bit) def decode(self, rc): c = 0 for x in xrange(self.size): bit = self.context[x].decode(rc) if bit: c |= bit << x return c
クラス BitsFreq はビット列モデルで用いる記号の出現頻度表です。引数 size は符号化・復号するビット数を表します。ビット数を size とすると、size 個のコンテキストを用意します。
符号化はメソッド encode で行います。引数 c は符号化する記号です。for ループで、c の下位ビットから順番に Context のメソッド encode で符号化を行い、size 個のビットを符号化したら終了します。
復号はメソッド decode で行います。for ループで 0 番目のコンテキストから順番に Context のメソッド decode でビットを復号して変数 c にセットし、size 個のビットを復号したら for ループを終了します。最後に復号した記号 c を返します。
αモデルとビット列モデルを使うとγモデルは簡単にプログラムできます。γモデルはビット列モデルを一つだけ使う実装方法もありますが、今回は複数のビット列モデルを使って階層的なモデル (structured model) を構成します。次の図を見てください。
αモデルの値 ┌───┐ │ 0 │ ビット列モデル ├───┤ ┌───────────────────┐ │ 1─┼─→│ビット数 1, 記号数 2, 記号 1 - 2 │ ├───┤ ├───────────────────┤ │ 2─┼─→│ビット数 2, 記号数 4, 記号 3 - 6 │ ├───┤ ├───────────────────┤ │ 3─┼─→│ビット数 3, 記号数 8, 記号 7 - 14 │ ├───┤ ├───────────────────┤ │ 4─┼─→│ビット数 4, 記号数 16, 記号 15 - 30 │ ├───┤ ├───────────────────┤ │ 5─┼─→│ビット数 5, 記号数 32, 記号 31 - 62 │ ├───┤ ├───────────────────┤ │ 6─┼─→│ビット数 6, 記号数 64, 記号 63 - 126 │ ├───┤ ├───────────────────┤ │ 7─┼─→│ビット数 7, 記号数 128, 記号 127 - 254│ ├───┤ ├───────────────────┤ │ 8─┼─→│ビット数 8, 記号数 256, 記号 255 - 510│ └───┘ └───────────────────┘ 図 : γモデルの階層構造
αモデルで符号化される値ごとに、対応するビット列モデルを作成します。αモデルの値が 0 の場合、ビット列モデルは作成しません。符号化される記号は 0 になります。αモデルの値が 1 の場合は、ビット数 1 のビット列モデルを作成します。この場合、2 個の記号を符号化できるので、ここに記号 1と 2 を割り当てます。αモデルの値が N の場合は、ビット数N 個のビット列モデルを作成し、そこに、2 ** N - 1 から 2 ** (N + 1) - 2 の記号を割り当てます。このような階層的なモデルを用いることで、圧縮率を向上させることができます。
それでは、γモデルのプログラムを示します。次のリストを見てください。
リスト : γモデル class GammaFreq: def __init__(self, size): n2 = size >> 1 n1 = 0 while n2 > 0: n1 += 1 n2 >>= 1 self.size = n1 self.context1 = AlphaFreq(n1 + 1) self.context2 = [None] * (n1 + 1) for x in xrange(1, n1 + 1): self.context2[x] = BitsFreq(x) def encode(self, rc, n): n1 = 0 n2 = (n + 1) >> 1 while n2 > 0: n1 += 1 n2 >>= 1 self.context1.encode(rc, n1) if n1 > 0: self.context2[n1].encode(rc, n + 1) def decode(self, rc): n1 = self.context1.decode(rc) if n1 > 0: n2 = self.context2[n1].decode(rc) n1 = (1 << n1) + n2 - 1 return n1
クラス GammaFreq はγモデルで用いる記号の出現頻度表です。引数 size は符号化・復号する記号数を表します。最初にαモデルで符号化する記号の上限値を変数 n1 に求めます。0 から n1 までの記号を符号化するので、AlpahFreq() に与える引数の値は n1 + 1 になります。次に、for ループで 1 から n1 までのビット列モデルを生成します。
符号化はメソッド encode で行います。引数 n は符号化する記号です。最初にαモデルで符号化する数値を n1 に求め、AlphaFreq のメソッド encode で符号化します。次に、n1 が 0 よりも大きい場合はビット列を BitsFreq のメソッド encode で符号化します。符号化するビット列は n + 1 になることに注意してください。
復号はメソッド decode で行います。AlphaFreq のメソッド decode でαモデルの値を復号して変数 n1 にセットします。n1 が 0 よりも大きい場合は BitsFreq のメソッド decode でビット列を復号して変数 n2 にセットします。そして、n1 と n2 から復号する記号を求めます。
バイナリレンジコーダのプログラムは Yuta Mori さんの Web サイト white page で公開されているプログラムを参考にさせていただきました。素晴らしいプログラムを公開されている Yuta Mori さんに感謝いたします。
# coding: utf-8 # # rangecoder2.py : バイナリレンジコーダ # # Copyright (C) 2007 Makoto Hiroi # # 改訂 2007/06/25 # バイナリモデル、αモデル、γモデルで # メソッド update を呼び出していた処理を削除 # from rangecoder import * B_INC = 4 B_LIMIT = 0x200 # コンテキスト class Context: def __init__(self): self.c0 = 1 self.c1 = 1 # 更新 def update(self, bit): if bit > 0: self.c1 += B_INC else: self.c0 += B_INC if self.c0 + self.c1 >= B_LIMIT: self.c0 = (self.c0 >> 1) | 1 self.c1 = (self.c1 >> 1) | 1 # 符号化 def encode(self, rc, bit): temp = rc.range / (self.c0 + self.c1) if bit > 0: rc.low += temp * self.c0 rc.range = temp * self.c1 else: rc.range = temp * self.c0 rc.encode_normalize() self.update(bit) # 復号 def decode(self, rc): temp = rc.range / (self.c0 + self.c1) if rc.low / temp < self.c0: bit = 0 rc.range = temp * self.c0 else: bit = 1 rc.low -= temp * self.c0 rc.range = temp * self.c1 rc.decode_normalize() self.update(bit) return bit ##### バイナリモデル ##### class Freq2: def __init__(self, size): self.size = size self.context = [Context() for _ in xrange(size - 1)] # 符号化 def encode(self, rc, code): def encode_sub(node): if node > 0: p = (node - 1) / 2 encode_sub(p) # 奇数は左の子 (1), 偶数は右の子 (0) bit = node & 1 self.context[p].encode(rc, bit) # encode_sub(code + self.size - 1) # 復号 def decode(self, rc): node = 0 node_size = self.size - 1 while node < node_size: bit = self.context[node].decode(rc) if bit > 0: # 1 は左の子 node = 2 * node + 1 else: # 0 は右の子 node = 2 * node + 2 return node - node_size ##### αモデル ##### class AlphaFreq: def __init__(self, size): self.size = size - 1 self.context = [Context() for _ in xrange(size - 1)] # 符号化 def encode(self, rc, c): for x in xrange(self.size): if x < c: bit = 0 else: bit = 1 self.context[x].encode(rc, bit) if bit: break # 復号 def decode(self, rc): c = 0 while c < self.size: bit = self.context[c].decode(rc) if bit: break c += 1 return c ##### γモデル ##### # ビット列モデル class BitsFreq: def __init__(self, size): self.size = size self.context = [Context() for _ in xrange(size)] # 符号化 def encode(self, rc, c): for x in xrange(self.size): bit = (c >> x) & 1 self.context[x].encode(rc, bit) # 復号 def decode(self, rc): c = 0 for x in xrange(self.size): bit = self.context[x].decode(rc) if bit: c |= bit << x return c # γモデル class GammaFreq: def __init__(self, size): n2 = size >> 1 n1 = 0 while n2 > 0: n1 += 1 n2 >>= 1 self.size = n1 self.context1 = AlphaFreq(n1 + 1) self.context2 = [None] * (n1 + 1) for x in xrange(1, n1 + 1): self.context2[x] = BitsFreq(x) # 符号化 def encode(self, rc, n): n1 = 0 n2 = (n + 1) >> 1 while n2 > 0: n1 += 1 n2 >>= 1 self.context1.encode(rc, n1) if n1 > 0: self.context2[n1].encode(rc, n + 1) # 復号 def decode(self, rc): n1 = self.context1.decode(rc) if n1 > 0: n2 = self.context2[n1].decode(rc) n1 = (1 << n1) + n2 - 1 return n1
# coding: utf-8 # # brc0.py : バイナリレンジコーダ (binary range coder) # # Copyright (C) 2007 Makoto Hiroi # import time, sys, getopt, os.path from rangecoder2 import * # ファイルの読み込み def read_file(fin): while True: c = getc(fin) if c is None: break yield c # バイナリレンジコーダの符号化 def encode(fin, fout): rc = RangeCoder(fout, ENCODE) freq = Freq2(256) for x in read_file(fin): freq.encode(rc, x) rc.finish() # バイナリレンジコーダの復号 def decode(fin, fout, size): rc = RangeCoder(fin, DECODE) freq = Freq2(256) for _ in xrange(size): putc(fout, freq.decode(rc)) # 符号化 def encode_file(name1, name2): size = os.path.getsize(name1) infile = open(name1, "rb") outfile = open(name2, "wb") putc(outfile, (size >> 24) & 0xff) putc(outfile, (size >> 16) & 0xff) putc(outfile, (size >> 8) & 0xff) putc(outfile, size & 0xff) if size > 0: encode(infile, outfile) infile.close() outfile.close() # 復号 def decode_file(name1, name2): infile = open(name1, "rb") outfile = open(name2, "wb") size = 0 for _ in xrange(4): size = (size << 8) + getc(infile) if size > 0: decode(infile, outfile, size) infile.close() outfile.close() # def main(): eflag = False dflag = False opts, args = getopt.getopt(sys.argv[1:], 'ed') for x, y in opts: if x == '-e' or x == '-E': eflag = True elif x == '-d' or x == '-D': dflag = True if eflag and dflag: print 'option error' elif eflag: encode_file(args[0], args[1]) elif dflag: decode_file(args[0], args[1]) else: print 'option error' # s = time.clock() main() e = time.clock() print "%.3f" % (e - s)