今回は「有限文脈モデル」について説明します。有限文脈モデルは、適応型レンジコーダを用いると簡単に実現することができます。
拙作のページ「シャノン・ファノ符号とハフマン符号」で説明した「無記憶情報源モデル」は、もっとも簡単な情報源モデルです。このモデルは、記号を生成するとき以前に生成した記号との間に関係がないため「無記憶」と呼ばれますが、このモデルを一般化して状態 (記憶) を持つモデルを考えることができます。参考文献『文書データ圧縮アルゴリズム入門』によると、状態 (記憶) があるモデルを「有限状態確率モデル」とか「マルコフ情報源モデル」と呼ぶそうです。
簡単に説明すると、情報源にはいくつかの状態があって、その状態によって記号の生成確率が異なります。そして、ある記号が生成されると別の状態へ移動します。これを「状態遷移」といいます。このようなモデルは状態遷移図で表すことができます。簡単な例を示しましょう。
┌────┐── b : 0.2 ─→┌────┐
┌→│ 状態Ａ │ │ 状態Ｂ │←┐
│ └────┘←─ a : 0.3 ──└────┘ │
│ │ │ │
└ a : 0.8 ┘ └ b : 0.7 ┘
図 1 : 簡単な状態遷移図
上図では、記号が a と b の 2 種類で、2 つの状態 A と B があります。A と B では記号の出現確率が異なることに注意してください。そして、A の状態で記号 b が出力されると、状態は B へ移ります。記号 a が出力されても状態は A のままです。逆に、状態 B で記号 a が出力されると、状態は A に移ります。記号 b が出力されても状態は移りません。
このモデルの場合、A と B ともに状態遷移する確率が低いので、aaaaaaabbbbbbb のように同じ記号が連続して出力される確率がとても高くなります。そして、この記号列を無記憶情報源モデルで符号化しても、効率よく圧縮できないことはすぐにわかると思います。
このような場合、状態によって記号の出現頻度表を切り替えることで、効率よく圧縮することができます。つまり、状態 A の出現頻度表 Table A と状態 B の出現頻度表 Table B を用意し、状態 A では Table A を、状態 B では Table B を使って符号化すればいいわけです。
このように、モデルが決まっていれば簡単なのですが、一般的なデータで有効なモデルを作成することはとても難しいことです。そこで、次のような単純なモデルを考えます。
これを「有限文脈モデル」といいます。そして、直前に出現した記号列の長さを「次数 (order)」といいます。有限文脈モデルは 1 次 (order-1) がいちばん簡単です。直前に出力した記号を覚えておいて、それに従って出現頻度表を切り替えるという単純な方法で実現できます。つまり、各記号ごとに出現頻度表を用意しておいて、直前に出力した記号が a であれば、a の出現頻度表を使って符号化を行うわけです。
したがって、記号が 256 種類あれば、出現頻度表も 256 個必要になります。order-2 であれば、ab や cd のあとに現れる記号の出現頻度表が必要になるので、個数は 256 * 256 = 65536 になります。このように、次数が大きくなるほど必要となるメモリ量が爆発的に増えるので、単純な方法では低次の有限文脈モデルしか実現できないのが欠点です。
order-1 や order-2 の有限文脈モデルは、適応型レンジコーダを使えば簡単にプログラムできます。ここで簡単な例題として order-2 のプログラムを作ってみましょう。次のリストを見てください。
リスト : 有限文脈モデル (order-2) の符号化
def encode(fin, fout):
rc = RangeCoder(fout, ENCODE)
freq = [[None] * 256 for _ in range(256)]
c00 = 0
c0 = 0
for x in read_file(fin):
if freq[c00][c0] is None: freq[c00][c0] = Freq(256, INC, LIMIT)
freq[c00][c0].encode(rc, x)
c00 = c0
c0 = x
rc.finish()
order-2 の場合、直前の 2 記号を変数 c0 と c00 に記憶しておいて、c0 と c00 の値によって出現頻度表を選択します。order-1 は直前の記号を変数 c0 に記憶することで実現できます。
出現頻度表は 2 次元配列 freq に格納します。freq は None で初期化しておきます。引数 c00 と c0 で出現頻度表を取り出し、それが None であれば Freq(256) で新しい出現頻度表を生成して freq[c00][c0] にセットします。あとは今までと同様に適応型レンジコーダで符号化するだけです。そして、c00 と c0 の値を更新して、直前の 2 記号を記憶します。
このプログラムでは c0 と c00 を 0 に初期化していますが、記号の範囲内であれば何でもかまいません。ただし、復号を行う関数 decode() と同じ値で初期化するように注意してください。
復号も簡単です。次のリストを見てください。
リスト : 有限文脈モデル (order-2) の復号
def decode(fin, fout, size):
freq = [[None] * 256 for _ in range(256)]
rc = RangeCoder(fin, DECODE)
c00 = 0
c0 = 0
for _ in range(size):
if freq[c00][c0] is None: freq[c00][c0] = Freq(256, INC, LIMIT)
x = freq[c00][c0].decode(rc)
fout.putc(x)
c00 = c0
c0 = x
符号化と同様に、直前の 2 記号 c0 と c00 の値によって出現頻度表を選択します。変数 c0 と c00 は符号化同じく 0 に初期化します。そして、選択した出現頻度表を使って、記号を適応型レンジコーダで復号します。あとは、c0 と c00 の値を更新するだけです。とても簡単ですね。
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。
表 : 有限文脈モデルの結果
ファイル名 サイズ order-0 order-1 order-2
------------------------------------------------------
alice29.txt 152,089 87,147 71,153 74,150
asyoulik.txt 125,179 75,533 59,733 65,493
cp.html 24,603 16,299 14,232 15,865
fields.c 11,150 7,164 6,570 7,414
grammar.lsp 3,721 2,305 2,449 2,769
kennedy.xls 1,029,744 460,734 382,459 272,423
lcet10.txt 426,754 249,491 195,676 187,560
plrabn12.txt 481,861 273,392 211,211 207,535
ptt5 513,216 78,090 58,594 68,650
sum 38,240 25,638 21,680 25,242
xargs.1 4,227 2,743 2,974 3,440
------------------------------------------------------
合計 2,810,784 1,278,536 1,026,731 930,541
order-0 と order-1 を比べると圧縮率は大幅に向上してます。ところが order-2 になると、大きなファイルの圧縮率は向上しますが、小さなファイルは order-1 よりも悪くなっています。前回説明したように、適応型レンジコーダは出現しない記号が多数あると、圧縮率が少し劣化するという欠点があります。
たとえば、記号が 0 と 1 しかないデータを符号化してみましょう。適応型符号化では記号 0 - 255 の出現頻度を 1 に初期化しています。このため、記号数が少ないうちは記号 2 - 255 の出現頻度の影響が大きくなり、圧縮率はどうしても劣化してしまいます。ようするに、記号をたくさん読み込まないと、その出現頻度表の確率はあてにならないというわけです。
order-1 には出現頻度表が 256 個、order-2 には 65536 個もあります。高次の有限文脈モデルになればなるほど、多数の出現頻度表を使うことになるので、この欠点の影響はとても大きなものになるでしょう。今回の結果はこの欠点があらわれていると思います。
そこで、適応型レンジコーダの欠点を改良する簡単な方法を紹介しましょう。一つは出現頻度表の累積度数の上限値を小さな値に設定することです。もう一つは、出現頻度表の更新時で記号数の増分値を +1 より大きくすることです。これは拙作のページ「Guest Book No.308」で大地さんから教えてもらった方法です。
二つの方法を適用すると、出現頻度表の更新が頻繁に行われるようになります。すると、最近出現している記号ほど確率が高くなり、データの局所的な変化に素早く追随することができるようになります。これが圧縮率が良くなる理由だと思われます。
ただし、この方法を使うと、その出現頻度表が表している値は正確な出現確率ではなくなります。つまり、無記憶情報源モデルで計算したエントロピーとは一致しなくなるのです。したがって、無記憶情報源モデルで求めた圧縮の限界よりも、圧縮率が良くなることもありますし、逆に今までよりも圧縮率が悪くなることもあります。どのようなデータでも圧縮率が向上するわけではありません。ご注意くださいませ。
それでは実際に、桁上がりのあるレンジコーダで試してみましょう。結果は次のようになりました。
表 : 適応型レンジコーダ (order-0) の結果
増分値 = +1 増分値 = +4
ファイル名 サイズ 従来版 0x8000 0x4000 0x8000 0x4000
-------------------------------------------------------------------------
alice29.txt 152,089 87,147 87,184 87,344 87,013 87,199
asyoulik.txt 125,179 75,533 75,591 75,731 75,442 75,596
cp.html 24,603 16,299 16,299 16,304 16,190 16,209
fields.c 11,150 7,164 7,164 7,164 7,068 7,023
grammar.lsp 3,721 2,305 2,305 2,305 2,235 2,235
kennedy.xls 1,029,744 460,734 439,758 433,591 427,600 426,102
lcet10.txt 426,754 249,491 248,641 248,640 247,554 247,601
plrabn12.txt 481,861 273,392 273,737 274,421 273,701 274,562
ptt5 513,216 78,090 75,432 74,808 72,655 72,115
sum 38,240 25,638 25,595 24,741 23,860 23,057
xargs.1 4,227 2,743 2,743 2,743 2,670 2,670
-------------------------------------------------------------------------
合計 2,810,784 1,278,536 1,254,449 1,247,792 1,235,988 1,234,369
記号の増分値は +1 と +4 で、累積度数表の上限値は 0x8000 と 0x4000 で試してみました。テキストファイルの場合、効果はほとんどありませんが、kennedy.xls や ptt5 のようにバイナリファイルでは効果があるようです。
有限文脈モデルの場合、この改良方法がとても有効なのです。記号の増分値をもっと大きな値に設定すると、圧縮率を大幅に向上させることができます。累積度数表の上限値を 0x4000 に設定して試してみたところ、結果は次のようになりました。
表 : 適応型レンジコーダ (order-1, order-2) の結果
order-1 サイズ +4 +8 +16 +32
-----------------------------------------------------------
alice29.txt 152,089 67,761 66,975 66,519 66,341
asyoulik.txt 125,179 56,308 55,534 55,139 55,007
cp.html 24,603 12,653 12,245 12,026 11,925
fields.c 11,150 5,562 5,243 5,022 4,887
grammar.lsp 3,721 2,049 1,911 1,819 1,762
kennedy.xls 1,029,744 330,033 321,961 317,377 323,931
lcet10.txt 426,754 190,112 188,598 187,646 187,234
plrabn12.txt 481,861 206,916 206,036 205,757 206,108
ptt5 513,216 55,658 54,920 54,534 54,521
sum 38,240 19,479 18,822 18,397 18,169
xargs.1 4,227 2,526 2,375 2,279 2,230
-----------------------------------------------------------
合計 2,810,784 949,057 934,620 926,515 932,115
order-2 サイズ +4 +16 +32 +64 +96
--------------------------------------------------------------------
alice29.txt 152,089 62,275 56,257 54,879 54,248 54,158
asyoulik.txt 125,179 54,392 48,569 47,202 46,564 46,476
cp.html 24,603 12,929 10,988 10,474 10,221 10,181
fields.c 11,150 5,892 4,745 4,374 4,134 4,045
grammar.lsp 3,721 2,283 1,880 1,739 1,645 1,611
kennedy.xls 1,029,744 229,549 213,430 208,621 202,963 199,177
lcet10.txt 426,754 164,719 154,175 151,767 150,656 150,634
plrabn12.txt 481,861 185,269 176,013 174,353 174,156 174,778
ptt5 513,216 62,522 59,423 59,167 59,792 60,621
sum 38,240 21,631 18,859 17,985 17,450 17,264
xargs.1 4,227 2,930 2,486 2,335 2,241 2,212
--------------------------------------------------------------------
合計 2,810,784 804,391 746,825 732,896 724,070 721,157
order-1, 2 の場合、増分値を増やすと圧縮率が大幅に向上しました。今回のテストでは、order-1 で +16 から +32 ぐらい、order-2 で +32 から +64 ぐらいの値で良い結果が得られるようです。もちろん、増分値の最適値は累積度数表の上限値やデータによって変わると思います。興味のある方は他のデータでも試してみてください。
もうひとつ、有限文脈モデルで圧縮率を向上させる有効な方法を紹介しましょう。高い圧縮率を実現しているデータ圧縮アルゴリズムに "PPM (Prediction by Partial Matching)" があります。PPM は 1984 年に J. G. Cleary 氏と I. H. Witten 氏によって提案されたアルゴリズムで、文脈から作られる統計的モデルによって次の文字の出現確率を予測する方法です。簡単にいえば「高次の有限文脈モデル」になりますが、PPM はまだ現れていない記号 (未出現記号) をエスケープ (escape) 記号とし、このエスケープ記号を使って符号化するところが特徴です。
もう少し具体的に説明しましょう。PPM の基本的な考え方はそれほど難しくありません。たとえば、有限文脈モデルの次数を 5 次 (order-5) としましょう。記号 a を符号化する場合、まず order-5 の出現頻度表を調べます。ここで、order-5 に記号 a が存在すれば、それを算術符号 (またはレンジコーダ) で符号化します。もし、記号 a が存在しない場合は、エスケープ記号を符号化して order-4 の出現頻度表を調べます。つまり、次数を下げながら記号 a が出現している文脈モデルを探すわけです。
PPM は高次の有限文脈モデルを操作するため、実際のプログラムはかなり複雑になります。いきなり PPM をプログラムするのは大変ですが、エスケープ記号というアイデアは PPM 以外の圧縮アルゴリズムにも用いることができそうです。そこで、有限文脈モデル (order-2) のプログラムにエスケープ記号を適用して、どのくらい効果があるか試してみましょう。
プログラムは簡単です。order-2 の出現頻度表で記号が見つからない場合は、その出現頻度表でエスケープ記号を符号化します。それから、order-0 の出現頻度表で記号を符号化します。つまり、有限文脈モデルは order-2 -> order-0 という 2 段階になります。今回は簡単なテストということで、order-2 -> order-1 -> order-0 という 3 段階のモデルにはしません。ご了承ください。
PPM の場合、エスケープ記号に与える出現確率をエスケープ確率と呼びます。そして、エスケープ確率の計算方法を Method と呼びます。Method にはいくつかの方式が提案されていますが、PPM では Method C や Method D が経験的に良い性能を持つと言われています。
Method C : u / (n + u) Method D : (u / 2) / n n : そのモデルで出現した記号の総数 u : そのモデルで出現したエスケープ記号の総数
適応型レンジコーダで符号化する場合、Method C はとても簡単に実現できます。まず、記号の出現頻度表は、エスケープ記号を 1 とし他の記号は 0 に初期化します。たとえば、記号 a を符号化する場合、表に記号 a がない（個数 0) 場合はエスケープ記号を符号化し、出現頻度表を更新します。このとき、記号 a とエスケープ記号の個数を増やせば、通常のレンジコーダで Method C を実現することができます。
つまり、記号 a を符号化したときは出現頻度表の a の個数を +1 して、エスケープ記号を符号化したときは記号 a とエスケープ記号の個数を +1 するのです。これでエスケープ記号の出現確率は u / (n + u) になるので、あとは通常のレンジコーダで符号化すればいいわけです。とても簡単ですね。
Method D は Method C の改良版です。Method C でエスケープ記号を符号化したとき、記号 a とエスケープ記号の個数を +1 ずつしましたが、これを 0.5 ずつにして合わせて +1 とするのが Method D です。Method C では、エスケープ記号の個数を +1 しているため、記号の出現確率よりもエスケープ確率の割合が増大する場合がありますが、Method D ではこれを補正することができます。
Method D を簡単に実現するには、記号 a を符号化するときに記号の個数を +2 すればいいでしょう。これでエスケープ記号の割合が増大するのを補正することができます。あとは通常の適応型レンジコーダで符号化すれば、Method D に相当する出現確率で符号化することができます。
それではプログラムを作りましょう。最初に出現頻度表を定義します。
リスト : 出現頻度表の定義
class FreqEsc:
def __init__(self, size, inc, limit):
self.size = size + 1
self.esc = size
self.inc = inc
self.limit = limit
self.count = [0] * self.size
self.count[self.esc] = 1
if self.size % GR == 0:
self.count_group = [0] * (self.size // GR)
else:
self.count_group = [0] * (self.size // GR + 1)
self.count_group[self.esc // GR] = 1
self.sum_ = 1
エスケープ記号を付け加えるので、クラス名は FreqEsc としました。引数 size は記号の種類です。この値にエスケープ記号は含まれません。したがって、出現頻度表の大きさを表すインスタンス変数 size の値は size + 1 で、エスケープ記号の値 esc は size になります。inc は記号の増分値で、limit は累積度数の上限値です。出現頻度表 count は 0 に初期化しておいて、count[esc] に 1 をセットします。
次は出現頻度表を更新するメソッド update() を作ります。
リスト : 出現頻度表の更新
def update(self, c0, c1):
self.count[c0] += self.inc
self.count[c1] += self.inc
self.count_group[c0 // GR] += self.inc
self.count_group[c1 // GR] += self.inc
self.sum_ += self.inc * 2
if self.sum_ >= self.limit:
n = 0
for x in range(len(self.count_group)):
self.count_group[x] = 0
for x in range(self.size):
if self.count[x] > 0:
self.count[x] = (self.count[x] >> 1) | 1
self.count_group[x // GR] += self.count[x]
n += self.count[x]
self.sum_ = n
エスケープ記号を符号化したあと、記号とエスケープ記号の出現頻度を更新します。エスケープ記号だけ更新すると、いつまでたっても他の記号を符号化することはできません。記号を符号化した場合は、引数 c0 と c1 には同じ記号を渡します。これで Method D に相当する出現確率になります。出現頻度の合計値 sum_ が limit 以上になったら、出現している記号の個数を半分にします。このとき、個数が 0 にならないように最下位ビットを 1 にしています。
なお、記号の増分値 inc に大きな値を設定すると、圧縮率が向上する場合があります。これはあとで試してみましょう。
次は記号の符号化を行うメソッド encode() を作ります。
リスト : 記号の符号化
def encode(self, rc, freq0, c):
if self.count[c] == 0:
c1 = self.esc
else:
c1 = c
temp = rc.range_ // self.sum_
rc.low += self.cumul(c1) * temp
rc.range_ = self.count[c1] * temp
rc.encode_normalize()
self.update(c, c1)
if c1 != c:
# freq0 で符号化
freq0.encode(rc, c)
引数 rc は RangeCoder のオブジェクト、freq0 は order-0 の出現頻度表、c は符号化する記号です。count[c] が 0 の場合、記号 c は出現していないのでエスケープ記号を符号化します。変数 c1 にエスケープ記号をセットします。
そうでなければ、c を c1 にセットして記号を符号化します。あとの処理は適応型レンジコーダの符号化処理と同じです。最後に、c1 と c が等しくない場合はエスケープ記号を符号化したので、order-0 の出現頻度表 freq0 で記号 c を符号化します。
次は復号を行うメソッド decode() を作ります。
リスト : 記号の復号
def decode(self, rc, freq0):
# 記号の探索
def search_code(value):
n = 0
for x in range(len(self.count_group)):
if value < n + self.count_group[x]: break
n += self.count_group[x]
for c in range(x*GR, self.size):
if value < n + self.count[c]: break
n += self.count[c]
return c, n
#
temp = rc.range_ // self.sum_
c, num = search_code(rc.low // temp)
rc.low -= temp * num
rc.range_ = temp * self.count[c]
rc.decode_normalize()
if c == self.esc:
c1 = freq0.decode(rc)
else:
c1 = c
self.update(c1, c)
return c1
記号の復号処理は適応型レンジコーダと同じです。復号した記号 c がエスケープ記号であれば、order-0 の出現頻度表 freq0 で記号 c1 を復号します。それから、update(c1, c) で出現頻度表を更新して記号 c1 を返します。
最後に符号化と復号を行う関数 encode() と decode() を作ります。
リスト : エスケープ記号付き有限文脈モデル
INC0 = 4
INC2 = 64
LIMIT = 0x4000
# 符号化
def encode(fin, fout):
rc = RangeCoder(fout, ENCODE)
freq0 = Freq(256, INC0, LIMIT)
freq = [[None] * 256 for _ in range(256)]
c00 = 0
c0 = 0
for x in read_file(fin):
if freq[c00][c0] is None:
freq[c00][c0] = FreqEsc(256, INC2, LIMIT)
freq[c00][c0].encode(rc, freq0, x)
c00 = c0
c0 = x
rc.finish()
# 復号
def decode(fin, fout, size):
freq0 = Freq(256, INC0, LIMIT)
freq = [[None] * 256 for _ in range(256)]
rc = RangeCoder(fin, DECODE)
c00 = 0
c0 = 0
for _ in range(size):
if freq[c00][c0] is None:
freq[c00][c0] = FreqEsc(256, INC2, LIMIT)
x = freq[c00][c0].decode(rc, freq0)
fout.putc(x)
c00 = c0
c0 = x
有限文脈モデル (order-2) のプログラムとの違いは、order-0 の出現頻度表を用意することと、order-2 の出現頻度表に FreqEsc を使うことだけです。order-0 の増分値は +4 に、order-2 の増分値 INC2 は +4 以上の値に設定します。累積度数の上限値 LIMIT は 0x4000 としました。
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。
表 : 有限文脈モデル + ESC 記号の結果
ファイル名 サイズ +16 +32 +64 LHA(lh5)
----------------------------------------------------------------
alice29.txt 152,089 52,023 51,988 52,132 59,117
asyoulik.txt 125,179 44,344 44,325 44,453 52,341
cp.html 24,603 8,597 8,585 8,573 8,384
fields.c 11,150 3,445 3,440 3,428 3,170
grammar.lsp 3,721 1,282 1,281 1,279 1,271
kennedy.xls 1,029,744 177,827 166,427 155,765 198,342
lcet10.txt 426,754 147,015 146,882 147,342 159,558
plrabn12.txt 481,861 170,081 170,544 172,006 210,045
ptt5 513,216 53,399 53,787 54,670 52,305
sum 38,240 15,165 15,128 15,062 13,993
xargs.1 4,227 1,763 1,763 1,763 1,778
----------------------------------------------------------------
合計 2,810,784 674,941 664,150 656,473 760,304
エスケープ記号の効果はとても大きいですね。INC2 は +32 程度でよさそうです。order-2 にエスケープ記号を適用しただけで、LHA を上回る圧縮率になるとは大変驚きました。PPM の圧縮率がなぜ高いのか、その理由が少しだけわかったような気がしました。
#
# freq.py : 適応型レンジコーダ用の出現頻度表
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
from rangecoder import *
# 定数
GR = 16
# 出現頻度表
class Freq:
def __init__(self, size, inc = 1, limit = MIN_RANGE):
self.size = size
self.inc = inc
self.limit = limit
self.count = [1] * size
if size % GR == 0:
self.count_group = [GR] * (size // GR)
else:
self.count_group = [GR] * (size // GR + 1)
self.sum_ = size
# 出現頻度表の更新
def update(self, c):
self.count[c] += self.inc
self.count_group[c // GR] += self.inc
self.sum_ += self.inc
if self.sum_ >= self.limit:
n = 0
for x in range(len(self.count_group)):
self.count_group[x] = 0
for x in range(self.size):
self.count[x] = (self.count[x] >> 1) | 1
self.count_group[x // GR] += self.count[x]
n += self.count[x]
self.sum_ = n
# 記号の累積度数を求める
def cumul(self, c):
n = 0
for x in range(c // GR): n += self.count_group[x]
for x in range((c // GR) * GR, c): n += self.count[x]
return n
# 符号化
def encode(self, rc, c):
temp = rc.range_ // self.sum_
rc.low += self.cumul(c) * temp
rc.range_ = self.count[c] * temp
rc.encode_normalize()
self.update(c)
# 復号
def decode(self, rc):
# 記号の探索
def search_code(value):
n = 0
for x in range(len(self.count_group)):
if value < n + self.count_group[x]: break
n += self.count_group[x]
for c in range(x*GR, self.size):
if value < n + self.count[c]: break
n += self.count[c]
return c, n
#
temp = rc.range_ // self.sum_
c, num = search_code(rc.low // temp)
rc.low -= temp * num
rc.range_ = temp * self.count[c]
rc.decode_normalize()
self.update(c)
return c
#
# rca0.py : 適応型レンジコーダ (order-0)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from freq import *
LIMIT = 0x4000
INC = 4
# ファイルの読み込み
def read_file(fin):
while True:
c = fin.getc()
if c is None: break
yield c
# order-0 の符号化
def encode(fin, fout):
rc = RangeCoder(fout, ENCODE)
freq = Freq(256, INC, LIMIT)
for x in read_file(fin):
freq.encode(rc, x)
rc.finish()
# order-0 の復号
def decode(fin, fout, size):
freq = Freq(256, INC, LIMIT)
rc = RangeCoder(fin, DECODE)
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='適応型RangeCoder(order-0)符号')
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))
#
# rca1.py : 適応型レンジコーダ (order-1)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from freq import *
LIMIT = 0x4000
INC = 16
# ファイルの読み込み
def read_file(fin):
while True:
c = fin.getc()
if c is None: break
yield c
# order-1 の符号化
def encode(fin, fout):
rc = RangeCoder(fout, ENCODE)
freq = [None] * 256
c0 = 0
for x in read_file(fin):
if freq[c0] is None: freq[c0] = Freq(256, INC, LIMIT)
freq[c0].encode(rc, x)
c0 = x
rc.finish()
# order-1 の復号
def decode(fin, fout, size):
rc = RangeCoder(fin, DECODE)
freq = [None] * 256
c0 = 0
for _ in range(size):
if freq[c0] is None: freq[c0] = Freq(256, INC, LIMIT)
x = freq[c0].decode(rc)
fout.putc(x)
c0 = x
# 符号化
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='適応型RangeCoder(order-1)符号')
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))
#
# rca2.py : 有限文脈モデル order-2
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from freq import *
LIMIT = 0x4000
INC = 64
# ファイルの読み込み
def read_file(fin):
while True:
c = fin.getc()
if c is None: break
yield c
# order-2 の符号化
def encode(fin, fout):
rc = RangeCoder(fout, ENCODE)
freq = [[None] * 256 for _ in range(256)]
c00 = 0
c0 = 0
for x in read_file(fin):
if freq[c00][c0] is None: freq[c00][c0] = Freq(256, INC, LIMIT)
freq[c00][c0].encode(rc, x)
c00 = c0
c0 = x
rc.finish()
# order-2 の復号
def decode(fin, fout, size):
freq = [[None] * 256 for _ in range(256)]
rc = RangeCoder(fin, DECODE)
c00 = 0
c0 = 0
for _ in range(size):
if freq[c00][c0] is None: freq[c00][c0] = Freq(256, INC, LIMIT)
x = freq[c00][c0].decode(rc)
fout.putc(x)
c00 = c0
c0 = x
# 符号化
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='適応型RangeCoder(order-2)符号')
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))
#
# rcae.py : 有限文脈モデル order-2 + Escape 記号
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from freq import *
INC0 = 4
INC2 = 64
LIMIT = 0x4000
# ESC 記号付き出現頻度表
class FreqEsc:
def __init__(self, size, inc, limit):
self.size = size + 1
self.esc = size
self.inc = inc
self.limit = limit
self.count = [0] * self.size
self.count[self.esc] = 1
if self.size % GR == 0:
self.count_group = [0] * (self.size // GR)
else:
self.count_group = [0] * (self.size // GR + 1)
self.count_group[self.esc // GR] = 1
self.sum_ = 1
# 出現頻度表の更新
def update(self, c0, c1):
self.count[c0] += self.inc
self.count[c1] += self.inc
self.count_group[c0 // GR] += self.inc
self.count_group[c1 // GR] += self.inc
self.sum_ += self.inc * 2
if self.sum_ >= self.limit:
n = 0
for x in range(len(self.count_group)):
self.count_group[x] = 0
for x in range(self.size):
if self.count[x] > 0:
self.count[x] = (self.count[x] >> 1) | 1
self.count_group[x // GR] += self.count[x]
n += self.count[x]
self.sum_ = n
# 記号の累積度数を求める
def cumul(self, c):
n = 0
for x in range(c // GR): n += self.count_group[x]
for x in range((c // GR) * GR, c): n += self.count[x]
return n
# 符号化
def encode(self, rc, freq0, c):
if self.count[c] == 0:
c1 = self.esc
else:
c1 = c
temp = rc.range_ // self.sum_
rc.low += self.cumul(c1) * temp
rc.range_ = self.count[c1] * temp
rc.encode_normalize()
self.update(c, c1)
if c1 != c:
# freq0 で符号化
freq0.encode(rc, c)
# 復号
def decode(self, rc, freq0):
# 記号の探索
def search_code(value):
n = 0
for x in range(len(self.count_group)):
if value < n + self.count_group[x]: break
n += self.count_group[x]
for c in range(x*GR, self.size):
if value < n + self.count[c]: break
n += self.count[c]
return c, n
#
temp = rc.range_ // self.sum_
c, num = search_code(rc.low // temp)
rc.low -= temp * num
rc.range_ = temp * self.count[c]
rc.decode_normalize()
if c == self.esc:
c1 = freq0.decode(rc)
else:
c1 = c
self.update(c1, c)
return c1
# ファイルの読み込み
def read_file(fin):
while True:
c = fin.getc()
if c is None: break
yield c
# 符号化
def encode(fin, fout):
rc = RangeCoder(fout, ENCODE)
freq0 = Freq(256, INC0, LIMIT)
freq = [[None] * 256 for _ in range(256)]
c00 = 0
c0 = 0
for x in read_file(fin):
if freq[c00][c0] is None:
freq[c00][c0] = FreqEsc(256, INC2, LIMIT)
freq[c00][c0].encode(rc, freq0, x)
c00 = c0
c0 = x
rc.finish()
# 復号
def decode(fin, fout, size):
freq0 = Freq(256, INC0, LIMIT)
freq = [[None] * 256 for _ in range(256)]
rc = RangeCoder(fin, DECODE)
c00 = 0
c0 = 0
for _ in range(size):
if freq[c00][c0] is None:
freq[c00][c0] = FreqEsc(256, INC2, LIMIT)
x = freq[c00][c0].decode(rc, freq0)
fout.putc(x)
c00 = c0
c0 = x
# 符号化
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='適応型RangeCoder(order-2+ESC)符号')
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))