今回はバイナリレンジコーダを使ってブロックソートに適した情報源モデルを作成します。
最初に、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 1.152 0.675 42,225 1.590 1.112
asyoulik.txt 125,179 38,924 1.328 0.633 38,916 1.375 0.907
cp.html 24,603 7,609 0.254 0.119 7,615 0.301 0.157
fields.c 11,150 3,040 0.239 0.061 3,051 0.172 0.072
grammar.lsp 3,721 1,221 0.105 0.024 1,233 0.092 0.052
kennedy.xls 1,029,744 125,444 7.278 3.940 120,367 7.556 4.077
lcet10.txt 426,754 105,025 3.108 1.748 105,044 4.135 2.637
plrabn12.txt 481,861 141,858 3.814 2.361 141,882 5.107 3.531
ptt5 513,216 47,874 1.927 1.097 47,923 2.253 1.421
sum 38,240 12,652 0.547 0.186 12,659 0.540 0.235
xargs.1 4,227 1,690 0.150 0.030 1,702 0.114 0.038
-------------------------------------------------------------------------
合計 2,810,784 527,593 19.902 10.874 522,617 23.235 14.239
符号化と復号の単位 : 秒
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
γモデルとバイナリモデルどちらでも、多値レンジコーダの structured model なみの圧縮率になりました。γモデルは stuructured model を用いているので、同じような圧縮率になるのは当然だと思いますが、バイナリモデルでも同程度の高い圧縮率を実現できるようです。ただし、どちらのモデルでも実行時間は多値レンジコーダよりも遅くなりました。特に、バイナリモデルは時間がかかります。
次は混合法を適用した結果を示します。
表 : ブロックソートの結果２
(BlockSorting + MTF-2 + ZLE + BinaryRangeCoder:混合法)
ファイル名 サイズ Gamma 符号化 復号 Binary 符号化 復号
-------------------------------------------------------------------------
alice29.txt 152,089 41,922 1.484 1.081 42,038 2.277 1.716
asyoulik.txt 125,179 38,673 1.340 1.055 38,751 1.979 1.503
cp.html 24,603 7,550 0.315 0.191 7,582 0.394 0.253
fields.c 11,150 3,019 0.166 0.072 3,040 0.218 0.125
grammar.lsp 3,721 1,210 0.095 0.033 1,229 0.117 0.055
kennedy.xls 1,029,744 93,258 9.576 6.102 89,838 9.632 6.242
lcet10.txt 426,754 104,381 3.922 2.687 104,638 5.901 4.342
plrabn12.txt 481,861 140,917 5.325 3.563 141,308 7.584 5.732
ptt5 513,216 47,581 2.238 1.503 47,661 2.829 2.034
sum 38,240 12,442 0.569 0.308 12,538 0.721 0.388
xargs.1 4,227 1,682 0.112 0.042 1,701 0.133 0.107
-------------------------------------------------------------------------
合計 2,810,784 492,635 25.142 16.637 490,324 31.785 22.497
符号化と復号の単位 : 秒
混合法を適用することで、どちらのモデルでも圧縮率は 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 1.387 0.776 41,712 1.650 1.389
asyoulik.txt 125,179 38,868 1.117 0.705 38,547 1.411 1.009
cp.html 24,603 7,489 0.287 0.139 7,420 0.334 0.192
fields.c 11,150 2,931 0.145 0.058 2,915 0.173 0.077
grammar.lsp 3,721 1,199 0.089 0.089 1,194 0.099 0.040
kennedy.xls 1,029,744 113,046 8.907 5.392 86,366 11.493 7.846
lcet10.txt 426,754 104,683 3.525 2.018 103,748 4.231 2.866
plrabn12.txt 481,861 141,876 4.240 2.567 140,753 5.289 3.709
ptt5 513,216 47,485 2.753 1.740 47,304 3.239 2.369
sum 38,240 12,305 0.526 0.233 12,142 0.599 0.379
xargs.1 4,227 1,663 0.102 0.029 1,658 0.110 0.042
-------------------------------------------------------------------------
合計 2,810,784 513,628 23.078 13.746 483,759 28.628 19.918
符号化と復号の単位 : 秒
バイナリレンジコーダの場合でも、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()
連長を符号化するγモデルの出現頻度表を変数 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 range(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('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]
出現頻度表の生成は符号化処理 (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 1.122 0.634 41,833 1.551 1.018
asyoulik.txt 125,179 38,948 1.005 0.623 38,593 1.302 0.904
cp.html 24,603 7,577 0.237 0.119 7,507 0.297 0.220
fields.c 11,150 3,036 0.145 0.048 2,992 0.165 0.087
grammar.lsp 3,721 1,220 0.090 0.099 1,206 0.097 0.094
kennedy.xls 1,029,744 114,319 7.147 3.704 86,517 9.344 5.722
lcet10.txt 426,754 105,020 2.986 1.803 104,006 3.821 2.509
plrabn12.txt 481,861 141,845 3.704 2.236 140,568 4.968 3.362
ptt5 513,216 47,710 1.921 1.058 47,441 2.266 1.432
sum 38,240 12,608 0.508 0.204 12,336 0.575 0.283
xargs.1 4,227 1,690 0.093 0.030 1,679 0.103 0.041
-------------------------------------------------------------------------
合計 2,810,784 516,259 18.958 10.558 484,678 24.489 15.672
符号化と復号の単位 : 秒
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 さんに感謝いたします。
#
# rangecoder2.py : バイナリレンジコーダ
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
from rangecoder import *
B_INC = 4
B_LIMIT = 0x200
# コンテキスト
class Context0:
def __init__(self):
self.c0 = 1
self.c1 = 1
# 更新
def update(self, bit):
if bit > 0:
self.c1 += B_INC
else:
self.c0 += B_INC
if self.c0 + self.c1 >= B_LIMIT:
self.c0 = (self.c0 >> 1) | 1
self.c1 = (self.c1 >> 1) | 1
# 符号化
def encode(self, rc, bit):
temp = rc.range_ // (self.c0 + self.c1)
if bit > 0:
rc.low += temp * self.c0
rc.range_ = temp * self.c1
else:
rc.range_ = temp * self.c0
rc.encode_normalize()
self.update(bit)
# 復号
def decode(self, rc):
temp = rc.range_ // (self.c0 + self.c1)
if rc.low // temp < self.c0:
bit = 0
rc.range_ = temp * self.c0
else:
bit = 1
rc.low -= temp * self.c0
rc.range_ = temp * self.c1
rc.decode_normalize()
self.update(bit)
return bit
# 改良版
class 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
##### バイナリモデル #####
class Freq2:
def __init__(self, size):
self.size = size
self.context = [Context() for _ in range(size - 1)]
# 符号化
def encode(self, rc, code):
def encode_sub(node):
if node > 0:
p = (node - 1) // 2
encode_sub(p)
# 奇数は左の子 (1), 偶数は右の子 (0)
bit = node & 1
self.context[p].encode(rc, bit)
#
encode_sub(code + self.size - 1)
# 復号
def decode(self, rc):
node = 0
node_size = self.size - 1
while node < node_size:
bit = self.context[node].decode(rc)
if bit > 0:
# 1 は左の子
node = 2 * node + 1
else:
# 0 は右の子
node = 2 * node + 2
return node - node_size
##### αモデル #####
class AlphaFreq:
def __init__(self, size):
self.size = size - 1
self.context = [Context() for _ in range(size - 1)]
# 符号化
def encode(self, rc, c):
for x in range(self.size):
if x < c:
bit = 0
else:
bit = 1
self.context[x].encode(rc, bit)
if bit: break
# 復号
def decode(self, rc):
c = 0
while c < self.size:
bit = self.context[c].decode(rc)
if bit: break
c += 1
return c
##### γモデル #####
# ビット列モデル
class BitsFreq:
def __init__(self, size):
self.size = size
self.context = [Context() for _ in range(size)]
# 符号化
def encode(self, rc, c):
for x in range(self.size):
bit = (c >> x) & 1
self.context[x].encode(rc, bit)
# 復号
def decode(self, rc):
c = 0
for x in range(self.size):
bit = self.context[x].decode(rc)
if bit: c |= bit << x
return c
# γモデル
class GammaFreq:
def __init__(self, size):
n2 = size >> 1
n1 = 0
while n2 > 0:
n1 += 1
n2 >>= 1
self.size = n1
self.context1 = AlphaFreq(n1 + 1)
self.context2 = [None] * (n1 + 1)
for x in range(1, n1 + 1):
self.context2[x] = BitsFreq(x)
# 符号化
def encode(self, rc, n):
n1 = 0
n2 = (n + 1) >> 1
while n2 > 0:
n1 += 1
n2 >>= 1
self.context1.encode(rc, n1)
if n1 > 0:
self.context2[n1].encode(rc, n + 1)
# 復号
def decode(self, rc):
n1 = self.context1.decode(rc)
if n1 > 0:
n2 = self.context2[n1].decode(rc)
n1 = (1 << n1) + n2 - 1
return n1
##### 0-1-2 coding #####
class Freq012:
def __init__(self, size):
self.context1 = [AlphaFreq(3) for _ in range(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
#
# rangecoder2m.py : バイナリレンジコーダ (混合法)
#
# Copyright (C) 2007-2022 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.c1 = [1] * 5
# 更新
def update(self, bit):
x = self.prev + 1
if bit > 0:
self.c1[0] += B_INC0
self.c1[x] += B_INC2
else:
self.c0[0] += B_INC0
self.c0[x] += B_INC2
if self.c0[0] + self.c1[0] >= B_LIMIT:
self.c0[0] = (self.c0[0] >> 1) | 1
self.c1[0] = (self.c1[0] >> 1) | 1
if self.c0[x] + self.c1[x] >= B_LIMIT:
self.c0[x] = (self.c0[x] >> 1) | 1
self.c1[x] = (self.c1[x] >> 1) | 1
self.prev = ((self.prev << 1) | bit) & 0x03
# 記号 0 の出現頻度を求める
def get_c0(self):
return self.c0[0] + self.c0[self.prev + 1]
# 記号 1 の出現頻度を求める
def get_c1(self):
return self.c1[0] + self.c1[self.prev + 1]
# 符号化
def encode(self, rc, bit):
c0 = self.get_c0()
c1 = self.get_c1()
temp = rc.range_ // (c0 + c1)
if bit > 0:
rc.low += temp * c0
rc.range_ = temp * c1
else:
rc.range_ = temp * c0
rc.encode_normalize()
self.update(bit)
# 復号
def decode(self, rc):
c0 = self.get_c0()
c1 = self.get_c1()
temp = rc.range_ // (c0 + c1)
if rc.low // temp < c0:
bit = 0
rc.range_ = temp * c0
else:
bit = 1
rc.low -= temp * c0
rc.range_ = temp * c1
rc.decode_normalize()
self.update(bit)
return bit
##### バイナリモデル (binary model) #####
# 出現頻度表
class Freq2:
def __init__(self, size):
self.size = size
self.context = [Context() for _ in range(size - 1)]
# 符号化
def encode(self, rc, code):
def encode_sub(node):
if node > 0:
p = (node - 1) // 2
encode_sub(p)
# 奇数は左の子 (1), 偶数は右の子 (0)
bit = node & 1
self.context[p].encode(rc, bit)
#
encode_sub(code + self.size - 1)
# 復号
def decode(self, rc):
node = 0
node_size = self.size - 1
while node < node_size:
bit = self.context[node].decode(rc)
if bit > 0:
# 1 は左の子
node = 2 * node + 1
else:
# 0 は右の子
node = 2 * node + 2
return node - node_size
##### αモデル #####
class AlphaFreq:
def __init__(self, size):
self.size = size - 1
self.context = [Context() for _ in range(size - 1)]
# 符号化
def encode(self, rc, c):
for x in range(self.size):
if x < c:
bit = 0
else:
bit = 1
self.context[x].encode(rc, bit)
if bit: break
# 復号
def decode(self, rc):
c = 0
while c < self.size:
bit = self.context[c].decode(rc)
if bit: break
c += 1
return c
##### γモデル #####
class BitsFreq:
def __init__(self, size):
self.size = size
self.context = [Context() for _ in range(size)]
# 符号化
def encode(self, rc, c):
for x in range(self.size):
bit = (c >> x) & 1
self.context[x].encode(rc, bit)
# 復号
def decode(self, rc):
c = 0
for x in range(self.size):
bit = self.context[x].decode(rc)
if bit: c |= bit << x
return c
class GammaFreq:
def __init__(self, size):
n2 = size >> 1
n1 = 0
while n2 > 0:
n1 += 1
n2 >>= 1
self.size = n1
self.context1 = AlphaFreq(n1 + 1)
self.context2 = [None] * (n1 + 1)
for x in range(1, n1 + 1):
self.context2[x] = BitsFreq(x)
# 符号化
def encode(self, rc, n):
n1 = 0
n2 = (n + 1) >> 1
while n2 > 0:
n1 += 1
n2 >>= 1
self.context1.encode(rc, n1)
if n1 > 0:
self.context2[n1].encode(rc, n + 1)
# 復号
def decode(self, rc):
n1 = self.context1.decode(rc)
if n1 > 0:
n2 = self.context2[n1].decode(rc)
n1 = (1 << n1) + n2 - 1
return n1
##### 0-1-2 coding #####
class Freq012:
def __init__(self, size):
self.context1 = [AlphaFreq(3) for _ in range(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
#
# bsrc2.py : ブロックソート + MTF + Zero Run Transform
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from array import *
from bwt import *
from mtf import *
from rangecoder2m import *
# 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)
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()
# ブロックソートの復号
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 range(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('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 + ZRT')
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))