今回はαモデルとγモデルの例題として、バイナリレンジコーダと LZ 符号を組み合わせてファイルを圧縮してみましょう。
最初に、バイナリレンジコーダと「LZSS 符号」を組み合わせてみましょう。本ページでは LZRC 符号と呼ぶことにします。LZH 符号 は LZSS 符号とハフマン符号を組み合わせることで高い圧縮率を実現しています。LZRC 符号はバイナリレンジコーダを用いることで、さらに圧縮率を改善することができます。次のリストを見てください。
リスト : 出現頻度表の初期化
def init_freq():
global freq_flag, freq_code, freq_pos, freq_len
freq_flag = AlphaFreq(2)
freq_code = Freq2(256)
freq_len = GammaFreq(MAX_LEN - MIN_LEN + 1)
freq_pos = GammaFreq(1 << POS_BITS)
関数 init_freq() は各モデルの出現頻度表を生成してグローバル変数にセットします。符号語を区別するフラグはαモデルで符号化します。AlphaFreq のオブジェクトを生成して freq_flag にセットします。フラグで使用する記号は {0, 1} の 2 つだけなので、AlphaFreq の引数には 2 を渡します。記号はバイナリモデルで符号化します。Freq2 のオブジェクトを生成して freq_code にセットします。記号は 256 種類 (0 - 255) あるので、Freq2 の引数は 256 になります。
長さはγモデルで符号化します。GammaFreq のオブジェクトを生成して freq_len にセットします。LZSS 符号の場合、長さが MIN_LEN 以上の記号列を符号化するので、GammaFreq に渡す記号の種類は MAX_LEN - MIN_LEN になります。距離 (位置) の符号化もγモデルを使います。GammaFreq にスライド窓の大きさ (1 << POS_BITS) を渡してオブジェクトを生成して freq_pos にセットします。
なお、γモデルは小さな整数ほど出現確率が高くなる場合に適したモデルです。一般的なテキストファイルの場合、短い距離が多く出現するとは考えにくいので、γモデルをそのまま使うよりも、違うモデルを作成した方がよいでしょう。たとえば、γモデルのα符号部をバイナリモデルに変更すると、テキストファイルの圧縮率は少し良くなるようです。興味のある方は試してみてください。
あとは、符号化と復号を行う関数を修正するだけです。符号化を行う関数 encode() は次のようになります。
リスト : LZRC 符号の符号化
def encode(fin, fout):
init_freq()
rc = RangeCoder(fout, ENCODE)
s = Slide(fin)
rp = 0
while rp < s.data_size:
s.search(rp)
if s.match_len < MIN_LEN:
num = 1
freq_flag.encode(rc, 0)
freq_code.encode(rc, s.buff[rp])
else:
num = s.match_len
freq_flag.encode(rc, 1)
freq_len.encode(rc, num - MIN_LEN)
freq_pos.encode(rc, rp - s.match_pos - 1)
for _ in range(num):
s.insert(rp)
rp += 1
if rp >= s.limit: rp = s.update(rp)
rc.finish()
最初に RangeCoder() で符号化用レンジコーダを生成し、各モデルの出現頻度表を init_freq() で初期化します。MIN_LEN 以上の記号列が見つからない場合は、freq_flag.encode() で 0 を符号化し、freq_code.encode() で記号 s.buff[rp] を符号化します。
MIN_LEN 以上の記号列が見つかった場合は、freq_flag.encode() で 1 を符号化します。次に、freq_len.encode() で長さ num - MIN_LEN を符号化し、freq_pos.encode() で距離 rp - match_pos - 1 を符号化します。最後に rc.finish() を呼び出して符号化を終了します。
次は復号を行う関数 decode() を修正します。次のリストを見てください。
リスト : LZRC 符号の復号
def decode(fin, fout, size):
init_freq()
rc = RangeCoder(fin, DECODE)
rp = 0
buff = [0] * (1 << POS_BITS)
while size > 0:
if freq_flag.decode(rc):
num = freq_len.decode(rc) + MIN_LEN
pos = freq_pos.decode(rc) + 1
pos = rp - pos
if pos < 0: pos += len(buff)
for _ in range(num):
c = buff[pos]
fout.putc(c)
buff[rp] = c
pos += 1
rp += 1
if pos >= len(buff): pos = 0
if rp >= len(buff): rp = 0
else:
num = 1
c = freq_code.decode(rc)
fout.putc(c)
buff[rp] = c
rp += 1
if rp >= len(buff): rp = 0
size -= num
最初に RangeCoder() で復号用レンジコーダを生成し、各モデルの出現頻度表を init_freq() で初期化します。最初に freq_flag.decode() でフラグを復号します。フラグが 1 の場合、 freq_len.decode() で長さを復号します。次に freq_pos.decode() で距離を復号し、距離と長さから記号列を復号します。記号を復号する場合は freq_code.decode() で記号を一つ復号するだけです。
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。
表 : LZRC 符号 (order-0) の結果 (スライド窓 8 k) [1]
ファイル名 サイズ LZRC LHA(lh5) 符号化 復号
---------------------------------------------------------
alice29.txt 152,089 59,433 59,117 1.553 0.995
asyoulik.txt 125,179 52,516 52,341 1.385 1.028
cp.html 24,603 8,349 8,384 0.217 0.126
fields.c 11,150 3,116 3,170 0.084 0.051
grammar.lsp 3,721 1,220 1,271 0.034 0.024
kennedy.xls 1,029,744 95,233 198,342 7.510 4.301
lcet10.txt 426,754 160,299 159,558 4.214 2.539
plrabn12.txt 481,861 210,775 210,045 5.575 3.293
ptt5 513,216 49,973 52,305 3.746 1.015
sum 38,240 13,630 13,993 0.363 0.202
xargs.1 4,227 1,732 1,778 0.042 0.026
---------------------------------------------------------
合計 2,810,784 656,276 760,304 24.723 13.600
符号化と復号の単位 : 秒
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
表 : LZRC 符号 (order-0) の結果 [2]
LHA
ファイル名 サイズ 8 k 32 k 64 k lh5(8k) lh6(32k)
---------------------------------------------------------------------
alice29.txt 152,089 59,433 54,482 52,788 59,117 54,266
asyoulik.txt 125,179 52,516 49,046 48,001 52,341 48,915
cp.html 24,603 8,349 7,957 7,957 8,384 8,046
fields.c 11,150 3,116 3,115 3,115 3,170 3,172
grammar.lsp 3,721 1,220 1,220 1,220 1,271 1,272
kennedy.xls 1,029,744 95,233 89,768 87,731 198,342 205,745
lcet10.txt 426,754 160,299 145,727 139,867 159,558 144,419
plrabn12.txt 481,861 210,775 196,357 190,263 210,045 194,957
ptt5 513,216 49,973 51.013 51,530 52,305 53,196
sum 38,240 13,630 12,586 12,593 13,993 12,951
xargs.1 4,227 1,732 1,732 1,732 1,778 1,778
--------------------------------------------------------------------
合計 2,810,784 656,276 613,003 596,797 760,304 728,717
スライド窓が 8 k, 32 k の場合で LHA (lh5, lh6) と比較すると、テキストファイルの圧縮率は LHA よりも少しだけ劣りますが、kennedy.xls の圧縮率はとても高くなりました。処理時間は、バイナリレンジコーダを用いている分だけ、符号化・復号ともに LZSS 符号よりも遅くなりました。ただし、バイナリモデルだけで符号化・復号するよりも、処理時間は高速です。
バイナリファイルの中には、同じデータが一定の間隔で繰り返し現れるものがあります。kennedy.xls もその一つで、このようなファイルでは長さと距離の符号化に structured model を用いることで圧縮率を大幅に向上させることができます。合計では LHA を大幅に上回る圧縮率になりました。
スライド窓を 64 k に増やすと、ほとんどのファイルで圧縮率は向上しますが、なかには ptt5 のように圧縮率が悪くなるファイルもあります。大きなテキストファイルの場合、スライド窓を大きくした方が高い圧縮率になりました。小さなファイルでも圧縮率は低下しないので、バイナリレンジコーダの効果は十分に出ていると思います。
このように、スライド窓を大きくしてバイナリレンジコーダを適用することで、LHA を上回る圧縮率を達成することができます。ここで記号の符号化に「有限文脈モデル」を適用すると、さらに圧縮率を向上させることができます。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
適応型レンジコーダの場合、有限文脈モデルに対応するのは簡単です。次のリストを見てください。
リスト : 出現頻度表の初期化
def init_freq():
global freq_flag, freq_code, freq_pos, freq_len
freq_flag = [AlphaFreq(2), AlphaFreq(2)]
freq_code = [Freq2(256) for _ in range(256)]
freq_len = GammaFreq(MAX_LEN - MIN_LEN + 1)
freq_pos = GammaFreq(1 << POS_BITS)
記号の出現頻度表は配列 freq_code に格納します。それから、有限文脈モデルを適用するのは記号だけではありません。フラグにも有限文脈モデル (order-1) を適用すると圧縮率が向上する場合があります。直前に出力したフラグを変数に記憶しておき、その値によって出現頻度表を選択します。フラグの出現頻度表は配列 freq_flag にセットします。
order-1 で符号化する関数 encode() をリストに示します。
リスト : order-1 の符号化
def encode(fin, fout):
init_freq()
rc = RangeCoder(fout, ENCODE)
s = Slide(fin)
rp = 0
c0 = 0
f0 = 0
while rp < s.data_size:
s.search(rp)
if s.match_len < MIN_LEN:
num = 1
freq_flag[f0].encode(rc, 0)
freq_code[c0].encode(rc, s.buff[rp])
f0 = 0
else:
num = s.match_len
freq_flag[f0].encode(rc, 1)
freq_len.encode(rc, num - MIN_LEN)
freq_pos.encode(rc, rp - s.match_pos - 1)
f0 = 1
for _ in range(num):
c0 = s.buff[rp]
s.insert(rp)
rp += 1
if rp >= s.limit: rp = s.update(rp)
rc.finish()
変数 c0 に直前の記号を、変数 f0 に直前に出力したフラグを記憶します。c0 と f0 は 0 に初期化しておきます。フラグを符号化するときは、freq_flag[f0] で出現頻度表を選択し、符号化したフラグを f0 にセットします。記号を符号化するときは freq_code[c0] で出現頻度表を求めます。あとは、出力した文字をハッシュ表へ登録するときに、直前の記号 c0 を更新するだけです。復号を行う関数 decode() の修正も同じです。
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。
表 : LZRC 符号 (order-1) の結果 (スライド窓 8 k) [1]
ファイル名 サイズ LZRC1 LHA(lh5) 符号化 復号
---------------------------------------------------------
alice29.txt 152,089 54,913 59,117 1.804 1.062
asyoulik.txt 125,179 47,920 52,341 1.610 0.938
cp.html 24,603 8,060 8,384 0.298 0.189
fields.c 11,150 3,112 3,170 0.132 0.101
grammar.lsp 3,721 1,246 1,271 0.083 0.068
kennedy.xls 1,029,744 86,266 198,342 7.580 4.189
lcet10.txt 426,754 146,592 159,558 4.822 2.728
plrabn12.txt 481,861 192,256 210,045 6.330 3.847
ptt5 513,216 47,381 52,305 3.898 1.103
sum 38,240 13,359 13,993 0.452 0.266
xargs.1 4,227 1,739 1,778 0.091 0.076
---------------------------------------------------------
合計 2,810,784 602,844 760,304 27.100 14.567
符号化と復号の単位 : 秒
表 : LZRC 符号 (order-1) の結果 [2]
LHA
ファイル名 サイズ 8 k 32 k 64 k lh5(8k) lh6(32k)
---------------------------------------------------------------------
alice29.txt 152,089 54,913 51,781 50,597 59,117 54,266
asyoulik.txt 125,179 47,920 46,099 45,423 52,341 48,915
cp.html 24,603 8,060 7,717 7,717 8,384 8,046
fields.c 11,150 3,112 3,116 3,116 3,170 3,172
grammar.lsp 3,721 1,246 1,246 1,246 1,271 1,272
kennedy.xls 1,029,744 86,266 73,889 70,144 198,342 205,745
lcet10.txt 426,754 146,592 136,757 132,589 159,558 144,419
plrabn12.txt 481,861 192,256 183,713 179,706 210,045 194,957
ptt5 513,216 47,381 48.148 48,368 52,305 53,196
sum 38,240 13,359 12,442 12,445 13,993 12,951
xargs.1 4,227 1,739 1,739 1,739 1,778 1,778
--------------------------------------------------------------------
合計 2,810,784 602,844 566,647 553,090 760,304 728,717
lzrc (order-0) では MIN_LEN の値を 4 に設定しましたが、lzrc1 (order-1) では 6 に設定します。記号を符号化するバイナリモデルの圧縮性能は order-0 よりも order-1 の方が高いので、MIN_LEN を 6 にした方が LZRC 符号の圧縮率は良くなります。
order-1 の効果はとても大きく、スライド窓が 8 k の場合は lh5 形式を、32 k の場合は lh6 形式を上回る圧縮率になりました。スライド窓を 64 k に増やすと、order-0 と同様にほとんどのファイルで圧縮率は向上しますが、ptt5 のように圧縮率が悪くなるファイルもあります。
大きなテキストファイルの場合、order-1 の効果により圧縮率は order-0 よりも高くなりました。一般に、有限文脈モデルはテキストファイルとの相性が良いので、英文テキストファイルは order-1 よりも order-2 の方が高い圧縮率になります。興味のある方はプログラムを改造してみてください。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
LZSS 符号 はハフマン符号やレンジコーダと組み合わせることで圧縮率を向上させることができました。それでは、LZW 符号 (LZT 符号) の場合はどうでしょうか。
LZW 符号の場合、辞書を大きくすると辞書番号も大きくなります。たとえば、辞書の大きさを 8192 とすると、0 から 8191 までの数値を符号化する必要があります。記号の種類が多くなると、ハフマン符号やレンジコーダを適用しても、効率的に圧縮することは難しくなります。
ところが、大きな数値でも効率的に圧縮できる方法があります。それがバイナリレンジコーダの「γモデル」です。実際に試してみたところ、LZT 符号の圧縮率を向上させることができました。そこで、次はγモデルを用いて LZT 符号の圧縮率を改善してみましょう。
プログラムは次のようになります。
リスト : LZT 符号 (γモデル) の符号化
def encode(fin, fout):
rc = RangeCoder(fout, ENCODE)
freq = GammaFreq(DIC_SIZE)
dic = Dic()
que = Queue()
p = fin.getc()
while True:
c = fin.getc()
if c is None:
freq.encode(rc, p)
break
q = dic.search(p, c)
if q is None:
freq.encode(rc, p)
dic.insert(que, p, c)
p = c
else:
que.delete(q)
que.insert(q)
p = q
rc.finish()
符号化の場合、RangeCoder() で符号化用のレンジコーダを作成し、GammaFreq() でγモデルの出現頻度表を作成します。記号の種類は辞書番号の最大値 DIC_SIZE を指定します。これで 0 から DIC_SIZE - 1 までの数値を符号化することができます。あとは freq.encode() で辞書番号を符号化するだけです。
次は復号を行う関数 decode() です。
リスト : LZT 符号 (γモデル) の復号
def decode(fin, fout, size):
rc = RangeCoder(fin, DECODE)
freq = GammaFreq(DIC_SIZE)
que = Queue()
dic = Dic()
p = freq.decode(rc)
c, i = dic.output(que, p, fout)
size -= i
while size > 0:
q = freq.decode(rc)
if dic.check_code(que, q):
c, i = dic.output(que, q, fout)
dic.insert(que, p, c)
else:
dic.insert(que, p, c)
c, i = dic.output(que, q, fout)
p = q
size -= i
復号の場合は RangeCoder() で復号用のレンジコーダを作成します。γモデルの出現頻度表 GammaFreq() は符号化と同じ記号数で作成します。あとは freq.decode() で辞書番号を復号して、辞書から記号列を復号するだけです。とても簡単ですね。
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。
表 : LZT 符号 + BinaryRangeCoder の結果 [1]
(辞書サイズ 8 k)
ファイル名 サイズ LZTRC LHA(lh5) 符号化 復号
---------------------------------------------------------
alice29.txt 152,089 63,411 59,117 1.242 1.206
asyoulik.txt 125,179 56,323 52,341 1.210 1.109
cp.html 24,603 10,840 8,384 0.276 0.201
fields.c 11,150 4,730 3,170 0.105 0.098
grammar.lsp 3,721 1,707 1,271 0.081 0.038
kennedy.xls 1,029,744 206,102 198,342 5.982 5.784
lcet10.txt 426,754 178,912 159,558 3.581 3.476
plrabn12.txt 481,861 213,732 210,045 4.411 4.153
ptt5 513,216 59,648 52,305 1.642 1.583
sum 38,240 17,806 13,993 0.385 0.339
xargs.1 4,227 2,226 1,778 0.056 0.047
---------------------------------------------------------
合計 2,810,784 815,437 760,304 18.971 18.034
符号化と復号の単位 : 秒
表 : LZT 符号 + BianryRangeCoder の結果 [2]
LHA
ファイル名 サイズ 8 k 32 k 64 k lh5(8k)
-----------------------------------------------------------
alice29.txt 152,089 63,411 60,496 60,508 59,117
asyoulik.txt 125,179 56,323 53,542 53,542 52,341
cp.html 24,603 10,840 10,840 10,840 8,384
fields.c 11,150 4,730 4,730 4,730 3,170
grammar.lsp 3,721 1,707 1,707 1,707 1,271
kennedy.xls 1,029,744 206,102 195,891 195,651 198,342
lcet10.txt 426,754 178,912 162,098 158,546 159,558
plrabn12.txt 481,861 213,732 197,703 193,544 210,045
ptt5 513,216 59,648 58.918 58,916 52,305
sum 38,240 17,806 17,794 17,794 13,993
xargs.1 4,227 2,226 2,226 2,226 1,778
-----------------------------------------------------------
合計 2,810,784 815,437 765,945 758,004 760,304
LZT 符号にγモデルを適用することで圧縮率は確かに向上しましたが、その効果は LZRC 符号 (LZSS 符号 + バイナリレンジコーダ) ほど大きくありません。辞書サイズを 64 k に増やしても、LHA (lh5 形式) より圧縮率が高くなるのは kennedy.xls, lcet10.txt, plrabn12.txt の 3 つだけでした。LZT 符号とγモデルを単純に組み合わせだだけでは、LZ77 符号系の圧縮率を越えるのは難しいようです。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
#
# lzrc0.py : LZSS 符号 + バイナリレンジコーダ (order-0)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from rangecoder2 import *
# 定数
MIN_LEN = 4
MAX_LEN = 256
POS_BITS = 13
# スライド窓
class Slide:
def __init__(self, s):
self.stream = s
self.size = 1 << POS_BITS
self.limit = self.size * 2
self.next_ = [None] * self.size
self.ht = {}
self.too_many_flag = {}
self.buff = [0] * (self.limit + MAX_LEN)
self.data_size = self.fread(0, self.limit + MAX_LEN)
self.match_len = 0
self.match_pos = 0
# データ入力
def fread(self, start, size):
for i in range(size):
c = self.stream.getc()
if c is None: return i
self.buff[start + i] = c
return size
# データ移動
def move_data(self, to, from_, size):
for n in range(size):
self.buff[to + n] = self.buff[from_ + n]
# スライド窓の更新
def update(self, rp):
if self.data_size < self.limit + MAX_LEN: return rp
# buffer update
self.move_data(0, self.size, self.size + MAX_LEN)
n = self.fread(self.size + MAX_LEN, self.size)
self.data_size = self.size + MAX_LEN + n
# hash update
for k, v in list(self.ht.items()):
if v < self.size:
del self.ht[k]
else:
self.ht[k] = v - self.size
#
for x in range(self.size):
v = self.next_[x]
if v == None or v < self.size:
self.next_[x] = None
else:
self.next_[x] = v - self.size
self.too_many_flag.clear()
return rp - self.size
# ハッシュ関数
def hash_value(self, rp):
value = 0
for x in range(MIN_LEN):
value = (value << 8) + self.buff[rp + x]
return value
# データの挿入
def insert(self, rp):
value = self.hash_value(rp)
if value in self.ht:
self.next_[rp & (self.size - 1)] = self.ht[value]
else:
self.next_[rp & (self.size - 1)] = None
self.ht[value] = rp
# データの探索
def search(self, rp):
b = self.buff
value = self.hash_value(rp)
limit = rp - self.size
self.match_len = 0
self.match_pos = 0
offset = 0
while value in self.too_many_flag:
if offset >= MAX_LEN - MIN_LEN or len(b) - (rp + offset) < MIN_LEN:
offset = 0
value = self.hash_value(rp)
break
offset += 1
value = self.hash_value(rp + offset)
#
while True:
count = 0
if value in self.ht:
n = self.ht[value]
else:
n = None
while n is not None and n - offset >= limit:
count += 1
if b[rp + self.match_len] == b[n + self.match_len - offset]:
x = 0
while x < MAX_LEN:
if b[rp + x] != b[n + x - offset]: break
x += 1
if self.match_len < x:
self.match_len = x
self.match_pos = n - offset
if x == MAX_LEN: break
n = self.next_[n & (self.size - 1)]
if count > 256: self.too_many_flag[value] = True
if self.match_len >= offset + MIN_LEN or offset == 0: break
# 再検索
offset = 0
value = self.hash_value(rp)
# データの終端をチェック
if self.match_len >= self.data_size - rp:
self.match_len = self.data_size - rp
# 出現頻度表の初期化
def init_freq():
global freq_flag, freq_code, freq_pos, freq_len
freq_flag = AlphaFreq(2)
freq_code = Freq2(256)
freq_len = GammaFreq(MAX_LEN - MIN_LEN + 1)
freq_pos = GammaFreq(1 << POS_BITS)
# LZRC 符号の符号化
def encode(fin, fout):
init_freq()
rc = RangeCoder(fout, ENCODE)
s = Slide(fin)
rp = 0
while rp < s.data_size:
s.search(rp)
if s.match_len < MIN_LEN:
num = 1
freq_flag.encode(rc, 0)
freq_code.encode(rc, s.buff[rp])
else:
num = s.match_len
freq_flag.encode(rc, 1)
freq_len.encode(rc, num - MIN_LEN)
freq_pos.encode(rc, rp - s.match_pos - 1)
for _ in range(num):
s.insert(rp)
rp += 1
if rp >= s.limit: rp = s.update(rp)
rc.finish()
# LZRC 符号の復号
def decode(fin, fout, size):
init_freq()
rc = RangeCoder(fin, DECODE)
rp = 0
buff = [0] * (1 << POS_BITS)
while size > 0:
if freq_flag.decode(rc):
num = freq_len.decode(rc) + MIN_LEN
pos = freq_pos.decode(rc) + 1
pos = rp - pos
if pos < 0: pos += len(buff)
for _ in range(num):
c = buff[pos]
fout.putc(c)
buff[rp] = c
pos += 1
rp += 1
if pos >= len(buff): pos = 0
if rp >= len(buff): rp = 0
else:
num = 1
c = freq_code.decode(rc)
fout.putc(c)
buff[rp] = c
rp += 1
if rp >= len(buff): rp = 0
size -= num
# 符号化
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='LZRC(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))
#
# lzrc1.py : LZSS 符号 + バイナリレンジコーダ (order-1)
#
# Copyright (C) 2007 Makoto Hiroi
#
import argparse, os.path, time
from rangecoder2 import *
# 定数
MIN_LEN = 6
MAX_LEN = 256
POS_BITS = 16
# スライド窓
class Slide:
def __init__(self, s):
self.stream = s
self.size = 1 << POS_BITS
self.limit = self.size * 2
self.next_ = [None] * self.size
self.ht = {}
self.too_many_flag = {}
self.buff = [0] * (self.limit + MAX_LEN)
self.data_size = self.fread(0, self.limit + MAX_LEN)
self.match_len = 0
self.match_pos = 0
# データ入力
def fread(self, start, size):
for i in range(size):
c = self.stream.getc()
if c is None: return i
self.buff[start + i] = c
return size
# データ移動
def move_data(self, to, from_, size):
for n in range(size):
self.buff[to + n] = self.buff[from_ + n]
# スライド窓の更新
def update(self, rp):
if self.data_size < self.limit + MAX_LEN: return rp
# buffer update
self.move_data(0, self.size, self.size + MAX_LEN)
n = self.fread(self.size + MAX_LEN, self.size)
self.data_size = self.size + MAX_LEN + n
# hash update
for k, v in list(self.ht.items()):
if v < self.size:
del self.ht[k]
else:
self.ht[k] = v - self.size
#
for x in range(self.size):
v = self.next_[x]
if v == None or v < self.size:
self.next_[x] = None
else:
self.next_[x] = v - self.size
self.too_many_flag.clear()
return rp - self.size
# ハッシュ関数
def hash_value(self, rp):
value = 0
for x in range(MIN_LEN):
value = (value << 8) + self.buff[rp + x]
return value
# データの挿入
def insert(self, rp):
value = self.hash_value(rp)
if value in self.ht:
self.next_[rp & (self.size - 1)] = self.ht[value]
else:
self.next_[rp & (self.size - 1)] = None
self.ht[value] = rp
# データの探索
def search(self, rp):
b = self.buff
value = self.hash_value(rp)
limit = rp - self.size
self.match_len = 0
self.match_pos = 0
offset = 0
while value in self.too_many_flag:
if offset >= MAX_LEN - MIN_LEN or len(b) - (rp + offset) < MIN_LEN:
offset = 0
value = self.hash_value(rp)
break
offset += 1
value = self.hash_value(rp + offset)
#
while True:
count = 0
if value in self.ht:
n = self.ht[value]
else:
n = None
while n is not None and n - offset >= limit:
count += 1
if b[rp + self.match_len] == b[n + self.match_len - offset]:
x = 0
while x < MAX_LEN:
if b[rp + x] != b[n + x - offset]: break
x += 1
if self.match_len < x:
self.match_len = x
self.match_pos = n - offset
if x == MAX_LEN: break
n = self.next_[n & (self.size - 1)]
if count > 256: self.too_many_flag[value] = True
if self.match_len >= offset + MIN_LEN or offset == 0: break
# 再検索
offset = 0
value = self.hash_value(rp)
# データの終端をチェック
if self.match_len >= self.data_size - rp:
self.match_len = self.data_size - rp
# 出現頻度表の初期化
def init_freq():
global freq_flag, freq_code, freq_pos, freq_len
freq_flag = [AlphaFreq(2), AlphaFreq(2)]
freq_code = [Freq2(256) for _ in range(256)]
freq_len = GammaFreq(MAX_LEN - MIN_LEN + 1)
freq_pos = GammaFreq(1 << POS_BITS)
# LZRC 符号の符号化 (order-1)
def encode(fin, fout):
init_freq()
rc = RangeCoder(fout, ENCODE)
s = Slide(fin)
rp = 0
c0 = 0
f0 = 0
while rp < s.data_size:
s.search(rp)
if s.match_len < MIN_LEN:
num = 1
freq_flag[f0].encode(rc, 0)
freq_code[c0].encode(rc, s.buff[rp])
f0 = 0
else:
num = s.match_len
freq_flag[f0].encode(rc, 1)
freq_len.encode(rc, num - MIN_LEN)
freq_pos.encode(rc, rp - s.match_pos - 1)
f0 = 1
for _ in range(num):
c0 = s.buff[rp]
s.insert(rp)
rp += 1
if rp >= s.limit: rp = s.update(rp)
rc.finish()
# LZRC 符号の復号 (order-1)
def decode(fin, fout, size):
init_freq()
rc = RangeCoder(fin, DECODE)
rp = 0
c0 = 0
f0 = 0
buff = [0] * (1 << POS_BITS)
while size > 0:
if freq_flag[f0].decode(rc):
num = freq_len.decode(rc) + MIN_LEN
pos = freq_pos.decode(rc) + 1
pos = rp - pos
if pos < 0: pos += len(buff)
for _ in range(num):
c = buff[pos]
fout.putc(c)
c0 = c
buff[rp] = c
pos += 1
rp += 1
if pos >= len(buff): pos = 0
if rp >= len(buff): rp = 0
f0 = 1
else:
num = 1
c = freq_code[c0].decode(rc)
fout.putc(c)
c0 = c
buff[rp] = c
rp += 1
if rp >= len(buff): rp = 0
f0 = 0
size -= num
# 符号化
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='LZRC(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))
#
# lztrc.py : LZT coding + Binary Range Coder
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from rangecoder2 import *
# 定数
DIC_BITS = 16
DIC_SIZE = 1 << DIC_BITS
HEAD = 0
##### LZT 符号 #####
# 双方向リストによるキュー
# 0 がヘッダ, 1 - 255 はダミー
class Queue:
def __init__(self):
self.prev = [None] * DIC_SIZE
self.next_ = [None] * DIC_SIZE
self.prev[HEAD] = HEAD
self.next_[HEAD] = HEAD
# 最後尾に追加
def insert(self, x):
last = self.prev[HEAD]
self.prev[x] = last
self.next_[x] = HEAD
self.next_[last] = x
self.prev[HEAD] = x
# 削除
def delete(self, x):
p = self.prev[x]
q = self.next_[x]
self.next_[p] = q
self.prev[q] = p
# 巡回
def traverse(self):
n = self.next_[HEAD]
while n != HEAD:
yield n
n = self.next_[n]
# 辞書
class Dic:
def __init__(self):
self.sym = [None] * DIC_SIZE
self.parent = [None] * DIC_SIZE
self.child = [0] * DIC_SIZE
self.ht = {}
for x in range(256): self.sym[x] = x
self.num = 256
# 探索
def search(self, n, c):
key = (n, c)
if key in self.ht: return self.ht[key]
return None
# 葉を探す
def search_leaf(self, q):
for x in q.traverse():
if self.child[x] == 0: return x
return None
# 削除
def delete(self, n):
p = self.parent[n]
c = self.sym[n]
del self.ht[(p, c)]
self.child[p] -= 1
# 挿入
def insert(self, q, p, c):
if self.num == DIC_SIZE:
n = self.search_leaf(q)
q.delete(n)
self.delete(n)
else:
n = self.num
self.num += 1
self.sym[n] = c
self.parent[n] = p
self.child[n] = 0
self.child[p] += 1
self.ht[(p, c)] = n
q.insert(n)
# 辞書番号のチェック
def check_code(self, q, n):
if self.num == DIC_SIZE:
return self.search_leaf(q) != n
return n < self.num
# 出力
def output(self, q, n, fout):
if self.parent[n] is None:
fout.putc(n)
return n, 1
else:
m, i = self.output(q, self.parent[n], fout)
fout.putc(self.sym[n])
q.delete(n)
q.insert(n)
return m, i + 1
# LZT 符号の符号化
def encode(fin, fout):
rc = RangeCoder(fout, ENCODE)
freq = GammaFreq(DIC_SIZE)
dic = Dic()
que = Queue()
p = fin.getc()
while True:
c = fin.getc()
if c is None:
freq.encode(rc, p)
break
q = dic.search(p, c)
if q is None:
freq.encode(rc, p)
dic.insert(que, p, c)
p = c
else:
que.delete(q)
que.insert(q)
p = q
rc.finish()
# LZT 符号の復号
def decode(fin, fout, size):
rc = RangeCoder(fin, DECODE)
freq = GammaFreq(DIC_SIZE)
que = Queue()
dic = Dic()
p = freq.decode(rc)
c, i = dic.output(que, p, fout)
size -= i
while size > 0:
q = freq.decode(rc)
if dic.check_code(que, q):
c, i = dic.output(que, q, fout)
dic.insert(que, p, c)
else:
dic.insert(que, p, c)
c, i = dic.output(que, q, fout)
p = q
size -= i
# 符号化
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='LZTRC符号')
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))