M.Hiroi's Home Page

Algorithms with Python

ブロックソート (BlockSorting) [2]

[ PrevPage | Python | NextPage ]

はじめに

前回説明したように、ブロックソートしたあとのデータは同じ記号が多数並びます。このデータを MTF (Move To Front) 法で符号化することにより、データ全体の中で記号 0 の割合が著しく増加し、記号の出現頻度を偏らせることができます。このあと、適応型レンジコーダで圧縮するだけでも高い圧縮率を達成することできますが、ここで連長圧縮 (ランレングス) を適用する、またはブロックソートに適した情報源モデルを作成すると、圧縮率をさらに改善できる場合があります。最初にランレングスから説明します。

●ブロックソートとランレングス

ランレングスは拙作のページ 連長圧縮 で詳しく説明しました。この中で説明した単純なランレングス (RLE), PackBits, Switched Run Length Encoding は、ブロックソートに適用しても効果はほとんどありません。本当にランレングスには効果があるのか疑問に思ったのですが、Google で圧縮関連のページを調べたり、いろいろと試行錯誤してみたところ、簡単で効果的な方法が 2 つありました。

ひとつは、「記号 0 だけをランレングスで符号化する」という方法です。これを「ゼロランレングス」と呼びます。この方法では、記号 0 をランレングスの開始記号にすることができるので、「0 + データの個数」のように 2 バイトで符号化することができます。MTF 法で変換したデータは 0 の個数が極めて多くなるので、0 だけをランレングスで符号化した方がより効果的なのでしょう。

もうひとつは、「同じ記号が数個以上続いていたらランレングスで符号化する」という方法です。たとえば、同じ記号が 3 つ以上続いていたら符号化することにしましょう。すると、データが "aaaaa" の場合は [a, a, a, 2] と表すことができます。逆に、"aaa" は [a, a, a, 0] と符号化されるので、1 バイト増えることになります。ですが、連続していない記号をランレングスで符号化することはないので、単純なランレングスよりもデータが膨らむ危険性は小さくなるはずです。そして、記号 0 は長く連なっている場合が多いので、ランレングスで符号化されるわけです。

どちらの方法でも効果はあるのですが、その中で特に優れている方法に Zero Length Encoding (ZLE) があります。ZLE はゼロランレングスの一種で、MTF 法で変換したあとに適用すると大きな効果を発揮します。ZLE の詳しい説明は拙作のページ 連長圧縮 をお読みください。

●プログラムの作成

それでは、ブロックソート + MTF 法のあとに Zero Length Encoding (ZLE) を適用してみましょう。符号化のプログラムは次のようになります。

リスト : ブロックソートの符号化

def bs_encode(fin, fout, size):
    # 入力
    buff = array('B')
    buff.fromfile(fin, size)
    buff *= 2
    # BlockSorting
    work, top = suffix_sort(buff, size)
    # Move To Front
    mtf2_encode(work)
    # Run Length Encoding
    r_size = zle_encode(work, buff)
    write_number(top, fout)
    write_number(r_size, fout)
    # RangeCoder
    rc = RangeCoder(fout, ENCODE)
    freq = Freq(256, INC, LIMIT)
    for x in range(r_size):
        freq.encode(rc, buff[x])
    rc.finish()

関数 zle_encode() はデータを ZLE で符号化します。入力データは work で、出力バッファに buff を指定します。ランレングスで符号化する場合、データが伸張する危険性があります。今回のプログラムではデータの伸張をチェックしていませんが、実際に圧縮ツールを作成する場合、データが伸張したらランレングスを不適用にするといった工夫が必要になるでしょう。

zle_encode() の返り値は符号化したあとのデータ数です。これを変数 r_size にセットします。そして、r_size を出力ファイルに書き込んでから、buff のデータを適応型レンジコーダで符号化します。

復号のプログラムは次のようになります。

リスト : ブロックソートの復号

def bs_decode(fin, fout, size):
    top = read_number(fin)
    r_size = read_number(fin)
    # RangeCoder
    work = array('B')
    rc = RangeCoder(fin, DECODE)
    freq = Freq(256, INC, LIMIT)
    for _ in range(r_size):
        work.append(freq.decode(rc))
    # Run Length Encoding
    buff = array('B')
    for _ in range(size): buff.append(0)
    zle_decode(work, buff)
    # Move To Front
    mtf2_decode(buff)
    # BlockSorting
    idx = array('I')
    for _ in range(size): idx.append(0)
    # 分布数えソート
    count = [0] * 256
    for x in range(size): count[ buff[x] ] += 1
    for x in range(1, 256): count[x] += count[x - 1]
    for x in range(size - 1, -1, -1):
        c = buff[x]
        count[c] -= 1
        idx[ count[c] ] = x
    # 出力
    x = idx[top]
    for _ in range(size):
        fout.putc(buff[x])
        x = idx[x]

read_number() で入力ファイルからデータ数を読み込んで r_size にセットします。次に、適応型レンジコーダで r_size 個の記号を復号してバッファ work にセットします。それから、関数 zle_decode() で ZLE の復号を行います。入力データが work で、出力バッファが buff です。buff の大きさは size になります。そして、MTF 法とブロックソートの復号を行います。

あとは特に難しいところはないでしょう。説明は割愛いたしますので、詳細は プログラムリスト1 をお読みください。

