ブロックソート (BlockSorting) の続きです。今回は バイナリレンジコーダ を使ってブロックソートに適した情報源モデルを作成します。
最初に、Zero Lenght Encoding (ZLE) のあとに「γモデル」と「バイナリモデル」で符号化してみましょう。バイナリレンジコーダは圧縮性能が高いので、これだけでも高い圧縮率を実現することができます。また、混合法を使うとさらに圧縮率を向上させることができます。
プログラムの修正はとても簡単です。rangecoder2.py (プログラムリスト１) を import して、γモデルであれば GammaFreq を、バイナリモデルであれば Freq2 を呼び出して出現頻度表を生成します。混合法を使う場合は rangecoder2m.py (プログラムリスト２) を import してください。
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。
表 : ブロックソートの結果１
(BlockSorting + MTF-2 + ZLE + BinaryRangeCoder)
ファイル名 サイズ Gamma 符号化 復号 Binary 符号化 復号
----------------------------------------------------------------------
alice29.txt 152,089 42,256 6.35 4.40 42,225 9.23 7.13
asyoulik.txt 125,179 38,924 5.57 4.76 38,916 8.00 6.19
cp.html 24,603 7,609 1.27 0.75 7,615 1.60 1.05
fields.c 11,150 3,040 0.66 0.31 3,051 0.83 0.48
grammar.lsp 3,721 1,221 0.39 0.12 1,233 0.42 0.18
kennedy.xls 1,029,744 125,444 39.96 25.38 120,367 41.47 25.77
lcet10.txt 426,754 105,025 16.77 11.34 105,044 24.21 18.41
plrabn12.txt 481,861 141,858 20.52 15.02 141,882 30.02 23.56
ptt5 513,216 47,874 10.15 6.68 47,923 12.69 8.94
sum 38,240 12,652 2.77 1.21 12,659 3.22 1.62
xargs.1 4,227 1,690 0.42 0.16 1,702 0.48 0.23
---------------------------------------------------------------------
合計 2,810,784 527,593 104.83 70.13 522,617 132.17 93.56
# 符号化と復号の単位 : 秒
実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
γモデルとバイナリモデルどちらでも、多値レンジコーダの structured model なみの圧縮率になりました。γモデルは stuructured model を用いているので、同じような圧縮率になるのは当然だと思いますが、バイナリモデルでも同程度の高い圧縮率を実現できるようです。ただし、どちらのモデルでも実行時間は多値レンジコーダよりも遅くなりました。特に、バイナリモデルは時間がかかります。
次は混合法を適用した結果を示します。
表 : ブロックソートの結果２
(BlockSorting + MTF-2 + ZLE + BinaryRangeCoder:混合法)
ファイル名 サイズ Gamma 符号化 復号 Binary 符号化 復号
----------------------------------------------------------------------
alice29.txt 152,089 41,922 8.04 6.07 42,037 12.45 10.54
asyoulik.txt 125,179 38,672 7.17 5.55 38,750 10.89 9.02
cp.html 24,603 7,550 1.54 1.03 7,582 2.10 1.53
fields.c 11,150 3,018 0.76 0.42 3,040 1.06 0.69
grammar.lsp 3,721 1,210 0.40 0.16 1,229 0.52 0.25
kennedy.xls 1,029,744 93,716 51.06 36.24 89,940 52.04 35.97
lcet10.txt 426,754 104,381 21.05 15.55 104,636 32.46 26.25
plrabn12.txt 481,861 140,914 26.57 20.89 141,307 40.93 34.28
ptt5 513,216 47,581 12.06 8.56 47,661 15.91 12.10
sum 38,240 12,442 3.24 1.70 12,537 4.00 2.35
xargs.1 4,227 1,682 0.46 0.22 1,701 0.60 0.34
---------------------------------------------------------------------
合計 2,810,784 493,088 132.35 96.39 490,420 172.96 133.32
# 符号化と復号の単位 : 秒
実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
混合法を適用することで、どちらのモデルでも圧縮率は bzip2 を上回り、多値レンジコーダの 0-1-2 coding と同じ程度になりました。特に、kennedy.xls の圧縮率は大幅に向上しました。混合法の効果はとても高いですね。そのかわり、実行時間はとても遅くなりました。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
次はバイナリレンジコーダを使って 0-1-2 coding を実装してみましょう。プログラムは簡単に作成できます。記号 {0, 1, 2} の符号化にはαモデルを、2 以上の記号の符号化にはγモデルを用います。プログラムは次のようになります。
リスト : 0-1-2 coding (バイナリレンジコーダ)
class Freq012:
def __init__(self, size):
self.context1 = [AlphaFreq(3) for _ in xrange(27)]
self.context2 = GammaFreq(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
0-1-2 coding は記号の種類が 3 つしかないので、αモデルで簡単に符号化できます。この場合、AlphaFreq の引数には 3 を渡します。そして、2 以上の記号を GammaFreq で符号化します。引数は size - 2 になります。あとは多値レンジコーダの 0-1-2 coding と同じです。混合法を適用する場合は、混合法のαモデルとγモデルを使うだけです。とても簡単ですね。
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。
表 : ブロックソートの結果
(BlockSorting + MTF-2 + 0-1-2 coding (BinaryRangeCoder))
ファイル名 サイズ 0-1-2 符号化 復号 混合法 符号化 復号
---------------------------------------------------------------------
alice29.txt 152,089 42,083 6.72 4.66 41,712 8.58 6.42
asyoulik.txt 125,179 38,868 5.86 4.20 38,547 7.58 5.85
cp.html 24,603 7,489 1.35 0.85 7,420 1.70 1.17
fields.c 11,150 2,931 0.67 0.33 2,915 0.80 0.45
grammar.lsp 3,721 1,199 0.36 0.13 1,194 0.42 0.18
kennedy.xls 1,029,744 113,046 47.66 32.74 86,820 61.84 46.31
lcet10.txt 426,754 104,683 18.17 12.41 103,747 22.91 16.93
plrabn12.txt 481,861 141,876 21.87 15.97 140,753 28.14 21.97
ptt5 513,216 47,485 14.62 10.97 47,302 18.27 14.45
sum 38,240 12,305 2.93 1.36 12,142 3.48 1.90
xargs.1 4,227 1,663 0.45 0.17 1,658 0.47 0.23
---------------------------------------------------------------------
合計 2,810,784 513,628 120.66 83.79 484,210 154.19 115.86
# 符号化と復号の単位 : 秒
実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
バイナリレンジコーダの場合でも、0-1-2 coding を適用することにより、圧縮率は高くなりました。多値レンジコーダの 0-1-2 coding よりも圧縮率は少し悪くなるようです。混合法を適用すると、圧縮率はさらに向上します。テキストファイルの場合、多値レンジコーダの 0-1-2 coding 混合法よりも圧縮率は少しだけ悪くなりますが、kennedy.xls の圧縮率がとても高くなるため、合計値ではとても高い圧縮率になりました。ただし、実行時間は遅くなります。バイナリレンジコーダの場合でも、0-1-2 coding の効果はとても高いようです。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
次はバイナリレンジコーダらしいモデルを紹介します。γモデルの特徴は、大きな整数値でも効率よく符号化できる点にあります。そこで、ランレングスの連長をγモデルで符号化することを考えてみましょう。
ランレングスの連長をγモデルで符号化する場合、いろいろな方法が考えられます。いくつかの方法を試してみたのですが、通常のランレングスのように「開始記号 + 連長」の形式で、連長をγモデルで符号化しても効果はほとんどありませんでした。
また、記号 0 だけをランレングスで圧縮するゼロランレングスの場合でも、「0 + 連長」の形式では、連長をγモデルで符号化しても効果はありません。ほかにも、Pack Bits や Switched Run Length Encoding を参考にいろいろ試してみたのですが、効果はほとんどありませんでした。
そこで、Yuta Mori さんの white page で公開されているプログラムを参考にしたところ、効果的な方法がありました。この方法は「記号 0 の連長」と「0 以外の記号」を交互に符号化します。そして、記号 0 の連長をγモデルで符号化するのです。この方法を Zero Run Transform といいます。
Zero Run Transform は 0 以外の記号が続く場合、記号と記号の間に記号 0 がないことを示すため連長 0 を符号化することになります。簡単な例を示しましょう。次の図を見てください。
"01000234" ==> [(1), 0, (3), 1, (0), 2, (0), 3] ; (n) = 記号 0 の連長
最初は 0 が 1 個なので、0 の連長 1 を符号化します。次は 0 以外の記号を符号化します。このとき、0 以外の記号はそのまま符号化するのではなく、値を -1 してから符号化します。そのまま符号化すると、圧縮率が悪くなってしまいます。
次は 0 が 3 個あるので連長 3 を符号化し、次の記号が 2 なので 1 を符号化します。次は 0 の連長を符号化しますが、記号は 0 ではありません。この場合、記号 0 が 0 個ということで、連長 0 を符号化します。それから、記号 3 を符号化するのです。このように、「記号 0 の連長」と「0 以外の記号」を交互に符号化していくわけです。
連長 0 を符号化するのは無駄なように思われますが、このほうが「開始記号 + 連長」の形式で連長をγモデルで符号化するよりも圧縮率が高くなるのです。これには M.Hiroi も驚きました。γモデルの場合、0 の出現確率が大きいので、連長 0 を符号化しても効率よく圧縮できるのでしょう。
それではプログラムを作りましょう。次のリストを見てください。
リスト : 符号化 (Zero Run Transform)
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)
write_number(top, fout)
# RangeCoder (Zero Run Transform)
rc = RangeCoder(fout, ENCODE)
freq_len = GammaFreq(size + 1)
freq_code = GammaFreq(255)
i = 0
while i < size:
# 0 の個数を符号化
count = 0
while i < size and work[i] == 0:
count += 1
i += 1
freq_len.encode(rc, count)
if i == size: break
# 記号を符号化
freq_code.encode(rc, work[i] - 1)
i += 1
rc.finish()
# 終了
fin.close()
fout.close()
連長を符号化するγモデルの出現頻度表を変数 freq_len にセットします。連長の最大値は size + 1 になります。記号を符号化するγモデルの出現頻度表を変数 freq_code にセットします。記号の種類は 255 になります。
そして、while ループで記号 0 の連長と記号を交互に符号化します。最初に記号 0 の個数を数えます。そして、個数 count を freq_len.encode で符号化します。count が 0 の場合も符号化することに注意してください。そのあとで、0 以外の記号を符号化します。このとき、記号を -1 することをお忘れなく。
次に記号を復号する関数 bs_decode を修正します。
リスト : 復号 (Zero Run Transform)
def bs_decode(fin, fout, size):
top = read_number(fin)
buff = array('B')
# RangeCoder (Zero Run Transform)
rc = RangeCoder(fin, DECODE)
freq_len = GammaFreq(size + 1)
freq_code = GammaFreq(255)
i = 0
while i < size:
# 0 の個数を復号
count = freq_len.decode(rc)
for _ in xrange(count): buff.append(0)
i += count
if i == size: break
# 記号を復号
buff.append(freq_code.decode(rc) + 1)
i += 1
# Move To Front
mtf2_decode(buff)
# BlockSorting
idx = array('L')
for _ in xrange(size): idx.append(0)
# 分布数えソート
count = [0] * 256
for x in xrange(size): count[ buff[x] ] += 1
for x in xrange(1, 256): count[x] += count[x - 1]
for x in xrange(size - 1, -1, -1):
c = buff[x]
count[c] -= 1
idx[ count[c] ] = x
# 出力
x = idx[top]
for _ in xrange(size):
putc(fout, buff[x])
x = idx[x]
出現頻度表の生成は符号化処理 (bs_encode) と同じです。最初に freq_len.decode を呼び出して記号 0 の個数を復号します。そして、count の個数だけバッファ work に 0 を追加します。次に、freq_code.decode で記号を復号して work に追加します。とても簡単ですね。
なお、記号 0 の連長をγモデルで符合化する場合、通常のランレングスとは相性があまりよくありません。特に、Zero Length Encoding を適用しても効果はほとんどありません。ただし、データによってはランレングスが有効な場合もあります。これは 0-1-2 coding の場合と同じで、1 以上の記号に対してランレングスを適用すると、ファイルによっては効果的な場合があります。
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。
表 : ブロックソートの結果
(BlockSorting + MTF-2 + Zero Run Transform)
ファイル名 サイズ ZRT 符号化 復号 混合法 符号化 復号
---------------------------------------------------------------------
alice29.txt 152,089 42,286 6.34 4.23 41,833 8.05 5.84
asyoulik.txt 125,179 38,948 5.63 3.91 38,592 7.21 5.41
cp.html 24,603 7,577 1.28 0.73 7,507 1.56 1.02
fields.c 11,150 3,036 0.66 0.29 2,991 0.75 0.40
grammar.lsp 3,721 1,220 0.40 0.12 1,206 0.40 0.16
kennedy.xls 1,029,744 114,319 39.93 24.37 86,881 50.43 34.71
lcet10.txt 426,754 105,020 16.84 10.86 104,005 21.04 14.92
plrabn12.txt 481,861 141,845 21.06 14.67 140,567 26.74 20.30
ptt5 513,216 47,710 10.44 6.53 47,441 12.32 8.44
sum 38,240 12,608 2.79 1.18 12,336 3.26 1.67
xargs.1 4,227 1,690 0.42 0.16 1,679 0.47 0.22
---------------------------------------------------------------------
合計 2,810,784 516,259 105.79 67.05 485,038 132.23 93.09
# 符号化と復号の単位 : 秒
実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
Zero Run Transform の圧縮率は 0-1-2 coding よりも少し悪くなりますが、それでも bzip2 を超える高い圧縮率になりました。混合法を適用すると圧縮率はさらに向上し、0-1-2 coding 混合法に匹敵する圧縮率になります。実行時間は 0-1-2 coding よりは速いですが、多値レンジコーダの 0-1-2 coding よりも遅くなりました。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
今回のプログラムを作成するに当たり、Yuta Mori さんの Web サイト white page で公開されているプログラムを参考にさせていただきました。素晴らしいプログラムとドキュメントを公開されている Yuta Mori さんに感謝いたします。
# coding: utf-8
#
# rangecoder2.py : バイナリレンジコーダ
#
# Copyright (C) 2007 Makoto Hiroi
#
from rangecoder import *
B_INC = 4
B_LIMIT = 0x200
# コンテキスト
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
##### バイナリモデル (binary model) #####
# 出現頻度表
class Freq2:
def __init__(self, size):
self.size = size
self.context = [Context() for _ in xrange(size - 1)]
# 符号化
def encode(self, rc, code):
def encode_sub(node):
if node > 0:
p = (node - 1) / 2
encode_sub(p)
# 奇数は左の子 (1), 偶数は右の子 (0)
bit = node & 1
self.context[p].encode(rc, bit)
#
encode_sub(code + self.size - 1)
# 復号
def decode(self, rc):
node = 0
node_size = self.size - 1
while node < node_size:
bit = self.context[node].decode(rc)
if bit > 0:
# 1 は左の子
node = 2 * node + 1
else:
# 0 は右の子
node = 2 * node + 2
return node - node_size
##### αモデル #####
class AlphaFreq:
def __init__(self, size):
self.size = size - 1
self.context = [Context() for _ in xrange(size - 1)]
# 符号化
def encode(self, rc, c):
for x in xrange(self.size):
if x < c:
bit = 0
else:
bit = 1
self.context[x].encode(rc, bit)
if bit: break
# 復号
def decode(self, rc):
c = 0
while c < self.size:
bit = self.context[c].decode(rc)
if bit: break
c += 1
return c
##### γモデル #####
class BitsFreq:
def __init__(self, size):
self.size = size
self.context = [Context() for _ in xrange(size)]
# 符号化
def encode(self, rc, c):
for x in xrange(self.size):
bit = (c >> x) & 1
self.context[x].encode(rc, bit)
# 復号
def decode(self, rc):
c = 0
for x in xrange(self.size):
bit = self.context[x].decode(rc)
if bit: c |= bit << x
return c
class GammaFreq:
def __init__(self, size):
n2 = size >> 1
n1 = 0
while n2 > 0:
n1 += 1
n2 >>= 1
self.size = n1
self.context1 = AlphaFreq(n1 + 1)
self.context2 = [None] * (n1 + 1)
for x in xrange(1, n1 + 1):
self.context2[x] = BitsFreq(x)
# 符号化
def encode(self, rc, n):
n1 = 0
n2 = (n + 1) >> 1
while n2 > 0:
n1 += 1
n2 >>= 1
self.context1.encode(rc, n1)
if n1 > 0:
self.context2[n1].encode(rc, n + 1)
# 復号
def decode(self, rc):
n1 = self.context1.decode(rc)
if n1 > 0:
n2 = self.context2[n1].decode(rc)
n1 = (1 << n1) + n2 - 1
return n1
##### 0-1-2 coding #####
class Freq012:
def __init__(self, size):
self.context1 = [AlphaFreq(3) for _ in xrange(27)]
self.context2 = GammaFreq(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
# coding: utf-8
#
# rangecoder2m.py : バイナリレンジコーダ (混合法)
#
# Copyright (C) 2007 Makoto Hiroi
#
from rangecoder import *
B_INC0 = 10
B_INC2 = 2
B_LIMIT = 0x200
# コンテキスト
class Context:
def __init__(self):
self.prev = 0
self.c0 = [1] * 5 # 0: order-1, 1 - 4: order-2
self.sum = [2] * 5
# 更新
def update(self, bit):
x = self.prev + 1
self.sum[0] += B_INC0
self.sum[x] += B_INC2
if bit == 0:
self.c0[0] += B_INC0
self.c0[x] += B_INC2
if self.sum[0] >= B_LIMIT:
self.c0[0] = (self.c0[0] >> 1) | 1
self.sum[0] = (self.sum[0] >> 1) | 1
if self.c0[0] >= self.sum[0]: self.sum[0] = self.c0[0] + 1
if self.sum[x] >= B_LIMIT:
self.c0[x] = (self.c0[x] >> 1) | 1
self.sum[x] = (self.sum[x] >> 1) | 1
if self.c0[x] >= self.sum[x]: self.sum[x] = self.c0[x] + 1
self.prev = ((self.prev << 1) | bit) & 0x03
#
def get_c0(self):
return self.c0[0] + self.c0[self.prev + 1]
#
def get_sum(self):
return self.sum[0] + self.sum[self.prev + 1]
# 符号化
def encode(self, rc, bit):
c0 = self.get_c0()
sum = self.get_sum()
temp = rc.range / sum
if bit > 0:
rc.low += temp * c0
rc.range -= temp * c0
else:
rc.range = temp * c0
rc.encode_normalize()
self.update(bit)
# 復号
def decode(self, rc):
c0 = self.get_c0()
sum = self.get_sum()
temp = rc.range / sum
if rc.low / temp < c0:
bit = 0
rc.range = temp * c0
else:
bit = 1
rc.low -= temp * c0
rc.range -= temp * c0
rc.decode_normalize()
self.update(bit)
return bit
##### バイナリモデル (binary model) #####
# 出現頻度表
class Freq2:
def __init__(self, size):
self.size = size
self.context = [Context() for _ in xrange(size - 1)]
# 符号化
def encode(self, rc, code):
def encode_sub(node):
if node > 0:
p = (node - 1) / 2
encode_sub(p)
# 奇数は左の子 (1), 偶数は右の子 (0)
bit = node & 1
self.context[p].encode(rc, bit)
#
encode_sub(code + self.size - 1)
# 復号
def decode(self, rc):
node = 0
node_size = self.size - 1
while node < node_size:
bit = self.context[node].decode(rc)
if bit > 0:
# 1 は左の子
node = 2 * node + 1
else:
# 0 は右の子
node = 2 * node + 2
return node - node_size
##### αモデル #####
class AlphaFreq:
def __init__(self, size):
self.size = size - 1
self.context = [Context() for _ in xrange(size - 1)]
# 符号化
def encode(self, rc, c):
for x in xrange(self.size):
if x < c:
bit = 0
else:
bit = 1
self.context[x].encode(rc, bit)
if bit: break
# 復号
def decode(self, rc):
c = 0
while c < self.size:
bit = self.context[c].decode(rc)
if bit: break
c += 1
return c
##### γモデル #####
class BitsFreq:
def __init__(self, size):
self.size = size
self.context = [Context() for _ in xrange(size)]
# 符号化
def encode(self, rc, c):
for x in xrange(self.size):
bit = (c >> x) & 1
self.context[x].encode(rc, bit)
# 復号
def decode(self, rc):
c = 0
for x in xrange(self.size):
bit = self.context[x].decode(rc)
if bit: c |= bit << x
return c
class GammaFreq:
def __init__(self, size):
n2 = size >> 1
n1 = 0
while n2 > 0:
n1 += 1
n2 >>= 1
self.size = n1
self.context1 = AlphaFreq(n1 + 1)
self.context2 = [None] * (n1 + 1)
for x in xrange(1, n1 + 1):
self.context2[x] = BitsFreq(x)
# 符号化
def encode(self, rc, n):
n1 = 0
n2 = (n + 1) >> 1
while n2 > 0:
n1 += 1
n2 >>= 1
self.context1.encode(rc, n1)
if n1 > 0:
self.context2[n1].encode(rc, n + 1)
# 復号
def decode(self, rc):
n1 = self.context1.decode(rc)
if n1 > 0:
n2 = self.context2[n1].decode(rc)
n1 = (1 << n1) + n2 - 1
return n1
##### 0-1-2 coding #####
class Freq012:
def __init__(self, size):
self.context1 = [AlphaFreq(3) for _ in xrange(27)]
self.context2 = GammaFreq(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
# coding: utf-8
#
# bsrc.py : ブロックソート (BlockSorting) によるファイルの圧縮
#
# Copyright (C) 2007 Makoto Hiroi
#
import time, sys, getopt, os.path
from array import *
from bwt import *
from mtf import *
from freq import *
from rangecoder2m import *
# 4 バイトの正整数値を出力
def write_number(num, fout):
putc(fout, (num >> 24) & 0xff)
putc(fout, (num >> 16) & 0xff)
putc(fout, (num >> 8) & 0xff)
putc(fout, num & 0xff)
# 4 バイトの正整数値を入力
def read_number(fin):
num = 0
for _ in xrange(4):
num = (num << 8) + getc(fin)
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)
# print work.count(0)
write_number(top, fout)
# RangeCoder (Zero Run Transform)
rc = RangeCoder(fout, ENCODE)
freq_len = GammaFreq(size + 1)
freq_code = GammaFreq(255)
i = 0
while i < size:
# 0 の個数を符号化
count = 0
while i < size and work[i] == 0:
count += 1
i += 1
freq_len.encode(rc, count)
if i == size: break
# 記号を符号化
freq_code.encode(rc, work[i] - 1)
i += 1
rc.finish()
# 終了
fin.close()
fout.close()
# ブロックソートの復号
def bs_decode(fin, fout, size):
top = read_number(fin)
buff = array('B')
# RangeCoder (Zero Run Transform)
rc = RangeCoder(fin, DECODE)
freq_len = GammaFreq(size + 1)
freq_code = GammaFreq(255)
i = 0
while i < size:
# 0 の個数を復号
count = freq_len.decode(rc)
for _ in xrange(count): buff.append(0)
i += count
if i == size: break
# 記号を復号
buff.append(freq_code.decode(rc) + 1)
i += 1
# Move To Front
mtf2_decode(buff)
# BlockSorting
idx = array('L')
for _ in xrange(size): idx.append(0)
# 分布数えソート
count = [0] * 256
for x in xrange(size): count[ buff[x] ] += 1
for x in xrange(1, 256): count[x] += count[x - 1]
for x in xrange(size - 1, -1, -1):
c = buff[x]
count[c] -= 1
idx[ count[c] ] = x
# 出力
x = idx[top]
for _ in xrange(size):
putc(fout, buff[x])
x = idx[x]
# 符号化
def encode_file(name1, name2):
size = os.path.getsize(name1)
infile = open(name1, "rb")
outfile = open(name2, "wb")
write_number(size, outfile)
if size > 0: bs_encode(infile, outfile, size)
infile.close()
outfile.close()
# 復号
def decode_file(name1, name2):
infile = open(name1, "rb")
outfile = open(name2, "wb")
size = read_number(infile)
if size > 0: bs_decode(infile, outfile, size)
infile.close()
outfile.close()
#
def main():
eflag = False
dflag = False
opts, args = getopt.getopt(sys.argv[1:], 'ed')
for x, y in opts:
if x == '-e' or x == '-E':
eflag = True
elif x == '-d' or x == '-D':
dflag = True
if eflag and dflag:
print 'option error'
elif eflag:
encode_file(args[0], args[1])
elif dflag:
decode_file(args[0], args[1])
else:
print 'option error'
#
s = time.clock()
main()
e = time.clock()
print "%.3f" % (e - s)