前回は Method C のプログラムを作ってファイルを圧縮してみました。今回は前回作成したプログラムを改良してみましょう。最初にエスケープ確率を Method D に変更します。そして、メモリを使い切ったときの対応として、「LRU スキーム」を導入します。
Method D はとても簡単にプログラムできます。記号を符号化・復号するときに、記号の増分値を 2 倍にすればいいわけです。これは出現頻度表を更新するメソッド update の引数に同じ記号を渡すだけで実現できます。
それからもう一つ、記号の増分値 INC を 1.5 倍に増やした Method D' という方法を試してみました。この方法は、メソッド update で引数 c0 の出現頻度を増やすとき、self.inc + self.inc / 2 とするだけで実現できます。エスケープ記号の増分値は self.inc のままです。
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。結果は次にようになりました。
表 : PPM の評価結果 (節の個数 100000, INC = +4)
Method
ファイル名 サイズ C D D' LHA bzip2
--------------------------------------------------------------------
alice29.txt 152,089 42,585 41,671 41,095 59,117 43,202
asyoulik.txt 125,179 39,405 38,646 38,310 52,341 39,569
cp.html 24,603 7,117 7,023 6,998 8,384 7,624
fields.c 11,150 3,008 2,933 2,860 3,170 3,039
grammar.lsp 3,721 1,141 1,127 1,107 1,271 1,283
kennedy.xls 1,029,744 184,738 170,625 169,728 198,342 130,280
lcet10.txt 426,754 106,399 103,788 102,287 159,558 107,706
plrabn12.txt 481,861 143,284 140,254 138,673 210,045 145,577
ptt5 513,216 51,339 50,731 51,309 52,305 49,759
sum 38,240 13,044 12,729 12,641 13,993 12,909
xargs.1 4,227 1,592 1,570 1,561 1,778 1,762
--------------------------------------------------------------------
合計 2,810,784 593,652 571,097 566,569 760,304 542,710
結果を見ると、PPM の圧縮率はエスケープ確率によって大きく左右されることがよくわかります。今回のプログラムでは Method D' の圧縮率が一番高くなりました。特に、テキストファイルとの相性が良いようです。テキストファイルの場合、出現する記号の種類は限られているので、エスケープ確率はそれほど大きくないはずです。記号数の増分値をエスケープ記号よりも増やすことで、エスケープ確率は少し低下するので、テキストファイルの圧縮率が高くなったと思われます。逆に、バイナリファイルでは圧縮率が低下する場合もあります。
今回はテストデータに The Canterbury Corpus だけしか使っていないので、興味のある方はいろいろなデータで試してみてください。
ところで、有限文脈モデルの場合、高次モデルで記号の増分値を増やすと、圧縮率が向上する場合があります。PPM の場合でも効果があるかもしれません。実際に試してみましょう。プログラムの修正は簡単です。クラス Trie のメソッド get_freq で新しい出現頻度表を生成するとき、記号の増分値を次のように設定します。
freq = FreqEsc(INC + 4 * x, LIMIT)
x は次数 (order) - 1 です。この場合、order-2, 3, 4, 5 の増分値は 8, 12, 16, 20 になります。4 を 6 と 8 に増やして試してみたところ、結果は次のようになりました。
表 : PPM の評価結果 (節の個数 100000, Method D')
ファイル名 サイズ 4 * x 6 * x 8 * x LHA bzip2
--------------------------------------------------------------------
alice29.txt 152,089 41,033 41,030 41,027 59,117 43,202
asyoulik.txt 125,179 38,363 38,371 38,376 52,341 39,569
cp.html 24,603 6,986 6,988 6,989 8,384 7,624
fields.c 11,150 2,835 2,834 2,833 3,170 3,039
grammar.lsp 3,721 1,099 1,099 1,099 1,271 1,283
kennedy.xls 1,029,744 149,502 145,031 141,109 198,342 130,280
lcet10.txt 426,754 102,069 102,065 102,074 159,558 107,706
plrabn12.txt 481,861 138,716 138,741 138,765 210,045 145,577
ptt5 513,216 51,735 51,936 52,144 52,305 49,759
sum 38,240 12,567 12,557 12,540 13,993 12,909
xargs.1 4,227 1,557 1,557 1,557 1,778 1,762
--------------------------------------------------------------------
合計 2,810,784 546,480 542,209 538,513 760,304 542,710
高次モデルの増分値を増やすことで、kennedy.xls の圧縮率は大幅に向上しました。その他のファイルでは、圧縮率が少し良くなる場合もありますし、逆に少し悪くなる場合もあります。有限文脈モデルのように、大きな効果はないようです。それでも、kennedy.xls の圧縮率は向上するので、ほかにも効果があるファイルがあるかもしれません。興味のある方はいろいろなデータで試してみてください。
今まで作成したプログラムは、メモリを使い切った時点で有限文脈モデル (トライ) を固定して、あとはそのままのモデルを使ってデータを圧縮しました。ところが、この方法では不都合な場合もあります。
たとえば、tar などのアーカイバで複数のファイルをひとつにまとめた場合、データの種類が途中で変化することがあります。この場合、モデルを固定するとデータの変化についていけないので、圧縮率が低下することが予想されます。そこで、実際に The Canterbury Corpus の 11 ファイルを tar でまとめたファイルを圧縮してみました。結果は次のようになりました。
表 : canterbury.tar の評価結果
ファイル名 サイズ 圧縮後 符号化 復号
-------------------------------------------------
Canterbury 2,821,120 721,495 213.73 267.24
# 符号化と復号の単位 : 秒
実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
圧縮率は大きく低下すると思っていたのですが、予想以上に圧縮率が良かったのには驚きました。それでも、データの変化に対応できれば、もう少し圧縮率は良くなるはずです。そこで、メモリを使い切ったときの対応に「LRU スキーム」を導入してみましょう。
LRU スキームは、長い間使われていない (最長時間未使用 : Least Recently Used) 節を取り除くことで、トライに空きスペースを作る操作のことです。PPM に LRU スキームを適用すると、符号化と復号に時間がかかることになりますが、少ないメモリでも高い圧縮率を期待することができます。また、データの局所的な偏在も反映することが可能になります。
LRU スキームは LZT 符号のときに「キュー (queue) 」を使って実装しました。今回のプログラムも LZT 符号のときに作成したキュー (Queue) を使うことにします。詳しい説明は拙作のページ LZT 符号 をお読みくださいませ。
それではプログラムを作りましょう。次のリストを見てください。
リスト : トライの定義
class Trie:
def __init__(self):
self.sym = [None] * TRIE_SIZE
self.freq = [None] * TRIE_SIZE
self.parent = [None] * TRIE_SIZE
self.child = [0] * TRIE_SIZE
self.ht = {}
for x in xrange(256):
self.sym[x] = x
self.freq[x] = FreqEsc(INC, LIMIT) # order-1
self.num = 256
トライから節を削除する場合、その親節が必要になります。このため、親節を表す配列 parent を追加します。ただし、削除できる節は「葉」だけであり、トライの途中から節を削除することはできません。ハッシュを使ってトライを実装する場合、節が「葉」なのかすぐに判別することができません。そこで、子の個数を配列 child で管理します。たとえば、n に子を追加するときは child[n] を +1 します。n の子を削除するときは child[n] を -1 します。child[n] が 0 の場合、n は葉であることがすぐにわかります。
次は、キューの先頭から葉を探すメソッド search_leaf と削除するメソッド delete を作ります。
リスト : 葉の探索と削除
# 探索
def search_leaf(self, que):
for x in que.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
search_leaf の引数 que は LRU スキームで使用するキューです。葉を探す処理は簡単です。キューのメソッド traverse を使って、節 x を取り出します。child[x] が 0 ならば return で x を返します。見つからない場合は None を返していますが、必ず見つかるはずなので、raise でエラーを送出してもいいでしょう。
delete の引数 n は削除する節です。まず、parent[n] と sym[n] から親節と記号を求めて、変数 p, c にセットします。そして、ハッシュ ht からキー (p, c) を削除して、child[p] を -1 します。これでトライから節 n を削除することができます。
最後に、出現頻度表を取得するメソッド get_freq を修正します。
リスト : 出現頻度表の取得
def get_freq(self, buff, prev_code, que):
n = prev_code[0]
buff.append(self.freq[n]) # order-1 をセット
for x in xrange(1, MAX_ORDER):
c = prev_code[x]
m = self.search(n, c)
if m is None:
# Trie に追加する
m = self.num
if m >= TRIE_SIZE:
m = self.search_leaf(que)
self.delete(m)
que.delete(m)
else:
self.num += 1
freq = FreqEsc(INC + 8 * x, LIMIT)
self.sym[m] = c
self.parent[m] = n
self.freq[m] = freq
self.child[m] = 0
self.child[n] += 1
self.ht[(n, c)] = m
que.insert(m)
else:
freq = self.freq[m]
que.delete(m)
que.insert(m)
# 出現頻度表を追加する
buff.append(freq)
n = m
引数 que は LRU スキーム用のキューです。新しい節をトライに追加するとき、self.num >= TRIE_SIZE の場合は空きエリアがありません。もっとも使われていない「葉」を search_leaf で探します。そして、見つけた葉 m をトライとキューから削除します。出現頻度表は新しく生成して freq にセットします。あとは節 m をトライとキューに追加するだけです。
節を見つけた場合、その節をメソッド delete で双方向リストから削除し、メソッド insert で双方向リストの最後尾へ移動します。これで節を LRU スキームで管理することができます。
あとはとくに難しいところはないでしょう。詳細は プログラムリスト１ をお読みくださいませ。
それでは、実際にファイルを圧縮してみましょう。最初に The Canterbury Corpus をアーカイバ tar でまとめた canterbury.tar の結果を表に示します。
表 : canterbury.tar の評価結果
PROG サイズ 圧縮後 符号化 復号
-----------------------------------------------
PPM 2,821,120 721,495 213.73 267.24
PPM(LRU) 2,821,120 531,965 275.57 303.90
# 符号化と復号の単位 : 秒
実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
LRU スキームの方が高い圧縮率になりました。LRU スキームは PPM でも大きな効果を発揮していることがわかります。次は The Canterbury Corpus の評価結果を表に示します。
表 : PPM の評価結果
(節の個数 100000, LRU スキーム, Method D')
ファイル名 サイズ PPM 符号化 復号 LHA bzip2
------------------------------------------------------------------
alice29.txt 152,089 41,027 16.15 18.12 59,117 43,202
asyoulik.txt 125,179 38,376 14.82 16.57 52,341 39,569
cp.html 24,603 6,989 3.27 3.69 8,384 7,624
fields.c 11,150 2,833 1.27 1.42 3,170 3,039
grammar.lsp 3,721 1,099 0.52 0.57 1,271 1,283
kennedy.xls 1,029,744 128,740 122.90 133.40 198,342 130,280
lcet10.txt 426,754 101,808 39.63 44.38 159,558 107,706
plrabn12.txt 481,861 138,771 45.57 51.04 210,045 145,577
ptt5 513,216 52,126 38.38 41.59 52,305 49,759
sum 38,240 12,540 5.56 6.21 13,993 12,909
xargs.1 4,227 1,557 0.70 0.78 1,778 1,762
------------------------------------------------------------------
合計 2,810,784 525,866 288.77 317.77 760,304 542,710
# 符号化と復号の単位 : 秒
実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
LRU スキームの効果により kennedy.xls の圧縮率は大幅に向上しました。LRU スキームの効果はとても高いことがわかります。そうはいっても、バイナリファイルが苦手であることに変わりはありませんね。また、符号化・復号の処理も大変遅くなりました。LRU スキームを行っているので、その分だけ時間がかかるのは仕方がないでしょう。
それでは、LRU スキームを適用さえすれば、節の個数は少なくても高い圧縮率になるのでしょうか。これはファイルの大きさによって変わると思われます。そこで、The Canterbury Corpus (11 ファイル) を tar でまとめたファイル Canterbury と The Large Corpus を圧縮してみました。実行結果は次のようになりました。
表 : PPM の評価結果 (LRU スキーム, Method D')
節の個数
ファイル名 サイズ 50,000 100,000 150,000 bzip2
--------------------------------------------------------------------
bible.txt 4,047,392 805,297 793,452 792,699 845,623
Canterbury 2,821,120 535,199 531,962 532,795 568,468
e.coli 4,638,690 1,129,469 1,129,469 1,129,469 1,251,004
world192.txt 2,473,400 502,988 474,209 464,949 489,583
--------------------------------------------------------------------
合計 13,980,602 2,972,953 2,929,092 2,919,912 3,154,678
大きなテキストファイル (bible.txt, world192.txt) の場合、節の個数を増やすと圧縮率は向上しました。ところが Canterbury のように、節の個数を増やしても圧縮率が向上しない場合もあります。また、e.coli は記号の種類が少ないデータで、使用する節の個数はとても少なく、PPM では高い圧縮率になります。PPM と相性の良いデータといえるでしょう。
PPM の場合、ある程度のメモリを確保できれば、LRU スキームを適用することにより、大きなファイルでも高い圧縮率を達成することができるようです。それにしても、基本的な PPM だけでここまで高い圧縮率を達成できるとは驚きました。PPM の改良版である PPM* を使った圧縮ツールが、極めて高い圧縮率をたたき出しているのも納得できます。
今回のプログラムは、テキストファイルであれば bzip2 を越える圧縮率を達成していますが、ブロックソートも負けてはいません。ブロックソートの圧縮率はバッファサイズで大きく変化します。bzip2 のバッファサイズは最大で 900 k byte までしか設定できません。そこで、拙作のページ ブロックソート [2] で作成した「ブロックソート 0-1-2 coding 混合法」でファイルを圧縮してみました。結果は次のようになりました。
表 : ブロックソートの評価結果
(bsrc = BlockSorting + MTF-2 + 0-1-2 coding 混合法)
PPM
ファイル名 サイズ (150,000) bzip2 bsrc
---------------------------------------------------------
bible.txt 4,047,392 792,699 845,623 760,899
Canterbury 2,821,120 532,795 568,468 518,815
e.coli 4,638,690 1,129,469 1,251,004 1,158,098
world192.txt 2,473,400 464,969 489,583 413,097
---------------------------------------------------------
合計 13,980,602 2,919,912 3,154,678 2,850,909
e.coli の圧縮率は PPM にかないませんが、それ以外のファイルは PPM よりも高い圧縮率になりました。ブロックソート法も優秀な圧縮アルゴリズムであることがよくわかります。ただし、バッファサイズを大きくするとブロックソートに時間がかかるようになります。それでも、今回のテストでは PPM よりも高速です。Canterbury の場合、符号化で 118 秒、復号で 90.3 秒でした。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
# coding: utf-8
#
# ppmfreq.py : 適応型レンジコーダ用の出現頻度表
#
# Copyright (C) 2007 Makoto Hiroi
#
# 定数
GR = 16
ESC = 256
CHAR_SIZE = 256
# ESC 記号付き出現頻度表
class FreqEsc:
def __init__(self, inc, limit):
self.sym = []
self.inc = inc
self.limit = limit
self.count = [0] * (ESC + 1)
self.count[ESC] = 1
self.count_group = [0] * ((ESC + 1) / GR + 1)
self.count_group[ESC/GR] = 1
self.sum = 1
self.prev = 0
# 出現頻度表の更新
def update(self, c0, c1 = None):
a = self.inc + self.inc / 2 # Method D'
self.count[c0] += a
self.count_group[c0 / GR] += a
self.sum += a
self.prev = c0
if c1 is not None:
self.count[c1] += self.inc
self.count_group[c1 / GR] += self.inc
self.sum += self.inc
if self.sum >= self.limit:
n = 0
for x in xrange(len(self.count_group)):
self.count_group[x] = 0
for x in xrange(len(self.count)):
if self.count[x] > 0:
self.count[x] = (self.count[x] >> 1) | 1
self.count_group[x / GR] += self.count[x]
n += self.count[x]
self.sum = n
# 符号化
def encode(self, rc, c, exclusion):
# 記号の累積度数を求める
def cumul(c):
n = 0
for x in xrange(c/GR): n += count_group[x]
for x in xrange((c/GR)*GR, c):
if x not in exclusion: n += self.count[x]
return n
#
count_group = self.count_group[:]
sum = self.sum
for x in exclusion:
count_group[x/GR] -= self.count[x]
sum -= self.count[x]
temp = rc.range / sum
rc.low += cumul(c) * temp
rc.range = self.count[c] * temp
rc.encode_normalize()
# 復号
def decode(self, rc, exclusion):
# 記号の探索
def search_code(value):
n = 0
for x in xrange(len(count_group)):
if value < n + count_group[x]: break
n += count_group[x]
for c in xrange(x*GR, len(self.count)):
if c not in exclusion:
if value < n + self.count[c]: break
n += self.count[c]
return c, n
#
count_group = self.count_group[:]
sum = self.sum
for x in exclusion:
count_group[x/GR] -= self.count[x]
sum -= self.count[x]
#
temp = rc.range / sum
c, num = search_code(rc.low / temp)
rc.low -= temp * num
rc.range = temp * self.count[c]
rc.decode_normalize()
return c
# order-(-1) 用の出現頻度表
class Freq(FreqEsc):
def __init__(self, inc, limit):
self.inc = inc
self.limit = limit
self.count = [1] * CHAR_SIZE
self.count_group = [GR] * (CHAR_SIZE / GR)
self.sum = CHAR_SIZE
self.prev = 0
# coding: utf-8
#
# ppm_lru.py : PPM のテスト
#
# Copyright (C) 2007 Makoto Hiroi
#
import time, sys, getopt, os.path
from rangecoder import *
from ppmfreq import *
# 定数
MAX_ORDER = 5
INC = 4
LIMIT = 0x4000
TRIE_SIZE = 100000
HEAD = 0
##### 双方向リストによるキュー #####
class Queue:
def __init__(self):
# 0 - 255 はキューに登録しない
self.prev = [None] * TRIE_SIZE
self.next = [None] * TRIE_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]
##### Trie #####
class Trie:
def __init__(self):
self.sym = [None] * TRIE_SIZE
self.freq = [None] * TRIE_SIZE
self.parent = [None] * TRIE_SIZE
self.child = [0] * TRIE_SIZE
self.ht = {}
for x in xrange(256):
self.sym[x] = x
self.freq[x] = FreqEsc(INC, LIMIT) # order-1
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, que):
for x in que.traverse():
if self.child[x] == 0: return x
return None
# 削除
def delete(self, n):
c = self.sym[n]
p = self.parent[n]
del self.ht[(p, c)]
self.child[p] -= 1
# 出現頻度表の取得
def get_freq(self, buff, prev_code, que):
n = prev_code[0]
buff.append(self.freq[n]) # order-1 をセット
for x in xrange(1, MAX_ORDER):
c = prev_code[x]
m = self.search(n, c)
if m is None:
# Trie に追加する
m = self.num
if m >= TRIE_SIZE:
m = self.search_leaf(que)
self.delete(m)
que.delete(m)
else:
self.num += 1
freq = FreqEsc(INC + 8 * x, LIMIT)
self.sym[m] = c
self.parent[m] = n
self.freq[m] = freq
self.child[m] = 0
self.child[n] += 1
self.ht[(n, c)] = m
que.insert(m)
else:
freq = self.freq[m]
que.delete(m)
que.insert(m)
# 出現頻度表を追加する
buff.append(freq)
n = m
##### 出現頻度表 #####
trie = Trie() # order-1 - MAX_ORDER
freq0 = FreqEsc(INC, LIMIT) # order-0
freq_1 = Freq(INC, LIMIT) # order-(-1)
#
def read_file(fin):
while True:
c = getc(fin)
if c is None: break
yield c
# PPM による符号化
def encode(fin, fout):
rc = RangeCoder(fout, ENCODE)
que = Queue()
prev_code = [0] * MAX_ORDER
exclusion = set()
for x in read_file(fin):
exclusion.clear()
buff = [freq_1, freq0]
trie.get_freq(buff, prev_code, que)
for i in xrange(MAX_ORDER + 1, -1, -1):
freq = buff[i]
if freq.count[x] == 0:
freq.encode(rc, ESC, exclusion)
freq.update(x, ESC)
exclusion.update(freq.sym)
freq.sym.append(x)
else:
freq.encode(rc, x, exclusion)
freq.update(x, x)
break
#
prev_code.pop()
prev_code.insert(0, x)
rc.finish()
# PPM による復号
def decode(fin, fout, size):
rc = RangeCoder(fin, DECODE)
que = Queue()
prev_code = [0] * MAX_ORDER
exclusion = set()
for _ in xrange(size):
exclusion.clear()
buff = [freq_1, freq0]
trie.get_freq(buff, prev_code, que)
for i in xrange(MAX_ORDER + 1, -1, -1):
freq = buff[i]
c = freq.decode(rc, exclusion)
if c == ESC:
exclusion.update(freq.sym)
else:
for x in xrange(MAX_ORDER + 1, i, -1):
buff[x].update(c, ESC)
buff[x].sym.append(c)
freq.update(c, c)
break
#
putc(fout, c)
prev_code.pop()
prev_code.insert(0, c)
# 符号化
def encode_file(name1, name2):
size = os.path.getsize(name1)
infile = open(name1, "rb")
outfile = open(name2, "wb")
putc(outfile, (size >> 24) & 0xff)
putc(outfile, (size >> 16) & 0xff)
putc(outfile, (size >> 8) & 0xff)
putc(outfile, size & 0xff)
if size > 0: encode(infile, outfile)
infile.close()
outfile.close()
# 復号
def decode_file(name1, name2):
infile = open(name1, "rb")
outfile = open(name2, "wb")
size = 0
for _ in xrange(4):
size = (size << 8) + getc(infile)
if size > 0: 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)
print trie.num