●評価結果

それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。

            表 : ブロックソートの結果
    (BlockSorting + MTF-2 + ZLE + RangeCoder)

ファイル名      サイズ   Range    bzip2    符号化  復号
---------------------------------------------------------
alice29.txt    152,089   43,513   43,202   0.868   0.504
asyoulik.txt   125,179   40,027   39,569   0.847   0.494
cp.html         24,603    7,760    7,624   0.207   0.081
fields.c        11,150    3,120    3,039   0.136   0.038
grammar.lsp      3,721    1,264    1,283   0.076   0.018
kennedy.xls  1,029,744  138,023  130,280   5.562   2.509
lcet10.txt     426,754  107,989  107,706   2.334   1.354
plrabn12.txt   481,861  145,671  145,577   2.688   1.714
ptt5           513,216   48,366   49,759   1.466   0.890
sum             38,240   13,060   12,909   0.422   0.126
xargs.1          4,227    1,740    1,762   0.077   0.021
---------------------------------------------------------
合計         2,810,784  550,533  542,710  14.683   7.749

符号化と復号の単位 : 秒
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

結果を見ればおわかりのように、前回よりも圧縮率は大幅に向上しています。ZLE の効果はとても高いことがわかります。実行速度もバイナリレンジコーダより高速です。それにしても、簡単な方法の組み合わせで bzip2 にせまる圧縮率を達成できるのですから、ブロックソートは本当に優れた方法だと思います。ここで、ブロックソート向きの「情報源モデル」を作成すると、さらに圧縮率を向上させることができます。

なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。

●情報源モデルの改良

ブロックソートの場合、MTF 法で変換することにより記号 0 がとても多くなるため、無記憶情報源モデルの適応型レンジコーダでも効率よく圧縮することができました。ですが、ブロックソート + MTF 法の特徴はそれだけではありません。1 や 2 などの小さな記号も多くなり、逆に 0xfe や 0xff などの大きな記号はとても少なくなります。つまり、記号が大きくなるにしたがって個数が減少していく反比例の関係になります。

このあと、Zero Length Encoding を適用すると 0 と 1 の個数は減少しますが、それでも記号 0 の個数は多くて、反比例の関係に大きな変化はないと考えられます。実際に、The Canterbury Corpus の alice29.txt を MTF-2 で変換した場合と、そのあと ZLE で圧縮した場合で、各記号の個数をカウントしてみました。記号 0 から 9 までの個数は次のようになりました。

 表 : 記号の個数 (alice29.txt)

MTF-2 のみ    MTF-2 -> ZLE
----------   --------------
 0: 85986     0: 20407
 1: 21296     1: 10616
 2:  9782     2: 21296
 3:  6498     3:  9782
 4:  4612     4:  6498
 5:  3572     5:  4612
 6:  3024     6:  3572
 7:  2530     7:  3024
 8:  2165     8:  2530
 9:  1785     9:  2165

ZLE により 0 と 1 の個数は大幅に減少しましたが、それでも記号 0, 1, 2 の個数はとても多く、そのあとの記号と個数は反比例の関係になっています。もしも、このような関係に適した情報源モデルを作成できれば、ブロックソートの圧縮率を改善することができるはずです。

●structured model

そこで、バイナリレンジコーダの「γモデル」で用いた sturctured model を多値レンジコーダにも適用してみましょう。次の図を見てください。

最初のポイントは、上図のように記号をグループに分けるところです。Group 0 は記号 0 だけですが、Group 1 は 1 と 2 で、Group 2 は 3, 4, 5, 6 というように、グループに割り当てる記号の個数を増やしていきます。

次に、記号を Group 番号 (first code) と Group 内の番号 (second code) の 2 つに分けて符号化します。つまり、first code (0 - 8) をレンジコーダで符号化し、それから second code を符号化するのです。これが第 2 のポイントです。

そして最後のポイントが、second code を符号化するときに first code によって記号の出現頻度表を切り替えるところです。このようなモデルを structured model と呼びます。

Group 0 は記号 0 を表すので second code は必要ありません。その分だけ記号 0 は効率よく符号化することができます。second code の場合でも、小さな記号の出現確率は高く、大きな記号になるほど出現確率は小さくなるので、ブロックソートに適した情報源モデルといえるでしょう。

●プログラムの作成

プログラムは次のようになります。

リスト : structured model

# 定数
LIMIT1 = 0x100
LIMIT2 = 0x200
LIMIT3 = 0x800

# structured model
class Freq1:
    def __init__(self, size):
        n2 = size >> 1
        n1 = 0
        while n2 > 0:
            n1 += 1
            n2 >>= 1
        self.size = n1
        self.context1 = Freq(n1 + 1, 4, LIMIT2)
        self.context2 = [None] * (n1 + 1)
        for x in range(1, n1 + 1):
            self.context2[x] = Freq(2 ** x, 4, LIMIT3)

クラス名は Freq1 としました。メソッド __init__() の引数 size は記号の種類を表します。最初に、Group 番号 (first code) の最大値を n1 に求めます。たとえば、n1 が 8 であれば、first code は 0 から 8 までになります。インスタンス変数 context1 に first code 用の出現頻度表をセットします。そして、context2 に second code 用の出現頻度表をセットします。

