M.Hiroi's Home Page

Algorithms with Python

有限文脈モデル

[ PrevPage | Python | NextPage ]

はじめに

今回は「有限文脈モデル」について説明します。有限文脈モデルは、適応型レンジコーダを用いると簡単に実現することができます。

●マルコフ情報源モデル

シャノン・ファノ符号とハフマン符号 で説明した「無記憶情報源モデル」は、もっとも簡単な情報源モデルです。このモデルは、記号を生成するとき以前に生成した記号との間に関係がないため「無記憶」と呼ばれますが、このモデルを一般化して状態 (記憶) を持つモデルを考えることができます。参考文献 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 の圧縮率がなぜ高いのか、その理由が少しだけわかったような気がしました。

●参考文献

  1. 植松友彦, 『文書データ圧縮アルゴリズム入門』, CQ出版社, 1994
  2. 広井誠, 『高性能圧縮ツール bsrc の理論と実装 (後編)』, Interface 2004 年 1 月号, CQ出版社
  3. 広井誠, 『PPM によるファイルの圧縮 (前編)』, Interface 2005 年 3 月号, CQ出版社
  4. 広井誠, 『PPM によるファイルの圧縮 (後編)』, Interface 2005 年 4 月号, CQ出版社

●プログラムリスト1

#
# 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

●プログラムリスト2

#
# 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))

●プログラムリスト3

#
# 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))

初版 2007 年 6 月 16 日
改訂 2022 年 9 月 23 日

Copyright (C) 2007-2022 Makoto Hiroi
All rights reserved.

[ PrevPage | Python | NextPage ]