はじめに
今回は適応型レンジコーダの高速化について説明します。
●適応型レンジコーダの高速化
最初に Rick さんから教えてもらった方法を紹介します。Rick さんのプログラムは線形探索を改良したものです。次のリストを見てください。
リスト : 出現頻度表の初期化と更新
# 定数
GR = 16
# 出現頻度表
class Freq:
def __init__(self, size):
self.size = size
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] += 1
self.count_group[c // GR] += 1
self.sum_ += 1
if self.sum_ >= MIN_RANGE:
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
Rick さんの改良方法は記号を GR (16) 個ずつのグループに分けて、グループの出現頻度表 count_group を用意するところがポイントです。この配列 count_group を使って、記号の累積度数を高速に求めることができます。
符号化で累積度数を求める処理は次のようになります。
リスト : 記号の累積度数を求める
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
たとえば、記号 c の値が 88 とすると、グループは 5 になります。この場合、記号 79 (= 5 * 16 - 1) までの累積度数は count_group[0] から count_group[4] までの値を足し算するだけで求めることができます。あとは count[80] から count[87] までの値を足し算すれば、記号 c (88) の累積度数を求めることができます。今までの方法だと繰り返しの回数が 87 回にもなりますが、今回の方法では 5 + 8 = 13 回ですみます。
復号も同様に配列 count_group を使って高速化することができます。次のリストを見てください。
リスト : 記号の復号
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
最初に count_group を使って記号のグループ番号を復号します。変数 n にグループの累積度数を求めながら、復号するグループ番号を線形探索しています。次に記号を復号します。グループの先頭記号から順番に累積度数を求めながら、復号する記号を線形探索します。
あとのプログラムは簡単なので説明は割愛いたします。詳細は プログラムリスト１ をお読みください。
●評価結果
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus で、実行時間を計測してみましょう。結果は次にようになりました。
表 : 高速化(1) の実行結果
従来版 高速化(1)
ファイル名 サイズ 符号化 復号 符号化 復号
-------------------------------------------------------
alice29.txt 152,089 1.219 2.239 0.516 0.651
asyoulik.txt 125,179 1.045 1.839 0.458 0.536
cp.html 24,603 0.197 0.363 0.093 0.115
fields.c 11,150 0.083 0.149 0.040 0.047
grammar.lsp 3,721 0.026 0.051 0.013 0.017
kennedy.xls 1,029,744 3.469 5.096 2.736 3.266
lcet10.txt 426,754 3.574 6.589 1.416 1.816
plrabn12.txt 481,861 3.968 7.060 1.574 2.043
ptt5 513,216 1.458 2.289 1.122 1.360
sum 38,240 0.239 0.381 0.120 0.163
xargs.1 4,227 0.033 0.070 0.015 0.022
-------------------------------------------------------
合計 2,810,784 15.131 26.126 8.103 10.036
符号化と復号の単位 : 秒
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
どのファイルでも実行時間は速くなりました。特に英文テキストの場合、改良の効果は大きく、2 倍から 3 倍ほど高速になりました。それでも、静的符号化に比べると遅くなるのは仕方がないでしょう。このように、Rick さんの改良は抜群の効果を発揮していて、とても優れた方法だと思います。Rick さんに感謝いたします。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
●二分木を使った高速化
次は mij4x さんの「二分木を使った高速化」を説明します。簡単な例として、記号が 8 種類 (0 - 7) の場合を考えてみましょう。二分木を使う場合、二分木の葉 (外部ノード) に記号の出現頻度を格納します。記号の値を基準にして二分木を構成すると、下図のようになります。
葉は左から記号の順番で並べます。記号が節の記号よりも小さい場合は左部分木をたどり、そうでなければ右部分木をたどります。ここで、節に左部分木の出現頻度の合計値を格納しておくと、記号の累積度数を簡単に求めることができます。次の図を見てください。
上図では、節と葉を記号の値で表しています。節の (N) は左部分木の出現頻度の合計値を表します。記号の出現頻度を {8, 7, 6, 5, 4, 3, 2, 1} とすると、節 4 の値は葉 0 から 3 までの合計値 26 になります。節 2 の場合は葉 0 と 1 の合計値なので 15 になります。節 1 は葉 0 の値 8 になります。
記号の累積度数を求める場合、葉に到達するまで二分木をたどります。ここで、右部分木をたどるときに出現頻度の合計値 N を足し算していくと、記号の累積度数を求めることができます。たとえば、記号 5 の累積度数を求めてみましょう。最初に変数 sum を 0 に初期化して、節 4 と記号 5 を比較します。記号の方が大きいので右部分木をたどります。このとき、節 4 の値 26 を変数 sum に加算します。
次に、節 6 と比較します。今度は記号の方が小さいので左部分木をたどります。このときは出現頻度の合計値を変数 sum に加算しません。その次に、節 5 と比較します。この場合は右部分木をたどるので 4 を加算して sum の値は 30 になります。ここで葉 5 に到達したので、求める累積度数の値は 30 になります。
更新処理も簡単です。次の図を見てください。
実は、累積度数を求めるとき、節に格納されている出現頻度の合計値もいっしょに更新することができます。左部分木をたどる場合、更新する記号はその部分木にあります。記号の出現頻度が一つ増えると、その部分木の出現頻度の合計値も一つ増えますね。つまり、左部分木をたどるとき、出現頻度の合計値を一つ増やせばよいのです。
たとえば、記号が 2 の場合を考えてみましょう。節 4 では左部分木をたどるので、合計値を +1 します。節 2 は右部分木をたどるので値を増やしません。節 3 で左部分木をたどるので、合計値を +1 します。これで、出現頻度の合計値を更新することができます。
このように、二分木を使って累積度数の計算と更新処理を行うことができます。記号の種類を N とすると、木の高さは log2 N になります。したがって、記号が 1 byte (0 - 255) の場合、節を 8 回たどるだけで累積度数の計算と更新処理を行うことができるのです。mij4x さんのプログラムは、二分木の代わりに配列と二分探索を使って高速な処理を実現しています。
●プログラムの作成
それではプログラムを作りましょう。mij4x さんのプログラムは二分探索を使っていますが、ここでは ヒープ のように配列を二分木に見立ててプログラムを作ることにします。次の図を見てください。
内部ノードを配列 count_sum で、外部ノードを配列 count で表します。たとえば、記号が 8 種類 (0 - 7) の場合、count_sum の大きさは 8 - 1 = 7 になります。節の親子関係は次に示す式で表すことができるので、二分木をたどる処理は簡単です。
節 N : 左の子 : 2 * N + 1 右の子 : 2 * N + 2 親 : (N - 1) / 2
記号数を N とすると、葉の番号は記号に N - 1 を足した値になります。上図の場合、記号 4 は葉 11 に対応し、その親は (14 - 1) / 2 = 5 になります。節 5 の親は 2 で、節 2 の親はルートの 0 になります。
最初に出現頻度表と頻度の更新処理を作ります。
リスト : 出現頻度表の初期化と更新
class Freq:
def __init__(self, size):
self.size = size
self.count = [0] * size
self.count_sum = [0] * (size - 1)
self.sum_ = 0
for x in range(size): self.put_value(x, 1)
# 頻度の更新
def put_value(self, c, n):
node = c + self.size - 1
self.count[c] += n
self.sum_ += n
while node > 0:
parent = (node - 1) // 2
if node & 1:
# 左の子
self.count_sum[parent] += n
node = parent
メソッド put_value() は出現頻度表の初期化と更新処理に使います。記号 c の出現頻度と合計値 sum_ を +n するとともに、count_sum の値を更新します。c から葉の番号を求めて node にセットし、ルート方向へ木をたどります。node の親 parent は (node - 1) / 2 で求めることができます。そして、parent の子 node が奇数の場合、node は左の子なので count_sum[parent] を +n します。
次は記号の累積度数を求めるメソッド cumul() を作ります。
リスト : 記号の累積度数を求める
def cumul(self, c):
n = 0
node = c + self.size - 1
while node > 0:
parent = (node - 1) // 2
if node & 1 == 0:
# 右の子
n += self.count_sum[parent]
else:
# 左の子
self.count_sum[parent] += 1
node = parent
return n
cumul() は累積度数を求めると同時に count_sum の値を更新します。木をたどる処理は put_value() と同じです。node が parent の右の子であれば、累積度数 n に count_sum[parent] を加算します。左の子の場合は出現頻度の合計値 count_sum[parent] を +1 します。最後に累積度数 n を返します。
最後に、復号処理で記号を探索する関数 search_code() を作ります。
リスト : 記号の復号
def decode(self, rc):
# 記号の探索
def search_code(value):
n = 0
node = 0
node_size = self.size - 1
while node < node_size:
if value < n + self.count_sum[node]:
# 左の子をたどる
self.count_sum[node] += 1
node = 2 * node + 1
else:
# 右の子をたどる
n += self.count_sum[node]
node = 2 * node + 2
return node - node_size, 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
内部関数 search_code() は二分木をルートから葉の方向へたどり、累積度数 n を求めながら記号を探索します。value が count_sum[node] + n より小さい場合、求める記号は左部分木にあります。そうでなければ右部分木にあります。左部分木をたどる場合は、count_sum[node] を +1 して count_sum を更新します。右部分木をたどる場合は、n に count_sum[node] を加算して累積度数を求めます。node が node_size 以上になったら葉に到達しました。記号 node - node_size とその累積度数 n を返します。
あとのプログラムは簡単なので説明は割愛いたします。詳細は プログラムリスト２ をお読みください。
●評価結果
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus で、実行時間を計測してみましょう。結果は次にようになりました。
表 : 二分木を使った高速化の実行結果
従来版 高速化(1) 高速化(2)
ファイル名 サイズ 符号化 復号 符号化 復号 符号化 復号
-----------------------------------------------------------------------
alice29.txt 152,089 1.219 2.239 0.516 0.651 0.575 0.577
asyoulik.txt 125,179 1.045 1.839 0.458 0.536 0.469 0.490
cp.html 24,603 0.197 0.363 0.093 0.115 0.103 0.098
fields.c 11,150 0.083 0.149 0.040 0.047 0.043 0.046
grammar.lsp 3,721 0.026 0.051 0.013 0.017 0.015 0.017
kennedy.xls 1,029,744 3.469 5.096 2.736 3.266 3.882 3.940
lcet10.txt 426,754 3.574 6.589 1.416 1.816 1.662 1.639
plrabn12.txt 481,861 3.968 7.060 1.574 2.043 1.872 1.797
ptt5 513,216 1.458 2.289 1.122 1.360 1.736 1.853
sum 38,240 0.239 0.381 0.120 0.163 0.158 0.154
xargs.1 4,227 0.033 0.070 0.015 0.022 0.017 0.017
-----------------------------------------------------------------------
合計 2,810,784 15.131 26.126 8.103 10.036 10.532 10.628
符号化と復号の単位 : 秒
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
高速化 (1) は Rick さんの改良方法、高速化 (2) は mij4x さんの改良方法の結果です。二分木を使った効果はとても高く、従来版に比べてとても高速になりました。符号化の場合、高速化 (1) よりも少し遅くなりますが、テキストファイルの場合、復号は高速化 (1) よりも少し速くなるようです。
それから、二分木を使った方法は、記号の種類を N とすると、累積度数の計算と更新処理が log2 N に比例する時間で済むという特徴があります。たとえば、記号の種類が 512 に増えても、累積度数の計算と更新処理は 9 回の繰り返しですみます。とても素晴らしい方法だと思います。mij4x さんに感謝いたします。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
●Binary Indexed Tree
次は Binary Indexed Tree (BIT) という方法を取り上げます。Yuta Mori さん によると、『累積度数の取得・更新なら、P. Fenwick氏のBinary Indexed Tree (BIT)という方法が比較的高速』 とのことです。Yuta Mori さんのプログラムは Binary Indexed Treeの二分探索処理 で公開されています。今回は Yuta Mori さんのプログラムを参考に BIT を python でプログラムしてみましょう。
BIT は二分木をベースにした方法です。簡単な例として、記号の種類が 16 (0 - 15) の場合を考えてみましょう。BIT は下図のように二分木を構成します。
BIT の場合、二分木の節に記号を対応させます。ただし、記号 0 は二分木の中に入れません。そして、節には記号の出現頻度を格納するのではなく、左部分木にある記号の出現頻度とその節の記号の出現頻度の合計値を格納します。たとえば、記号の出現頻度を 0 から順番に {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} とすると、BIT の各節の値は次のようになります。
記号 0 と「葉」にあたる節はその記号の出現頻度を表します。BIT の場合、奇数の記号は葉になります。葉以外の節は、左部分木にある記号の出現頻度の合計値にその節の記号の出現頻度を足した値を保持します。たとえば、節 10 の値は記号 9 と記号 10 の出現頻度を足した 21 になります。節 12 の値は、記号 9, 10, 11 と記号 12 の出現頻度を足した 46 になります。節 8 は記号 1 から 8 の出現頻度の合計 44 になります。このように二分木を構成すると、記号の出現頻度と累積度数を簡単に求めることができます。
●累積度数の求め方
それでは、記号の累積度数を求めてみましょう。記号 12 の累積度数は記号 0 から 11 までの出現頻度の合計値になります。BIT の場合、記号 1 から 11 までの出現頻度の合計値は、節 11 からルート方向に木をたどり、記号 11 以下の節の値を足し算すると求めることができます。
この場合、経路は 11 - 10 - 12 - 8 で、足し算する節は 11, 10, 8 になります。節 11 は記号 11 の出現頻度、節 10 は記号 9, 10 の出現頻度の合計値、節 8 は記号 1 - 8 の出現頻度の合計値なので、これで記号 1 - 11 の出現頻度の合計値を求めることができます。あとは、記号 0 の出現頻度を足し算すれば、累積度数を求めることができます。
BIT の場合、次の式を使って値を足し算する節を求めることができます。
def BACKWARD(c): return c & (c - 1)
実際に計算してみると次のようになります。
1 : 1 2 : 2 3 : 3 2 4 : 4 5 : 5 4 6 : 6 4 7 : 7 6 4 8 : 8 9 : 9 8 10 : 10 8 11 : 11 10 8 12 : 12 8 13 : 13 12 8 14 : 14 12 8 15 : 15 14 12 8
上図の二分木をたどってみてください。同じ結果になります。このように、簡単な式で節をたどることができるとはちょっと驚きました。式についての説明は割愛いたしますので、興味のある方は P. Fenwick 氏 の論文 A New Data Structure for Cumulative Probability Tables (PDF) をお読みください。
累積度数を求めるプログラムは次のようになります。
リスト : 累積度数を求める
def cumul(self, c):
n = 0
if c > 0:
n = self.count[0]
# c - 1 までの頻度を加算する
c -= 1
while c > 0:
n += self.count[c]
c = c & (c - 1) # BACKWARD
return n
変数 n に記号 0 の累積度数 0 をセットします。そのあと、BACKWARD で節をたどりながら、sum に節の値を加算していきます。これで記号 c の累積度数を求めることができます。
●出現頻度の求め方
記号の出現頻度も簡単に求めることができます。記号 0 と記号が奇数の場合は、節の値をそのまま返せばいいですね。その他の場合、記号 c の累積度数から記号 c - 1 の累積度数を引き算すれば、記号 c の出現頻度を求めることができます。たとえば、記号 12 の出現頻度を求めてみましょう。次の式を見てください。
12の累積度数 - 11の累積度数 = ([12] + [8] + [0]) - ([11] + [10] + [8] + [0]) = [12] - [11] - [10] = 46 - 12 - 21 = 13
このように、節 12 の次の節 8 以下の節は共通になるので計算する必要はありません。したがって、節 12 の値から節 11 と 10 の値を引き算すればいいわけです。これをプログラムすると次のようになります。
リスト : 記号の出現頻度を求める
def get_prob(self, c):
val = self.count[c]
if c > 0 and c & 1 == 0:
p = c & (c - 1) # BACKWARD
c -= 1
while c != p:
val -= self.count[c]
c = c & (c - 1) # BACKWARD
return val
節の値を変数 val にセットします。記号 0 と奇数の記号は val をそのまま返します。それ以外の場合、記号 c の次の節を変数 p にセットし、c - 1 の節の値を val から引き算します。あとは、BACKWARD で節をたどりながら、節の値を val から引き算すればいいわけです。c が p と等しくなったら for ループを終了して val を返します。
●出現頻度の更新
更新処理も簡単です。たとえば、記号 11 の出現頻度を +1 する場合、節 11 からルート方向に木をたどり、記号 11 以上の節の値を +1 します。この場合、経路は 11 - 10 - 12 - 8 で、+1 する節は 11, 12 になります。節 11 は記号 11 の出現頻度、節 12 は記号 9 から 12 の出現頻度の合計値で、他の節には記号 11 の値は含まれていません。節 11 と 12 の値を + 1 すればいいわけです。
BIT の場合、次の式を使って更新する節を求めることができます。
def FORWARD(c): return c + (c & (- c))
実際に計算してみると次のようになります。
1 : 1 2 4 8 2 : 2 4 8 3 : 3 4 8 4 : 4 8 5 : 5 6 8 6 : 6 8 7 : 7 8 8 : 8 9 : 9 10 12 10 : 10 12 11 : 11 12 12 : 12 13 : 13 14 14 : 14 15 : 15
上図の二分木をたどってみてください。同じ結果になることがわかります。これをプログラムすると次のようになります。
リスト : 出現頻度の更新
def put_value(self, c, inc):
if c > 0:
while c < self.size:
self.count[c] += inc
c += (c & (- c)) # FORWARD
else:
self.count[0] += inc
self.sum_ += inc
FORWARD で節をたどりながら、節の値に inc を加算していきます。c が size 以上になったら終了です。最後に、記号の総数を表す sum_ に inc を加算します。
●出現頻度表の初期化と更新
BIT の初期化と更新処理は put_value() を使って行います。次のリストを見てください。
リスト : BIT の初期化と更新
class Freq:
def __init__(self, size):
self.size = size
self.sum_ = 0
self.count = [0] * size
self.mid = 1 # 修正
while self.mid < size // 2: self.mid <<= 1 # 2010/10/16
for i in range(size): self.put_value(i, 1)
# 出現頻度表の更新
def update(self, c):
self.put_value(c, 1)
if self.sum_ >= MIN_RANGE:
for i in range(self.size):
n = get_prob(i) >> 1
if n > 0: self.put_value(i, - n)
size が 2 の累乗以外の場合でも正しく復号できるように修正。中央値 (ルート) を求める処理を追加します。size が 2 の累乗の場合、中央値は size / 2 で求めることができますが、それ以外の場合は size / 2 <= 2n を満たす最小の 2n (n は整数) が中央値になります。
メソッド __init__() は記号の出現頻度を 1 に初期化します。配列 count は 0 で初期化されているので、put_value() で各記号の出現頻度を +1 するだけです。
メソッド update() は記号 c の出現頻度を put_value() で +1 します。そして、出現頻度の合計値 sum_ が MIN_RANGE 以上になったならば、各記号の出現頻度を半分にします。まず、get_prob() で記号の出現頻度を求めて 値を 1/2 にします。そして、その値を put_value() で引き算します。
●記号の復号
最後に記号を復号するメソッド decode() の内部関数 search_code() を作ります。
リスト ; 記号の復号
def decode(self, rc):
# 記号の探索
def search_code(value):
c = 0
n = 0
if self.count[0] <= value:
h = self.mid # 修正 2010/10/16
n = self.count[0]
while h > 0:
# 修正 2010/10/16
if c + h < self.size and n + self.count[c + h] <= value:
n += self.count[c + h]
c += h
h >>= 1
c += 1
return c, n
#
temp = rc.range_ // self.sum_
c, num = search_code(rc.low // temp)
rc.low -= temp * num
rc.range_ = temp * self.get_prob(c)
rc.decode_normalize()
self.update(c)
return c
size が 2 の累乗以外の場合でも正しく復号できるように修正。変数 h を self.mid で初期化して、count の値を求めるとき c + h < self.size のチェックを追加しました。
内部関数 search_code() は変数 n に累積度数を求め、復号する記号を二分探索します。while ループで二分探索を行い、value <= 累積度数 を満たす一番大きな記号 c を探します。したがって、求める記号は c + 1 になります。最後に、c と n を返します。
あとのプログラムは簡単なので説明は割愛いたします。詳細は プログラムリスト３ をお読みください。
●評価結果
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus で、実行時間を計測してみましょう。結果は次にようになりました。
表 : BIT の実行結果
高速化(1) 高速化(2) 高速化(3)
ファイル名 サイズ 符号化 復号 符号化 復号 符号化 復号 符号化 復号
---------------------------------------------------------------------------------------
alice29.txt 152,089 1.219 2.239 0.516 0.651 0.575 0.577 0.612 0.865
asyoulik.txt 125,179 1.045 1.839 0.458 0.536 0.469 0.490 0.531 0.738
cp.html 24,603 0.197 0.363 0.093 0.115 0.103 0.098 0.109 0.151
fields.c 11,150 0.083 0.149 0.040 0.047 0.043 0.046 0.052 0.065
grammar.lsp 3,721 0.026 0.051 0.013 0.017 0.015 0.017 0.016 0.024
kennedy.xls 1,029,744 3.469 5.096 2.736 3.266 3.882 3.940 3.239 4.160
lcet10.txt 426,754 3.574 6.589 1.416 1.816 1.662 1.639 1.750 2.414
plrabn12.txt 481,861 3.968 7.060 1.574 2.043 1.872 1.797 1.948 2.733
ptt5 513,216 1.458 2.289 1.122 1.360 1.736 1.853 0.990 1.173
sum 38,240 0.239 0.381 0.120 0.163 0.158 0.154 0.134 0.174
xargs.1 4,227 0.033 0.070 0.015 0.022 0.017 0.017 0.021 0.034
--------------------------------------------------------------------------------------
合計 2,810,784 15.131 26.126 8.103 10.036 10.532 10.628 9.402 12.531
符号化と復号の単位 : 秒
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
高速化 (3) が BIT の実行結果です。BIT の効果はとても高く、従来版に比べてとても高速になりましたが、ptt5 を除いて高速化 (1) よりも少し遅くなりました。BIT のプログラムはけっこう複雑になるので、処理が単純な高速化 (1) の方が少し速くなるようです。BIT は記号 0 を二分木に含めていないので、ptt5 のように記号 0 が多いファイルでは BIT の方が高速に処理できるようです。
それから、BIT は記号の種類を N とすると、累積度数の計算と更新処理が log2 N に比例する時間で済むのも特徴です。たとえば、記号の種類が 512 に増えても、累積度数の計算と更新処理は 9 回の繰り返しですみます。また、メモリの消費が少ないのも長所のひとつでしょう。Binary Indexed Tree (BIT) は優れた方法だと思います。Yuta Mori さんに感謝いたします。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
●プログラムリスト１
#
# rc21.py : 適応型レンジコーダ (高速化その１)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from rangecoder import *
# 定数
GR = 16
# 出現頻度表
class Freq:
def __init__(self, size):
self.size = size
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] += 1
self.count_group[c // GR] += 1
self.sum_ += 1
if self.sum_ >= MIN_RANGE:
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
# ファイルの読み込み
def read_file(fin):
while True:
c = fin.getc()
if c is None: break
yield c
# レンジコーダによる符号化
def encode(fin, fout):
rc = RangeCoder(fout, ENCODE)
freq = Freq(256)
for x in read_file(fin):
freq.encode(rc, x)
rc.finish()
# レンジコーダによる復号
def decode(fin, fout, size):
freq = Freq(256)
rc = RangeCoder(fin, DECODE)
for _ in range(size):
fout.putc(freq.decode(rc))
# 符号化
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='適応型RangeCoder符号')
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))
●プログラムリスト２
#
# rc22.py : 適応型レンジコーダ (二分木を使った高速化)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from rangecoder import *
# 出現頻度表
class Freq:
def __init__(self, size):
self.size = size
self.count = [0] * size
self.count_sum = [0] * (size - 1)
self.sum_ = 0
for x in range(size): self.put_value(x, 1)
# 頻度の更新
def put_value(self, c, n):
node = c + self.size - 1
self.count[c] += n
self.sum_ += n
while node > 0:
parent = (node - 1) // 2
if node & 1:
# 左の子
self.count_sum[parent] += n
node = parent
# 記号の累積度数を求める
def cumul(self, c):
n = 0
node = c + self.size - 1
while node > 0:
parent = (node - 1) // 2
if node & 1 == 0:
# 右の子
n += self.count_sum[parent]
else:
# 左の子
self.count_sum[parent] += 1
node = parent
return n
# 出現頻度表の更新
def update(self, c):
self.count[c] += 1
self.sum_ += 1
if self.sum_ >= MIN_RANGE:
for x in range(self.size):
n = self.count[x] >> 1
if n > 0: self.put_value(x, - 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
node = 0
node_size = self.size - 1
while node < node_size:
if value < n + self.count_sum[node]:
# 左の子をたどる
self.count_sum[node] += 1
node = 2 * node + 1
else:
# 右の子をたどる
n += self.count_sum[node]
node = 2 * node + 2
return node - node_size, 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
# ファイルの読み込み
def read_file(fin):
while True:
c = fin.getc()
if c is None: break
yield c
# レンジコーダによる符号化
def encode(fin, fout):
rc = RangeCoder(fout, ENCODE)
freq = Freq(256)
for x in read_file(fin):
freq.encode(rc, x)
rc.finish()
# レンジコーダによる復号
def decode(fin, fout, size):
freq = Freq(256)
rc = RangeCoder(fin, DECODE)
for _ in range(size):
fout.putc(freq.decode(rc))
# 符号化
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='適応型RangeCoder符号')
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))
●プログラムリスト３
#
# rc23.py : 適応型レンジコーダ (BIT による高速化)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from rangecoder import *
# 出現頻度表
class Freq:
def __init__(self, size):
self.size = size
self.sum_ = 0
self.count = [0] * size
self.mid = 1 # 修正
while self.mid < size // 2: self.mid <<= 1 # 2010/10/16
for i in range(size): self.put_value(i, 1)
# 記号の出現頻度を求める
def get_prob(self, c):
val = self.count[c]
if c > 0 and c & 1 == 0:
p = c & (c - 1) # BACKWARD
c -= 1
while c != p:
val -= self.count[c]
c = c & (c - 1) # BACKWARD
return val
# 頻度の更新
def put_value(self, c, inc):
if c > 0:
while c < self.size:
self.count[c] += inc
c += (c & (- c)) # FORWARD
else:
self.count[0] += inc
self.sum_ += inc
# 記号の累積度数を求める
def cumul(self, c):
n = 0
if c > 0:
n = self.count[0]
# c - 1 までの頻度を加算する
c -= 1
while c > 0:
n += self.count[c]
c = c & (c - 1) # BACKWARD
return n
# 出現頻度表の更新
def update(self, c):
self.put_value(c, 1)
if self.sum_ >= MIN_RANGE:
for i in range(self.size):
n = get_prob(i) >> 1
if n > 0: self.put_value(i, - n)
# 符号化
def encode(self, rc, c):
temp = rc.range_ // self.sum_
rc.low += self.cumul(c) * temp
rc.range_ = self.get_prob(c) * temp
rc.encode_normalize()
self.update(c)
# 復号
def decode(self, rc):
# 記号の探索
def search_code(value):
c = 0
n = 0
if self.count[0] <= value:
h = self.mid # 修正 2010/10/16
n = self.count[0]
while h > 0:
# 修正 2010/10/16
if c + h < self.size and n + self.count[c + h] <= value:
n += self.count[c + h]
c += h
h >>= 1
c += 1
return c, n
#
temp = rc.range_ // self.sum_
c, num = search_code(rc.low // temp)
rc.low -= temp * num
rc.range_ = temp * self.get_prob(c)
rc.decode_normalize()
self.update(c)
return c
# ファイルの読み込み
def read_file(fin):
while True:
c = fin.getc()
if c is None: break
yield c
# レンジコーダによる符号化
def encode(fin, fout):
rc = RangeCoder(fout, ENCODE)
freq = Freq(256)
for x in read_file(fin):
freq.encode(rc, x)
rc.finish()
# レンジコーダによる復号
def decode(fin, fout, size):
freq = Freq(256)
rc = RangeCoder(fin, DECODE)
for _ in range(size):
fout.putc(freq.decode(rc))
# 符号化
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='適応型RangeCoder符号')
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))
改訂 2022 年 9 月 23 日