structured model の場合、累積度数の上限値と記号の増分値により、圧縮率が少し変化することに注意してください。今回はテストプログラムということで、増分値は +4 で固定しますが、累積度数の上限値は first code と second code で変更します。first code は LIMIT2 (0x200) とし、second code は LIMIT3 (0x800) としました。興味のある方はいろいろ試してみてください。

次は符号化と復号を行うメソッドを作ります。

リスト : structured model の符号化と復号

    # 符号化
    def encode(self, rc, c):
        n1 = 0
        n2 = (c + 1) >> 1
        while n2 > 0:
            n1 += 1
            n2 >>= 1
        self.context1.encode(rc, n1)
        if n1 > 0:
            self.context2[n1].encode(rc, (c + 1) & ((2 ** n1) - 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

メソッド encode のポイントは、記号 c を first code と second code に分けて符号化するところです。最初に記号 c を first code (n1) に変換し、context1 の出現頻度表で符号化します。n1 が 0 よりも大きい場合は second code を符号化します。second code は c + 1 の下位 n1 ビットで、用いる出現頻度表は context2[n1] になります。

メソッド decode は encode と同様に、まず first code を復号し、それが 0 よりも大きければ second code を復号します。このとき、first code と second code から記号 n1 を復号することに注意してください。出現頻度表を切り替える処理は encode とまったく同じです。

●評価結果

それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。

            表 : ブロックソートの結果
    (BlockSorting + MTF-2 + ZLE + structured model)

ファイル名      サイズ  s-model   bzip2    符号化  復号
---------------------------------------------------------
alice29.txt    152,089   42,309   43,202   1.025   0.672
asyoulik.txt   125,179   38,979   39,569   0.876   0.587
cp.html         24,603    7,612    7,624   0.219   0.113
fields.c        11,150    3,045    3,039   0.132   0.052
grammar.lsp      3,721    1,226    1,283   0.099   0.022
kennedy.xls  1,029,744  122,323  130,280   5.734   2.879
lcet10.txt     426,754  105,293  107,706   2.713   1.733
plrabn12.txt   481,861  142,271  145,577   3.271   2.222
ptt5           513,216   48,051   49,759   1.665   1.083
sum             38,240   12,638   12,909   0.423   0.165
xargs.1          4,227    1,698    1,762   0.094   0.028
---------------------------------------------------------
合計         2,810,784  525,445  542,710  16.251   9.556

符号化と復号の単位 : 秒
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

結果を見ればおわかりのように、structured model は多値レンジコーダよりも圧縮率が向上しています。そして、bzip2 を上回る圧縮率になりました。structured model の効果は十分に出ていると思います。

なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。

ところで、ブロックソートに適した情報源モデルは structured model だけではありません。ほかにも優れたモデルがあります。次は、有限文脈モデルを用いた "0-1-2 coding" というモデルを紹介します。

●0-1-2 coding

0-1-2 coding は難しい方法ではありません。名前が示すように記号 0, 1, 2 を符号化する方法です。このとき、2 以上の記号は 2 に変換して符号化するところがポイントです。つまり、記号を 0, 1, 2 の 3 つに分けて符号化するのです。

ブロックソートのあと MTF 法で変換すると、記号 0 と 1 の個数はとても多くなります。記号を 0, 1, 2 の 3 種類に限定すれば、高次の有限文脈モデルを適用することにより、圧縮率は極めて高くなります。あとは、残りの記号を適切な情報源モデルで符号化することにより、トータルで高い圧縮率を達成しようというのが 0-1-2 coding の目的です。

0-1-2 coding の符号化のアルゴリズムは次のようになります。

リスト : 0-1-2 coding の符号化(疑似コード)

符号化(記号 c):
    c1 = c が 2 以上であれば 2 に変換する
    直前の N 文字から N 次モデルの出現頻度表 freq を求める
    記号 c1 をレンジコーダで符号化
    freq を更新する
    直前の文字を更新する
    if c >= 2:
        # 2 以上の記号の符号化 (structured model)
        c2 = c - 2
        c21 = 記号 c2 の first code を求める
        記号 c21 をレンジコーダで符号化
        出現頻度表を更新する
        if c21 > 0:
            c22 = 記号 c2 の second code を求める
            記号 c22 をレンジコーダで符号化
            出現頻度表を更新する

0-1-2 coding は記号 c1 (0, 1, 2) を N 次の有限文脈モデルで符号化し、記号 c が 2 以上の場合は記号 c2 (= c - 2) を適切な情報源モデル(たとえば structured model など) で符号化します。とても簡単ですね。復号も簡単で、まず記号 c1 を復号して値が 2 であれば、記号 c2 を復号して元の記号を求めるだけです。有限文脈モデルの次数ですが、試してみたところ order-3 で十分なようです。

このように、0-1-2 coding は記号 0, 1, 2 に高次の有限文脈モデルを適用することで圧縮率を向上させる方法です。このため、ランレングスとは相性があまりよくありません。特に、Zero Length Encoding の場合、0-1-2 coding ではほとんど効果がありません。

逆にいえば、ランレングスを適用しなくても、高い圧縮率を達成できる方法が 0-1-2 coding なのです。もっとも、データによってはランレングスが有効な場合もあります。これはあとで試してみましょう。

●プログラムの作成

それではプログラムを作りましょう。次のリストを見てください。

リスト : 0-1-2 coding

class Freq012:
    def __init__(self, size):
        self.context1 = [Freq(3, 4, LIMIT1) for _ in range(27)]
        self.context2 = Freq1(size - 2)
        self.c0 = self.c1 = self.c2 = 0

    # 符号化
    def encode(self, rc, c):
        freq = self.context1[self.c2 * 9 + self.c1 * 3 + self.c0]
        self.c2 = self.c1
        self.c1 = self.c0
        if c < 2:
            freq.encode(rc, c)
            self.c0 = c
        else:
            freq.encode(rc, 2)
            self.c0 = 2
            self.context2.encode(rc, c - 2)

    # 復号
    def decode(self, rc):
        freq = self.context1[self.c2 * 9 + self.c1 * 3 + self.c0]
        self.c2 = self.c1
        self.c1 = self.c0
        c = freq.decode(rc)
        self.c0 = c
        if c >= 2:
            c = self.context2.decode(rc)
            c += 2
        return c

クラス名は Freq012 としました。インスタンス変数 context1 には order-3 の出現頻度表をセットします。3 種類の記号で order-3 の有限文脈モデルを構成するので、出現頻度表の個数は 27 になります。累積度数の上限値は LIMIT1 (0x100) としました。context2 には sutructured model の出現頻度表をセットします。直前の 3 記号は c0, c1, c2 に格納します。すると、出現頻度表の選択は context1[c2 * 9 + c1 * 3 + c0] になります。

符号化を行うメソッド encode は、context1 から出現頻度表を選んで記号 (0, 1, 2) を符号化します。記号 c が 2 以上であれば、structured model で c - 2 を符号化します。復号を行うメソッド decode は、context1 から出現頻度表を選んで記号 c を復号します。c が 2 の場合は、structured model で記号 c を復号して、c + 2 を返します。

●評価結果

それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。

            表 : ブロックソートの結果
       (BlockSorting + MTF-2 + 0-1-2 coding)

ファイル名      サイズ   0-1-2    bzip2    符号化  復号
---------------------------------------------------------
alice29.txt    152,089   42,041   43,202   1.184   0.764
asyoulik.txt   125,179   38,796   39,569   0.996   0.741
cp.html         24,603    7,474    7,624   0.238   0.160
fields.c        11,150    2,925    3,039   0.133   0.059
grammar.lsp      3,721    1,200    1,283   0.088   0.026
kennedy.xls  1,029,744  108,395  130,280   7.236   4.744
lcet10.txt     426,754  104,533  107,706   3.103   2.098
plrabn12.txt   481,861  141,789  145,577   3.618   2.609
ptt5           513,216   47,834   49,759   2.460   1.979
sum             38,240   12,274   12,909   0.464   0.206
xargs.1          4,227    1,665    1,762   0.088   0.034
---------------------------------------------------------
合計         2,810,784  508,890  542,710  19.608  13.420

符号化と復号の単位 : 秒
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

0-1-2 coding の圧縮率は structured model だけの場合よりも高くなります。0-1-2 coding はランレングス (ZLE) を適用しなくても高い圧縮率を達成できることがわかります。0-1-2 coding はブロックソートに適した優れた情報源モデルだと思います。そのかわり、実行時間はかなり遅くなります。それでもバイナリレンジコーダよりは高速です。

ところで、0-1-2 coding とランレングスを組み合わせることもできます。この場合、2 以上の記号に対して、同じ記号が 7 個以上続いたときにランレングスで符号化します。ランレングスのプログラムは プログラムリスト1 の rle.py (rle_encode2, rle_decode2) をお読みください。

結果は次のようになりました。

            表 : ブロックソートの結果
     (BlockSorting + MTF-2 + RLE-2 + 0-1-2 coding)

ファイル名      サイズ   0-1-2    bzip2    符号化  復号
---------------------------------------------------------
alice29.txt    152,089   42,045   43,202   1.152   0.811
asyoulik.txt   125,179   38,801   39,569   1.006   0.746
cp.html         24,603    7,478    7,624   0.238   0.142
fields.c        11,150    2,929    3,039   0.137   0.066
grammar.lsp      3,721    1,204    1,283   0.090   0.026
kennedy.xls  1,029,744   89,401  130,280   6.911   4.410
lcet10.txt     426,754  104,537  107,706   3.184   2.312
plrabn12.txt   481,861  141,793  145,577   3.758   2.798
ptt5           513,216   47,838   49,759   2.648   2.241
sum             38,240   12,273   12,909   0.482   0.223
xargs.1          4,227    1,664    1,762   0.095   0.031
---------------------------------------------------------
合計         2,810,784  489,963  542,710  19.701  13.806

符号化と復号の単位 : 秒
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

ランレングスのデータ数 (4 バイト) をファイルに付加しているので、ほとんどのファイルで 4 バイト増加していますが、バイナリファイル (kennedy.xls, sum) では効果があるようです。特に、kennedy.xls の圧縮率は大幅に向上しました。ファイルによっては、ランレングスにも効果があるようです。

なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。

●混合法

次は 0-1-2 coding に混合法を適用してみましょう。拙作のページ バイナリレンジコーダ [3] で簡単に説明しましたが、混合法は複数のモデルを混ぜ合わせて得られる出現確率を使って記号を符号化する方法です。

バイナリレンジコーダの場合、コンテキストに混合法を適用して圧縮率を改善することができました。混合法はコンテキストだけではなく、ほかのモデルにも適用することができます。実際に 0-1-2 coding に混合法を適用してみたところ、圧縮率を改善することができました。混合するモデルの次数と記号数の増分値を示します。

0-1-2 coding                  : order-4 (INC +2), order-1 (INC +14)
structured model (first code) : order-2 (INC +4), order-0 (INC +12)

0-1-2 coding の場合、order-3 と order-0 を混合するよりも、order-4 と order-1 を混合した方が少しだけ圧縮率が良くなりました。そして、0-1-2 coding だけではなく、structured model の first code に混合法を適用することで、圧縮率はさらに向上します。structured model の場合、first code に高次の有限文脈モデルを適用しても効果はほとんど無かったのですが、order-2 と order-0 を混合してみたところ圧縮率を改善することができました。

●プログラムの作成

それではプログラムを作りましょう。最初に、2 つの出現頻度表を混合して記号を符号化・復号する関数を作ります。次のリストを見てください。

リスト : 混合法

# 符号化
def _encode(rc, freq1, freq2, c):
    def cumul():
        n = 0
        for x in range(c):
            n += freq1.count[x] + freq2.count[x]
        return n
    #
    temp = rc.range_ // (freq1.sum_ + freq2.sum_)
    rc.low += cumul() * temp
    rc.range_ = (freq1.count[c] + freq2.count[c]) * temp
    rc.encode_normalize()
    freq1.update(c)
    freq2.update(c)

# 復号
def _decode(rc, freq1, freq2):
    def search_code(value):
        n = 0
        for c in range(freq1.size):
            m = freq1.count[c] + freq2.count[c]
            if value < n + m: break
            n += m
        return c, n
    #
    temp = rc.range_ // (freq1.sum_ + freq2.sum_)
    c, num = search_code(rc.low // temp)
    rc.low -= temp * num
    rc.range_ = temp * (freq1.count[c] + freq2.count[c])
    rc.decode_normalize()
    freq1.update(c)
    freq2.update(c)
    return c

関数 _encode() と _decode() は二つの出現頻度表 freq1 と freq2 の count を加算して、記号を符号化・復号します。そのあと、メソッド update で二つの出現頻度表 freq1 と freq2 を更新します。

次は structured model に混合法を適用しましょう。プログラムは次のようになります。

リスト : structured model の混合法

class Freq1m:
    def __init__(self, size):
        n2 = size >> 1
        n1 = 0
        while n2 > 0:
            n1 += 1
            n2 >>= 1
        n1 += 1
        self.size = n1
        self.c0 = self.c1 = 0
        self.context1 = [Freq(n1, 4, LIMIT2) for _ in range(n1 * n1)]  # order-2
        self.context2 = Freq(n1, 12, LIMIT2)
        self.context3 = [None] * n1
        for x in range(1, n1):
            self.context3[x] = Freq(2 ** x, 4, LIMIT3)

    # 符号化
    def encode(self, rc, c):
        n1 = 0
        n2 = (c + 1) >> 1
        while n2 > 0:
            n1 += 1
            n2 >>= 1
        freq1 = self.context1[self.c1 * self.size + self.c0]
        freq2 = self.context2
        _encode(rc, freq1, freq2, n1)
        self.c1 = self.c0
        self.c0 = n1
        if n1 > 0:
            self.context3[n1].encode(rc, (c + 1) & ((2 ** n1) - 1))

    # 復号
    def decode(self, rc):
        freq1 = self.context1[self.c1 * self.size + self.c0]
        freq2 = self.context2
        n1 = _decode(rc, freq1, freq2)
        self.c1 = self.c0
        self.c0 = n1
        if n1 > 0:
            n2 = self.context3[n1].decode(rc)
            n1 = (1 << n1) + n2 - 1
        return n1

クラス名は freq1m としました。インスタンス変数 context1 には first code の高次モデル (order-2) を、context2 には低次モデル (order-0) を格納します。context3 には second code の出現頻度表を格納します。first code の種類が n1 個とすると、context1 の大きさは n1 * n1 になります。n1 はインスタンス変数 size に格納します。高次モデルは order-2 なので、直前の 2 記号をインスタンス変数 c0, c1 に格納します。

メソッド encode() と decode() は、context1[c1 * size + c0] と context2 の出現頻度表を混合して、記号を符号化・復号します。この処理は関数 _encode(), _decode() を呼び出すだけなので簡単です。first code が 0 よりも大きい場合は、context3 の出現頻度表を使って second code を符号化・復号します。

次は 0-1-2 coding に混合法を適用します。次のリストを見てください。

リスト : 0-1-2 coding の混合法

class Freq012m:
    def __init__(self, size):
        self.context1 = [Freq(3, 2, LIMIT1) for _ in range(81)]  # order-4
        self.context2 = [Freq(3, 14, LIMIT1) for _ in range(3)]  # order-1
        self.context3 = Freq1m(size - 2)
        self.c0 = self.c1 = self.c2 = self.c3 = 0

    # 符号化
    def encode(self, rc, c):
        freq1 = self.context1[self.c3 * 27 + self.c2 * 9 + self.c1 * 3 + self.c0]
        freq2 = self.context2[self.c0]
        self.c3 = self.c2
        self.c2 = self.c1
        self.c1 = self.c0
        if c < 2:
            _encode(rc, freq1, freq2, c)
            self.c0 = c
        else:
            _encode(rc, freq1, freq2, 2)
            self.c0 = 2
            self.context3.encode(rc, c - 2)

    # 復号
    def decode(self, rc):
        freq1 = self.context1[self.c3 * 27 + self.c2 * 9 + self.c1 * 3 + self.c0]
        freq2 = self.context2[self.c0]
        self.c3 = self.c2
        self.c2 = self.c1
        self.c1 = self.c0
        c = _decode(rc, freq1, freq2)
        self.c0 = c
        if c >= 2:
            c = self.context3.decode(rc) + 2
        return c

クラス名は freq012m としました。インスタンス変数 context1 に高次モデル (order-4) を、context2 に低次モデル (order-1) を格納します。そして、context3 に Freq1m のオブジェクトをセットします。高次モデルは order-4 なので、直前の 4 記号をインスタンス変数 c0, c1, c2, c3 に格納します。

あとは、メソッド encode() と decode() で、高次モデルの出現頻度表 freq1 と低次モデルの出現頻度表 freq2 を選択し、関数 _encode(), _decode() を呼び出して記号を符号化・復号するだけです。記号が 2 以上の場合は、context3 の structured model (混合法) を使って、記号を符号化・復号します。

●評価結果

それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。

            表 : ブロックソートの結果
     (BlockSorting + MTF-2 + 0-1-2 coding:混合法)

ファイル名      サイズ   0-1-2    bzip2    符号化  復号
---------------------------------------------------------
alice29.txt    152,089   41,452   43,202   1.386   0.970
asyoulik.txt   125,179   38,327   39,569   1.168   0.871
cp.html         24,603    7,396    7,624   0.280   0.164
fields.c        11,150    2,912    3,039   0.153   0.067
grammar.lsp      3,721    1,185    1,283   0.092   0.030
kennedy.xls  1,029,744  107,085  130,280   8.417   5.794
lcet10.txt     426,754  103,146  107,706   3.680   2.558
plrabn12.txt   481,861  140,002  145,577   4.289   3.228
ptt5           513,216   47,481   49,759   2.989   2.432
sum             38,240   12,109   12,909   0.513   0.251
xargs.1          4,227    1,654    1,762   0.096   0.041
---------------------------------------------------------
合計         2,810,784  502,749  542,710  23.063  16.406

符号化と復号の単位 : 秒
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

混合法を適用したことにより、圧縮率は 0-1-2 coding よりも少し高くなりました。混合法の効果は十分に出ていると思います。実行時間は 2 つの出現頻度表を混合する分だけ 0-1-2 coding よりも遅くなります。2 以上の記号にランレングスを適用すると、kennedy.xls の圧縮率はもっと高くなります。興味のある方は試してみてください。

なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。

●参考文献

  1. 広井誠, 『高性能圧縮ツール bsrc の理論と実装 (前編, 後編)』, Interface 2003 年 12 月号, 2004 年 1 月号, CQ出版社
  2. 広井誠, 『高性能圧縮ツール bsrc の改良 bsrc2 (前編, 後編)』, Interface 2004 年 10 月号, 11 月号, CQ出版社

●プログラムリスト1

#
# rle.py : Run Length Encoding
#
#          Copyright (C) 2007-2022 Makoto Hiroi
#

# 定数
MAX_LEN = 255

##### Run Length Encoding #####

# ランレングス符号化
def rle_encode(buff1, buff2, n):
    size = len(buff1)
    i = 0
    j = 0
    while i < size:
        c = buff1[i]
        i += 1
        k = 1
        while i < size and k < MAX_LEN + n:
            if buff1[i] != c: break
            k += 1
            i += 1
        if k >= n:
            for _ in range(n):
                buff2[j] = c
                j += 1
            k -= n
            buff2[j] = k
            j += 1
        else:
            for _ in range(k):
                buff2[j] = c
                j += 1
    return j

# ランレングス復号
def rle_decode(buff1, buff2, n):
    size = len(buff1)
    i = 0
    j = 0
    while i < size:
        c = buff1[i]
        i += 1
        k = 1
        while i < size and k < n:
            if buff1[i] != c: break
            i += 1
            k += 1
        if k == n:
            k += buff1[i]
            i += 1
        for _ in range(k):
            buff2[j] = c
            j += 1
    return j


##### 2 以上の記号を符号化 #####

# ランレングス符号化
def rle_encode2(buff1, buff2, n):
    size = len(buff1)
    i = 0
    j = 0
    while i < size:
        c = buff1[i]
        i += 1
        if c < 2:
            buff2[j] = c
            j += 1
            continue
        k = 1
        while i < size and k < MAX_LEN + n:
            if buff1[i] != c: break
            k += 1
            i += 1
        if k >= n:
            for _ in range(n):
                buff2[j] = c
                j += 1
            k -= n
            buff2[j] = k
            j += 1
        else:
            for _ in range(k):
                buff2[j] = c
                j += 1
    return j

# ランレングス復号
def rle_decode2(buff1, buff2, n):
    size = len(buff1)
    i = 0
    j = 0
    while i < size:
        c = buff1[i]
        i += 1
        if c < 2:
            buff2[j] = c
            j += 1
            continue
        k = 1
        while i < size and k < n:
            if buff1[i] != c: break
            i += 1
            k += 1
        if k == n:
            k += buff1[i]
            i += 1
        for _ in range(k):
            buff2[j] = c
            j += 1
    return j


##### Zero Length Encoding #####

# 符号化
def zle_encode(buff1, buff2):
    size = len(buff1)
    i = 0
    j = 0
    while i < size:
        c = buff1[i]
        i += 1
        if c == 0:
            count = 1
            while i < size and buff1[i] == 0:
                count += 1
                i += 1
            count += 1
            while count != 1:
                buff2[j] = count & 1
                j += 1
                count >>= 1
        elif c == 0xfe:
            buff2[j] = 0xff
            buff2[j + 1] = 0
            j += 2
        elif c == 0xff:
            buff2[j] = 0xff
            buff2[j + 1] = 1
            j += 2
        else:
            buff2[j] = c + 1
            j += 1
    return j

# 復号
def zle_decode(buff1, buff2):
    size = len(buff1)
    i = 0
    j = 0
    while i < size:
        if buff1[i] <= 1:
            # 0 と 1 を探す
            k = 0
            while i < size and buff1[i] <= 1:
                k += 1
                i += 1
            # 数値に変換する
            count = 1
            for x in range(1, k + 1):
                count = (count << 1) + buff1[i - x]
            count -= 1
            for _ in range(count):
                buff2[j] = 0
                j += 1
        else:
            c = buff1[i]
            i += 1
            if c == 0xff:
                c = buff1[i]
                i += 1
                if c == 0:
                    buff2[j] = 0xfe
                else:
                    buff2[j] = 0xff
            else:
                buff2[j] = c - 1
            j += 1
#
# bsrc1.py : ブロックソート + MTF + ZLE + RangeCoder
#
#            Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from array import *
from bwt import *
from mtf import *
from rle import *
from freq import *

# 定数
LIMIT = 0x4000
INC   = 4

# 4 バイトの正整数値を出力
def write_number(num, fout):
    fout.putc((num >> 24) & 0xff)
    fout.putc((num >> 16) & 0xff)
    fout.putc((num >> 8) & 0xff)
    fout.putc(num & 0xff)

# 4 バイトの正整数値を入力
def read_number(fin):
    num = 0
    for _ in range(4):
        num = (num << 8) + fin.getc()
    return num

# 符号化
def bs_encode(fin, fout, size):
    # 入力
    buff = array('B')
    buff.fromfile(fin, size)
    buff *= 2
    # BlockSorting
    work, top = suffix_sort(buff, size)
    # Move To Front
    mtf2_encode(work)
    # Run Length Encoding
    # r_size = zle_encode(work, buff)
    r_size = rle_encode2(work, buff, 7)
    write_number(top, fout)
    write_number(r_size, fout)
    # RangeCoder
    rc = RangeCoder(fout, ENCODE)
    # freq = Freq(256, INC, LIMIT)
    # freq = Freq1(256)
    freq = Freq012(256)
    for x in range(r_size):
        freq.encode(rc, buff[x])
    rc.finish()

# ブロックソートの復号
def bs_decode(fin, fout, size):
    top = read_number(fin)
    r_size = read_number(fin)
    # RangeCoder
    work = array('B')
    rc = RangeCoder(fin, DECODE)
    # freq = Freq(256, INC, LIMIT)
    # freq = Freq1(256)
    freq = Freq012(256)
    for _ in range(r_size):
        work.append(freq.decode(rc))
    # Run Length Encoding
    buff = array('B')
    for _ in range(size): buff.append(0)
    # zle_decode(work, buff)
    rle_decode2(work, buff, 7)
    # Move To Front
    mtf2_decode(buff)
    # BlockSorting
    idx = array('I')
    for _ in range(size): idx.append(0)
    # 分布数えソート
    count = [0] * 256
    for x in range(size): count[ buff[x] ] += 1
    for x in range(1, 256): count[x] += count[x - 1]
    for x in range(size - 1, -1, -1):
        c = buff[x]
        count[c] -= 1
        idx[ count[c] ] = x
    # 出力
    x = idx[top]
    for _ in range(size):
        fout.putc(buff[x])
        x = idx[x]

# 符号化
def encode_file(name1, name2):
    size = os.path.getsize(name1)
    with open(name1, 'rb') as fin, ByteIO(name2, WOPEN) as fout:
        write_number(size, fout)
        if size > 0: bs_encode(fin, fout, size)

# 復号
def decode_file(name1, name2):
    with ByteIO(name1, ROPEN) as fin, ByteIO(name2, WOPEN) as fout:
        size = read_number(fin)
        if size > 0: bs_decode(fin, fout, size)

# オプション解析
parser = argparse.ArgumentParser(description='ブロックソート + MTF + ZLE + レンジコーダ')
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))

●プログラムリスト2

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

#
# structured model
#
LIMIT1 = 0x100
LIMIT2 = 0x200
LIMIT3 = 0x800

class Freq1:
    def __init__(self, size):
        n2 = size >> 1
        n1 = 0
        while n2 > 0:
            n1 += 1
            n2 >>= 1
        self.size = n1
        self.context1 = Freq(n1 + 1, 4, LIMIT2)
        self.context2 = [None] * (n1 + 1)
        for x in range(1, n1 + 1):
            self.context2[x] = Freq(2 ** x, 4, LIMIT3)

    # 符号化
    def encode(self, rc, c):
        n1 = 0
        n2 = (c + 1) >> 1
        while n2 > 0:
            n1 += 1
            n2 >>= 1
        self.context1.encode(rc, n1)
        if n1 > 0:
            self.context2[n1].encode(rc, (c + 1) & ((2 ** n1) - 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

#
# 0-1-2 coding
#
class Freq012:
    def __init__(self, size):
        self.context1 = [Freq(3, 4, LIMIT1) for _ in range(27)]
        self.context2 = Freq1(size - 2)
        self.c0 = self.c1 = self.c2 = 0

    # 符号化
    def encode(self, rc, c):
        freq = self.context1[self.c2 * 9 + self.c1 * 3 + self.c0]
        self.c2 = self.c1
        self.c1 = self.c0
        if c < 2:
            freq.encode(rc, c)
            self.c0 = c
        else:
            freq.encode(rc, 2)
            self.c0 = 2
            self.context2.encode(rc, c - 2)

    # 復号
    def decode(self, rc):
        freq = self.context1[self.c2 * 9 + self.c1 * 3 + self.c0]
        self.c2 = self.c1
        self.c1 = self.c0
        c = freq.decode(rc)
        self.c0 = c
        if c >= 2:
            c = self.context2.decode(rc)
            c += 2
        return c

#
# 混合法
#

# 符号化
def _encode(rc, freq1, freq2, c):
    def cumul():
        n = 0
        for x in range(c):
            n += freq1.count[x] + freq2.count[x]
        return n
    #
    temp = rc.range_ // (freq1.sum_ + freq2.sum_)
    rc.low += cumul() * temp
    rc.range_ = (freq1.count[c] + freq2.count[c]) * temp
    rc.encode_normalize()
    freq1.update(c)
    freq2.update(c)

# 復号
def _decode(rc, freq1, freq2):
    def search_code(value):
        n = 0
        for c in range(freq1.size):
            m = freq1.count[c] + freq2.count[c]
            if value < n + m: break
            n += m
        return c, n
    #
    temp = rc.range_ // (freq1.sum_ + freq2.sum_)
    c, num = search_code(rc.low // temp)
    rc.low -= temp * num
    rc.range_ = temp * (freq1.count[c] + freq2.count[c])
    rc.decode_normalize()
    freq1.update(c)
    freq2.update(c)
    return c

class Freq1m:
    def __init__(self, size):
        n2 = size >> 1
        n1 = 0
        while n2 > 0:
            n1 += 1
            n2 >>= 1
        n1 += 1
        self.size = n1
        self.c0 = self.c1 = 0
        self.context1 = [Freq(n1, 4, LIMIT2) for _ in range(n1 * n1)]  # order-2
        self.context2 = Freq(n1, 12, LIMIT2)
        self.context3 = [None] * n1
        for x in range(1, n1):
            self.context3[x] = Freq(2 ** x, 4, LIMIT3)

    # 符号化
    def encode(self, rc, c):
        n1 = 0
        n2 = (c + 1) >> 1
        while n2 > 0:
            n1 += 1
            n2 >>= 1
        freq1 = self.context1[self.c1 * self.size + self.c0]
        freq2 = self.context2
        _encode(rc, freq1, freq2, n1)
        self.c1 = self.c0
        self.c0 = n1
        if n1 > 0:
            self.context3[n1].encode(rc, (c + 1) & ((2 ** n1) - 1))

    # 復号
    def decode(self, rc):
        freq1 = self.context1[self.c1 * self.size + self.c0]
        freq2 = self.context2
        n1 = _decode(rc, freq1, freq2)
        self.c1 = self.c0
        self.c0 = n1
        if n1 > 0:
            n2 = self.context3[n1].decode(rc)
            n1 = (1 << n1) + n2 - 1
        return n1

class Freq012m:
    def __init__(self, size):
        self.context1 = [Freq(3, 2, LIMIT1) for _ in range(81)]  # order-4
        self.context2 = [Freq(3, 14, LIMIT1) for _ in range(3)]  # order-1
        self.context3 = Freq1m(size - 2)
        self.c0 = self.c1 = self.c2 = self.c3 = 0

    # 符号化
    def encode(self, rc, c):
        freq1 = self.context1[self.c3 * 27 + self.c2 * 9 + self.c1 * 3 + self.c0]
        freq2 = self.context2[self.c0]
        self.c3 = self.c2
        self.c2 = self.c1
        self.c1 = self.c0
        if c < 2:
            _encode(rc, freq1, freq2, c)
            self.c0 = c
        else:
            _encode(rc, freq1, freq2, 2)
            self.c0 = 2
            self.context3.encode(rc, c - 2)

    # 復号
    def decode(self, rc):
        freq1 = self.context1[self.c3 * 27 + self.c2 * 9 + self.c1 * 3 + self.c0]
        freq2 = self.context2[self.c0]
        self.c3 = self.c2
        self.c2 = self.c1
        self.c1 = self.c0
        c = _decode(rc, freq1, freq2)
        self.c0 = c
        if c >= 2:
            c = self.context3.decode(rc) + 2
        return c

初版 2007 年 8 月 11 日
改訂 2022 年 10 月 1 日

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

[ PrevPage | Python | NextPage ]