はじめに
今回はバイナリレンジコーダ (Binary Range Coder) を取り上げます。記号 {0, 1} だけを符号化する方法に「二値算術符号」があります。これに対し、3 つ以上の記号を符号化する方法を「多値算術符号」と呼びます。一般に、二値算術符号は多値算術符号よりも簡単にプログラムできるため、画像の圧縮などで使われることがあります。
レンジコーダの場合、二値でも多値でも簡単にプログラムできますが、モデル化によっては、バイナリレンジコーダを用いた方が効率的にデータを圧縮することができる場合があります。今回はバイナリレンジコーダを用いていくつかのモデルを作成して、実際にファイルを圧縮してみましょう。
●バイナリレンジコーダと数値の対応
バイナリレンジコーダは 2 種類の記号 {0, 1} しか扱うことができないので、このままでは 0 と 1 以外の数値（多値）を表すことができません。このため、バイナリレンジコーダで多値を表す方法を考えなければいけません。
一番簡単な方法は、0 から N までの数値を表すのに N 個の「コンテキスト (context)」を用意することです。コンテキストはバイナリレンジコーダで使用する記号 {0, 1} の出現頻度表と考えてください。たとえば、0 から 7 までの数値を符号化する場合を考えてみましょう。次の図を見てください。
符号化する数値とコンテキストの番号を対応させるところがポイントです。数値 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 個のコンテキストを用意します。多数のコンテキストを使いますが、静的符号化の場合、各記号の出現確率は多値レンジコーダと変わらないことに注意してください。次の図を見てください。
たとえば、静的符号化で記号 {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 に初期化すると多値レンジコーダとは異なる出現確率になります。次の図を見てください。
多値レンジコーダの場合、記号 {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 から 7 の記号は上図に示す符号木（二分木）で表すことができます。左の枝には符号 0 を、右の枝には符号 1 を割り当てます。葉に記号を割り当て、木のルートから葉までの経路が符号語になります。木を配列で表すと、節の親子関係は次に示す式で表すことができるので、木をたどる処理は簡単です。
節 N : 左の子 : 2 * N + 1 右の子 : 2 * N + 2 親 : (N - 1) / 2
記号数を N とすると、葉の番号は記号に N - 1 を足した値になります。図 7 の場合、記号 4 は葉 11 に対応し、その親は (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 range(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 range(size):
fout.putc(freq.decode(rc))
RangeCoder と Freq2 のオブジェクトを生成して、変数 rc と freq にセットします。あとは適応型レンジコーダと同様に、freq.enocde() を呼び出して符号化を行い、freq.decode() を呼び出して記号を復号するだけです。
●評価結果
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。
表 : バイナリモデルの結果 (増分値 = +4)
上限値 B_LIMIT
ファイル名 サイズ 0x800 0x400 0x200 符号化 復号
--------------------------------------------------------------------
alice29.txt 152,089 86,692 86,692 86,843 1.616 1.492
asyoulik.txt 125,179 75,183 75,143 75,172 1.517 1.148
cp.html 24,603 16,140 16,143 16,162 0.366 0.249
fields.c 11,150 6,946 6,905 6,866 0.165 0.151
grammar.lsp 3,721 2,194 2,189 2,185 0.063 0.040
kennedy.xls 1,029,744 421,926 412,162 405,032 11.133 9.537
lcet10.txt 426,754 246,311 245,719 245,213 4.638 3.899
plrabn12.txt 481,861 273,321 273,817 274,908 5.215 4.453
ptt5 513,216 68,403 68,118 68,126 5.386 4.656
sum 38,240 22,179 21,643 21,188 0.443 0.361
xargs.1 4,227 2,636 2,630 2,623 0.077 0.050
--------------------------------------------------------------------
合計 2,810,784 1,221,931 1,211,161 1,204,318 30.619 26.036
符号化と復号の単位 : 秒
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
圧縮率は多値レンジコーダ (適応型) よりも少しですが高くなっています。今回のテストでは、累積度数の上限値 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 のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
●補足 (2007/08/04)
今回のバイナリレンジコーダでは、記号 {0, 1} の出現頻度を Context のインスタンス変数 c0 と c1 に格納しています。このほかに、記号 0 の出現頻度 c0 と記号 {0, 1} の合計値 sum を使って記号を符号化する方法もあります。この方法は June さんに教えてもらいました。June さんに感謝いたします。
プログラムは次のようになります。
リスト : Context の定義 (その２)
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 range(size - 1)]
クラス AlphaFreq はαモデルで用いる記号の出現頻度表です。引数 size は記号の種類を表します。この場合、インスタンス変数 size に size - 1 をセットして、size - 1 個のコンテキストを用意します。
次は符号化を行うメソッド encode() を作ります。
リスト : αモデルの符号化
def encode(self, rc, c):
for x in range(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
while ループで 0 番目のコンテキストから順番に復号していき、1 を復号したコンテキストの番号が復号する記号になります。復号した記号 bit が 1 ならば、while ループを脱出します。このときの変数 c の値が、復号する記号になります。すべてのコンテキストで 0 を復号したら while ループを終了します。この場合、復号する記号は size (記号の種類 - 1) になります。
●γモデルの作成
次はγ符号に基づくモデル (γモデル) を作成しましょう。γ符号はα符号とビット列の 2 つの部分から構成されます。α符号の部分はαモデルを使えばいいので、ビット列を符号化・復号するモデル (ビット列モデル) が必要になります。次のリストを見てください。
リスト : ビット列のモデル
class BitsFreq:
def __init__(self, size):
self.size = size
self.context = [Context() for _ in range(size)]
def encode(self, rc, c):
for x in range(self.size):
bit = (c >> x) & 1
self.context[x].encode(rc, bit)
def decode(self, rc):
c = 0
for x in range(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 の場合、ビット列モデルは作成しません。符号化される記号は 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 range(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 から復号する記号を求めます。
●参考文献
- 植松友彦, 『文書データ圧縮アルゴリズム入門』, ＣＱ出版社, 1994
- 広井誠, 『LZ77 符号によるファイルの圧縮とその改良（後編）』, Interface 2006 年 7 月号, ＣＱ出版社
バイナリレンジコーダのプログラムは Yuta Mori さんの Web サイト white page で公開されているプログラムを参考にさせていただきました。素晴らしいプログラムを公開されている Yuta Mori さんに感謝いたします。
●プログラムリスト１
#
# rangecoder2.py : バイナリレンジコーダ
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
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 range(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 range(size - 1)]
# 符号化
def encode(self, rc, c):
for x in range(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 range(size)]
# 符号化
def encode(self, rc, c):
for x in range(self.size):
bit = (c >> x) & 1
self.context[x].encode(rc, bit)
# 復号
def decode(self, rc):
c = 0
for x in range(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 range(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
●プログラムリスト２
#
# brc0.py : バイナリレンジコーダ (binary range coder)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from rangecoder2 import *
# ファイルの読み込み
def read_file(fin):
while True:
c = fin.getc()
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 range(size):
fout.putc(freq.decode(rc))
# 符号化
def encode_file(name1, name2):
size = os.path.getsize(name1)
with ByteIO(name1, ROPEN) as fin, ByteIO(name2, WOPEN) as fout:
fout.putc((size >> 24) & 0xff)
fout.putc((size >> 16) & 0xff)
fout.putc((size >> 8) & 0xff)
fout.putc(size & 0xff)
if size > 0: encode(fin, fout)
# 復号
def decode_file(name1, name2):
with ByteIO(name1, ROPEN) as fin, ByteIO(name2, WOPEN) as fout:
size = 0
for _ in range(4):
size = (size << 8) + fin.getc()
if size > 0: decode(fin, fout, size)
# オプション解析
parser = argparse.ArgumentParser(description='BinaryRangeCoder符号')
parser.add_argument('name1', help='入力ファイル')
parser.add_argument('name2', help='出力ファイル')
parser.add_argument('-e', '--encode', action='store_true', help='符号化')
parser.add_argument('-d', '--decode', action='store_true', help='復号')
args = parser.parse_args()
# 実行
s = time.time()
if args.encode and not args.decode:
encode_file(args.name1, args.name2)
elif args.decode:
decode_file(args.name1, args.name2)
else:
print('option error')
e = time.time()
print('{:.3f}'.format(e - s))
改訂 2022 年 9 月 23 日