1987 年に T. C. Bell が開発した LZB 符号は、一致長の符号化にγ符号を、位置の符号化に可変長符号 (CBT 符号) を用いて LZSS 符号の圧縮率を改善する方法です。詳しい説明は拙作のページ Algorithms with Python: LZB 符号と LZH 符号 をお読みください。
# coding: utf-8
#
# lzb.rb : LZB 符号
#
# Copyright (C) 2006-2023 Makoto Hiroi
#
require "optparse"
require "./bitio"
# 定数
MIN_LEN = 3
MAX_LEN = 128
POS_BITS = 15
# スライド窓
class Slide
attr_reader :match_len, :match_pos, :buff, :data_size, :limit
def initialize(file)
@file = file
@size = 1 << POS_BITS
@limit = @size * 2
@next = Array.new(@size, nil)
@hash = {}
@buff = Array.new(@limit + MAX_LEN, 0)
@data_size = read_data(0, @limit + MAX_LEN)
@match_len = 0
@match_pos = 0
end
private
def read_data(start, size)
n = 0
while n < size
c = @file.getbyte
break unless c
@buff[start + n] = c
n += 1
end
n
end
def move_data(to, from, size)
n = 0
while n < size
@buff[to + n] = @buff[from + n]
n += 1
end
end
def hash_value(rp)
(@buff[rp] << 16) + (@buff[rp + 1] << 8) + @buff[rp + 2]
end
public
def update(rp)
return rp if @data_size < @limit + MAX_LEN
# buffer update
move_data(0, @size, @size + MAX_LEN)
n = read_data(@size + MAX_LEN, @size)
@data_size = @size + MAX_LEN + n
# hash update
@hash.each do |k, v|
if v < @size
@hash.delete(k)
else
@hash[k] = v - @size
end
end
@next.map! do |v|
if v == nil || v < @size
nil
else
v - @size
end
end
rp - @size
end
def insert(rp)
value = hash_value(rp)
@next[rp & (@size - 1)] = @hash[value]
@hash[value] = rp
end
# 単純なハッシュ法
# ハッシュ値の衝突が多いと極端に遅くなる
def search(rp)
n = @hash[hash_value(rp)]
limit = rp - @size
@match_len = 0
@match_pos = 0
while n
break if n < limit
if @buff[rp + @match_len] == @buff[n + @match_len]
x = 0
while x < MAX_LEN
break if @buff[rp + x] != @buff[n + x]
x += 1
end
if @match_len < x
@match_len = x
@match_pos = n
break if x == MAX_LEN
end
end
n = @next[n & (@size - 1)]
end
# データの終端をチェック
@match_len = @data_size - rp if @match_len >= @data_size - rp
end
end
# 位置の符号化には CBT 符号を使う
$pos_bits = 0
def update_pos_bits(rp)
if $pos_bits < POS_BITS
$pos_bits += 1 while rp > (1 << $pos_bits) - 1
end
end
def pos_encode(fout, rp, pos)
if 1 < $pos_bits && $pos_bits < POS_BITS
fout.cbt_encode(pos, rp, $pos_bits)
else
fout.putbits($pos_bits, pos)
end
end
def pos_decode(fin, rp)
if 1 < $pos_bits && $pos_bits < POS_BITS
fin.cbt_decode(rp, $pos_bits)
else
fin.getbits($pos_bits)
end
end
# 符号化
def encode(fin, fout)
s = Slide.new(fin)
rp = 0
begin
s.search(rp)
if s.match_len < MIN_LEN
len = 1
fout.putbit(0)
fout.putbits(8, s.buff[rp])
else
len = s.match_len
fout.putbit(1)
fout.gamma_encode(len - MIN_LEN)
pos_encode(fout, rp, rp - s.match_pos - 1)
end
len.times do
s.insert(rp)
rp += 1
rp = s.update(rp) if rp >= s.limit
end
update_pos_bits(rp)
end while rp < s.data_size
end
def encode_file(name1, name2)
fin = open(name1, "rb")
fout = BitIO.new(name2, WOPEN)
size = File.size(name1)
fout.putbits(32, size)
encode(fin, fout) if size > 0
fin.close
fout.close
end
# 復号
def decode(fin, fout, size)
rp = 0
buff = Array.new(1 << POS_BITS)
while size > 0
if fin.getbit == 1
len = fin.gamma_decode + MIN_LEN
pos = rp - (pos_decode(fin, rp) + 1)
pos += buff.size if pos < 0
len.times do
c = buff[pos]
fout.putc(c)
buff[rp] = c
pos += 1
rp += 1
pos = 0 if pos >= buff.size
rp = 0 if rp >= buff.size
end
else
len = 1
c = fin.getbits(8)
fout.putc(c)
buff[rp] = c
rp += 1
rp = 0 if rp >= buff.size
end
size -= len
update_pos_bits(rp)
end
end
def decode_file(name1, name2)
fin = BitIO.new(name1, ROPEN)
fout = open(name2, "wb")
size = fin.getbits(32)
decode(fin, fout, size) if size > 0
fin.close
fout.close
end
def main
eflag = false
dflag = false
opts = OptionParser.new
opts.on("-e"){|v| eflag = true}
opts.on("-d"){|v| dflag = true}
opts.parse!(ARGV)
if eflag && !dflag
encode_file(ARGV[0], ARGV[1])
elsif dflag && !eflag
decode_file(ARGV[0], ARGV[1])
else
print "option error"
end
end
# 実行
s = Time.now
main
e = Time.now
printf "%.3f\n", e - s
テストデータは Canterbury Corpus で配布されている The Canterbury Corpus です。
スライド窓の大きさ 8192, MAX_LEN = 18 の場合 ファイル名 サイズ LZSS LZB ------------------------------------------- alice29.txt 152,089 68,332 66,120 asyoulik.txt 125,179 61,789 58,833 cp.html 24,603 10,278 10,126 fields.c 11,150 3,859 3,824 grammar.lsp 3,721 1,594 1,471 kennedy.xls 1,029,744 291,968 317,643 lcet10.txt 426,754 184.684 179,973 plrabn12.txt 481,861 247,780 234,576 ptt5 513,216 107,289 120,286 sum 38,240 17,500 17,137 xargs.1 4,227 2,198 2,007 ------------------------------------------- 合計 2,810,784 997,271 1,011,006 スライド窓の大きさ 32 k, MAX_LEN = 128 の場合 ファイル名 サイズ LZB 符号化 復号 ------------------------------------------------ alice29.txt 152,089 60,437 0.345 0.153 asyoulik.txt 125,179 54,736 0.285 0.133 cp.html 24,603 8,973 0.038 0.026 fields.c 11,150 3,513 0.019 0.013 grammar.lsp 3,721 1,424 0.009 0.007 kennedy.xls 1,029,744 328,111 1.882 0.864 lcet10.txt 426,754 162,247 0.999 0.398 plrabn12.txt 481,861 218,902 1.292 0.515 ptt5 513,216 69,737 10.139 0.281 sum 38,240 15,078 0.119 0.041 xargs.1 4,227 1,985 0.010 0.008 ------------------------------------------------ 合計 2,810,784 925,143 15.137 2.439 符号化と復号の単位 : 秒 実行環境 : Ruby 3.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
CBT 符号を用いて LZW 符号の圧縮率を改善します。詳しい説明は拙作のページ Algorithms with Python: LZ78 符号 (LZW 符号) をお読みください。
# coding: utf-8
#
# lzw1.rb : LZW 符号 + CBT 符号
#
# Copyright (C) 2006-2023 Makoto Hiroi
#
require "optparse"
require "./bitio"
# 辞書の大きさ
DIC_SIZE = 15
# 節
class Node
attr_accessor :code, :parent
def initialize(code, parent)
@code = code
@parent = parent
end
end
# トライはハッシュ法で実装
class Dic
attr_reader :len
def initialize(size)
@max_bits = size
@bits = 9
@count = 256
@buff = []
@hash = {}
@len = 0
256.times do |c|
@buff << Node.new(c, nil)
end
end
# CBT 符号で符号化
def encode(file, c)
if @bits < @max_bits
file.cbt_encode(c, @count, @bits)
@count += 1
@bits += 1 if @count > (1 << @bits) - 1
else
file.putbits(@max_bits, c)
end
end
# CBT 符号の復号
def decode(file)
if @bits < @max_bits
n = file.cbt_decode(@count, @bits)
@count += 1
@bits += 1 if @count > (1 << @bits) - 1
n
else
file.getbits(@max_bits)
end
end
# 辞書番号のチェック
def check_code(code)
code < @buff.size
end
# 子を探す
def search_child(n, c)
@hash[(n << 8) + c]
end
# 子を挿入する
def insert_child(n, c)
if @buff.size < (1 << @max_bits)
child = @buff.size
@buff << Node.new(c, n)
@hash[(n << 8) + c] = child
end
end
# 出力
def output(file, n)
if @buff[n].parent == nil
file.putc(n)
@len = 1
return n
else
m = output(file, @buff[n].parent)
file.putc(@buff[n].code)
@len += 1
return m
end
end
end
# 符号化
def encode(fin, fout)
dic = Dic.new(DIC_SIZE)
p = fin.getbyte
while c = fin.getbyte
q = dic.search_child(p, c)
if q
p = q
else
dic.encode(fout, p)
dic.insert_child(p, c)
p = c
end
end
dic.encode(fout, p)
end
def encode_file(name1, name2)
fin = open(name1, "rb")
fout = BitIO.new(name2, WOPEN)
size = File.size(name1)
fout.putbits(32, size)
encode(fin, fout) if size > 0
fin.close
fout.close
end
# 復号
def decode(fin, fout, size)
dic = Dic.new(DIC_SIZE)
p = dic.decode(fin)
c = dic.output(fout, p)
size -= dic.len
while size > 0
q = dic.decode(fin)
if dic.check_code(q)
c = dic.output(fout, q)
dic.insert_child(p, c)
else
dic.insert_child(p, c)
c = dic.output(fout, q)
end
p = q
size -= dic.len
end
end
def decode_file(name1, name2)
fin = BitIO.new(name1, ROPEN)
fout = open(name2, "wb")
size = fin.getbits(32)
decode(fin, fout, size) if size > 0
fin.close
fout.close
end
def main
eflag = false
dflag = false
opts = OptionParser.new
opts.on("-e"){|v| eflag = true}
opts.on("-d"){|v| dflag = true}
opts.parse!(ARGV)
if eflag && !dflag
encode_file(ARGV[0], ARGV[1])
elsif dflag && !eflag
decode_file(ARGV[0], ARGV[1])
else
print "option error"
end
end
# 実行
s = Time.now
main
e = Time.now
printf "%.3f\n", e - s
テストデータは Canterbury Corpus で配布されている The Canterbury Corpus です。
辞書の大きさ = 8192 ファイル名 サイズ LZW LZW1 ------------------------------------------ alice29.txt 152,089 68,448 67,415 asyoulik.txt 125,179 59,085 58,056 cp.html 24,603 12,150 11,111 fields.c 11,150 5,760 4,810 grammar.lsp 3,721 2,294 1,747 kennedy.xls 1,029,744 339,542 338,558 lcet10.txt 426,754 194,996 193,968 plrabn12.txt 481,861 220,850 219,812 ptt5 513,216 66,101 65,084 sum 38,240 30,163 29,123 xargs.1 4,227 2,916 2,249 ------------------------------------------ 合計 2,810,784 1,002,305 991,993 辞書の大きさ = 32 k ファイル名 サイズ LZW1 符号化 復号 ------------------------------------------------ alice29.txt 152,089 61,123 0.151 0.220 asyoulik.txt 125,179 54,117 0.132 0.194 cp.html 24,603 10,877 0.028 0.042 fields.c 11,150 4,810 0.014 0.020 grammar.lsp 3,721 1,747 0.007 0.009 kennedy.xls 1,029,744 338,206 0.686 1.114 lcet10.txt 426,754 168,556 0.357 0.545 plrabn12.txt 481,861 200,493 0.406 0.621 ptt5 513,216 61,101 0.205 0.432 sum 38,240 19,473 0.050 0.065 xargs.1 4,227 2,249 0.010 0.010 ------------------------------------------------ 合計 2,810,784 922,752 2.046 3.272 符号化と復号の単位 : 秒 実行環境 : Ruby 3.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
LZT 符号は 1987 年に Tischer によって開発されました。LZT 符号のおもな改良点は、辞書が満杯になった場合、長い間使われていない (最長時間未使用 : Least Recently Used) 語を取り除くことで辞書の空きスペースを作るところです。このような操作を「LRU スキーム」と呼びます。LZT 符号は LRU スキームを行うため符号化と復号に時間がかかることになりますが、少ないメモリでも高い圧縮率を期待することができます。詳しい説明は拙作のページ Algorithms with Python: LZT 符号 をお読みください。
# coding: utf-8
#
# lzt.rb : LZT 符号 + CBT 符号
#
# Copyright (C) 2006-2023 Makoto Hiroi
#
require "optparse"
require "./bitio"
# 辞書の大きさ
DIC_SIZE = 15
# 節
class Node
attr_accessor :code, :parent, :child
def initialize(code, parent)
@code = code
@parent = parent
# 子の個数
@child = 0
end
end
# トライはハッシュ法で実装
class Dic
HEAD = 0
attr_reader :len
def initialize(size)
@max_bits = size
@bits = 9
@count = 256
@buff = []
@hash = {}
@len = 0
256.times do |c|
@buff << Node.new(c, nil)
end
# 双方向リスト
@prev = Array.new(1 << @max_bits)
@link = Array.new(1 << @max_bits)
@prev[HEAD] = HEAD
@link[HEAD] = HEAD
end
# 双方向リストの操作
def add_list(n)
if n >= 256
last = @prev[HEAD]
@prev[n] = last
@link[n] = HEAD
@link[last] = n
@prev[HEAD] = n
end
end
def delete_list(n)
if n >= 256
p = @prev[n]
q = @link[n]
@prev[q] = p
@link[p] = q
end
end
# 葉を探す
def search_leaf
i = @link[HEAD]
while i != HEAD
break if @buff[i].child == 0
i = @link[i]
end
i
end
# 子を探す
def search_child(n, c)
@hash[(n << 8) + c]
end
# 子を削除する
def delete_child(n)
p = @buff[n].parent
@hash.delete((p << 8) + @buff[n].code)
@buff[p].child -= 1
end
# 子を挿入する
def insert_child(n, c)
if @buff.size < (1 << @max_bits)
child = @buff.size
@buff << Node.new(c, n)
else
child = search_leaf
delete_list(child)
delete_child(child)
@buff[child].code = c
@buff[child].parent = n
end
@buff[n].child += 1
@hash[(n << 8) + c] = child
add_list(child)
end
# CBT 符号
def encode(file, c)
if @bits < @max_bits
file.cbt_encode(c, @count, @bits)
@count += 1
@bits += 1 if @count > (1 << @bits) - 1
else
file.putbits(@max_bits, c)
end
end
def decode(file)
if @bits < @max_bits
n = file.cbt_decode(@count, @bits)
@count += 1
@bits += 1 if @count > (1 << @bits) - 1
n
else
file.getbits(@max_bits)
end
end
# 辞書番号のチェック
def check_code(code)
if @buff.size == (1 << @max_bits)
return true if search_leaf != code
elsif code < @buff.size
return true
end
false
end
# 出力
def output(file, n)
if @buff[n].parent == nil
file.putc(n)
delete_list(n)
add_list(n)
@len = 1
return n
else
m = output(file, @buff[n].parent)
file.putc(@buff[n].code)
delete_list(n)
add_list(n)
@len += 1
return m
end
end
end
# 符号化
def encode(fin, fout)
dic = Dic.new(DIC_SIZE)
p = fin.getbyte
while c = fin.getbyte
q = dic.search_child(p, c)
if q
p = q
dic.delete_list(q)
dic.add_list(q)
else
dic.encode(fout, p)
dic.insert_child(p, c)
p = c
end
end
dic.encode(fout, p)
end
def encode_file(name1, name2)
fin = open(name1, "rb")
fout = BitIO.new(name2, WOPEN)
size = File.size(name1)
fout.putbits(32, size)
encode(fin, fout) if size > 0
fin.close
fout.close
end
# 復号
def decode(fin, fout, size)
dic = Dic.new(DIC_SIZE)
p = dic.decode(fin)
c = dic.output(fout, p)
size -= dic.len
while size > 0
q = dic.decode(fin)
if dic.check_code(q)
c = dic.output(fout, q)
dic.insert_child(p, c)
else
dic.insert_child(p, c)
c = dic.output(fout, q)
end
p = q
size -= dic.len
end
end
def decode_file(name1, name2)
fin = BitIO.new(name1, ROPEN)
fout = open(name2, "wb")
size = fin.getbits(32)
decode(fin, fout, size) if size > 0
fin.close
fout.close
end
def main
eflag = false
dflag = false
opts = OptionParser.new
opts.on("-e"){|v| eflag = true}
opts.on("-d"){|v| dflag = true}
opts.parse!(ARGV)
if eflag && !dflag
encode_file(ARGV[0], ARGV[1])
elsif dflag && !eflag
decode_file(ARGV[0], ARGV[1])
else
print "option error"
end
end
# 実行
s = Time.now
main
e = Time.now
printf "%.3f\n", e - s
テストデータは Canterbury Corpus で配布されている The Canterbury Corpus です。
辞書の大きさ = 8192 ファイル名 サイズ LZW LZW1 LZT --------------------------------------------------- alice29.txt 152,089 68,448 67,415 64,193 asyoulik.txt 125,179 59,085 58,056 56,937 cp.html 24,603 12,150 11,111 11,111 fields.c 11,150 5,760 4,810 4,810 grammar.lsp 3,721 2,294 1,747 1,747 kennedy.xls 1,029,744 339,542 338,558 274,242 lcet10.txt 426,754 194,996 193,968 180,431 plrabn12.txt 481,861 220,850 219,812 215,225 ptt5 513,216 66,101 65,084 61,407 sum 38,240 30,163 29,123 19,364 xargs.1 4,227 2,916 2,249 2,249 --------------------------------------------------- 合計 2,810,784 1,002,305 991,993 891,716 辞書の大きさ = 32 k ファイル名 サイズ LZT 符号化 復号 ------------------------------------------------ alice29.txt 152,089 61,097 0.200 0.280 asyoulik.txt 125,179 54,117 0.170 0.235 cp.html 24,603 10,877 0.038 0.061 fields.c 11,150 4,810 0.018 0.024 grammar.lsp 3,721 1,747 0.009 0.012 kennedy.xls 1,029,744 303,277 1.069 1.630 lcet10.txt 426,754 163,278 0.555 0.776 plrabn12.txt 481,861 198,821 0.656 0.908 ptt5 513,216 61,064 0.359 0.586 sum 38,240 19,473 0.061 0.080 xargs.1 4,227 2,249 0.009 0.012 ------------------------------------------------ 合計 2,810,784 880,810 3.144 4.604 符号化と復号の単位 : 秒 実行環境 : Ruby 3.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
スプレイ符号は「動的符号化」の一種で、符号木に対して出現した記号の符号語長が半分になるようにスプレイ操作を適用することにより、頻繁に現れる記号に短い符号語を割り当てることができます。詳しい説明は拙作のページ Algorithms with Python: バイナリレンジコーダ [3], スプレー符号 をお読みください。
# coding: utf-8
#
# splaycode.rb : スプレイ符号
#
# Copyright (C) 2006-2023 Makoto Hiroi
#
require "optparse"
require "./bitio"
# ファイルの終了
EOF = 256
class SplayCode
def initialize(n)
@num = n - 1
@parent = Array.new(2 * n - 1)
@left = Array.new(n - 1)
@right = Array.new(n - 1)
for i in 0 ... n - 1
@parent[i] = (i - 1) / 2
@left[i] = 2 * i + 1
@right[i] = 2 * i + 2
end
for i in n - 1 ... 2 * n - 1
@parent[i] = (i - 1) / 2
end
end
private
# splay 操作で符号長を半分にする
def splay(code)
n = @num + code
begin
p = @parent[n]
break if p == 0
g = @parent[p]
if @left[g] == p
gc = @right[g]
@right[g] = n
else
gc = @left[g]
@left[g] = n
end
@parent[n] = g
if @left[p] == n
@left[p] = gc
else
@right[p] = gc
end
@parent[gc] = p
n = g
end while n > 0
end
# 符号化
def encode_sub(fout, n, p)
encode_sub(fout, p, @parent[p]) if p > 0
if @right[p] == n
fout.putbit(1)
else
fout.putbit(0)
end
end
public
# 符号化
def encode(fout, code)
n = @num + code
encode_sub(fout, n, @parent[n])
splay(code)
end
# 復号
def decode(fin)
n = 0
while n < @num
if fin.getbit == 1
n = @right[n]
else
n = @left[n]
end
end
code = n - @num
splay(code)
code
end
end
# 符号化
def encode(name1, name2)
fin = open(name1, "rb")
fout = BitIO.new(name2, WOPEN)
splay = SplayCode.new(257)
fin.each_byte do |c|
splay.encode(fout, c)
end
splay.encode(fout, EOF)
fin.close
fout.close
end
# 復号
def decode(name1, name2)
fin = BitIO.new(name1, ROPEN)
fout = open(name2, "wb")
splay = SplayCode.new(257)
while (c = splay.decode(fin)) != EOF
fout.putc(c)
end
fin.close
fout.close
end
def main
eflag = false
dflag = false
opts = OptionParser.new
opts.on("-e"){|v| eflag = true}
opts.on("-d"){|v| dflag = true}
opts.parse!(ARGV)
if eflag && !dflag
encode(ARGV[0], ARGV[1])
elsif dflag && !eflag
decode(ARGV[0], ARGV[1])
else
print "option error"
end
end
# 実行
s = Time.now
main
e = Time.now
printf "%.3f\n", e - s
テストデータは Canterbury Corpus で配布されている The Canterbury Corpus です。
ファイル名 サイズ Splay 符号化 復号 ------------------------------------------------ alice29.txt 152,089 104,800 0.260 0.283 asyoulik.txt 125,179 90,108 0.252 0.239 cp.html 24,603 18,931 0.051 0.055 fields.c 11,150 7,875 0.024 0.025 grammar.lsp 3,721 2,497 0.010 0.010 kennedy.xls 1,029,744 501,392 1.303 1.407 lcet10.txt 426,754 289,971 0.746 0.768 plrabn12.txt 481,861 336,093 0.854 0.893 ptt5 513,216 109,677 0.285 0.381 sum 38,240 23,580 0.076 0.071 xargs.1 4,227 3,047 0.011 0.011 ------------------------------------------------ 合計 2,810,784 1,487,971 3.872 4.143 符号化と復号の単位 : 秒 実行環境 : Ruby 3.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
レンジコーダ (range coder) は 1998 年に Michael Schindler 氏が発表し、「高性能、高速、特許フリー」の方法として注目を集めるようになった符号化方式です。Michael Schindler 氏のレンジコーダは計算の途中で「桁上がり」が発生します。ところが、ロシアの Dmitry Subbotin 氏が発表した「桁上げのないレンジコーダ」は、その名のごとく桁上がりが発生しません。現在、レンジコーダは主にこの 2 種類の形式が存在するようです。
レンジコーダは原理的には「算術符号」と同じ方法です。性能は算術符号に比べるとわずかに劣化しますが、実現方法はとても簡単で実行速度も高速です。もちろん、ハフマン符号よりも高性能です。詳しい説明は拙作のページ Algorithms with Python: レンジコーダ [1], [2], [3] をお読みください。
# coding: utf-8
#
# rangecoder.rb : レンジコーダ (桁上がりあり)
#
# Copyright (C) 2006-2023 Makoto Hiroi
#
# 定数
ENCODE = "encode"
DECODE = "decode"
class RangeCoder
MAX_RANGE = 0x100000000
MIN_RANGE = 0x1000000
MASK = 0xffffffff
SHIFT = 24
attr_accessor :range, :low
def initialize(file, mode)
@file = file
@range = MAX_RANGE
@buff = 0
@cnt = 0
if mode == ENCODE
@low = 0
elsif mode == DECODE
@file.getbyte # buff の初期値 (0) を読み捨てる
# 4 byte read
@low = @file.getbyte
@low = (@low << 8) + @file.getbyte
@low = (@low << 8) + @file.getbyte
@low = (@low << 8) + @file.getbyte
else
raise "RangeCoder mode error"
end
end
def buff_flush(c)
@file.putc(@buff)
while @cnt > 0
@file.putc(c)
@cnt -= 1
end
end
def encode_normalize
while @range < MIN_RANGE
if @low < (0xff << SHIFT)
# 桁上がりが発生しない場合
buff_flush(0xff)
@buff = (@low >> SHIFT) & 0xff
elsif @low >= MAX_RANGE
# 桁上がり
@buff += 1
buff_flush(0)
@buff = (@low >> SHIFT) & 0xff
else
# 上位 8 bit が 0xff
@cnt += 1
end
@low = (@low << 8) & MASK
@range <<= 8
end
end
def decode_normalize
while @range < MIN_RANGE
@range <<= 8
@low = ((@low << 8) + @file.getbyte) & MASK
end
end
# 符号化の終了処理
def finish
if @low >= MAX_RANGE
# 桁上がり
@buff += 1
buff_flush(0)
else
buff_flush(0xff)
end
@file.putc((@low >> SHIFT) & 0xff)
@file.putc((@low >> 16) & 0xff)
@file.putc((@low >> 8) & 0xff)
@file.putc(@low & 0xff)
end
end
# 出現頻度表
class Frequency
GR = 16
def initialize(size, limit = 0x2000, inc = 4)
@count = Array.new(size, 1)
@count_group = Array.new(size / GR + 1, GR)
@count_group[size / GR] = size % GR
@sum = size
@limit = limit
@inc = inc
end
# 出現頻度表の更新
def update(c)
@count[c] += @inc
@count_group[c / GR] += @inc
@sum += @inc
if @sum > @limit
@sum = 0
@count_group.fill(0)
for x in 0 ... @count.size
@count[x] = (@count[x] >>= 1) | 1
@count_group[x / GR] += @count[x]
@sum += @count[x]
end
end
end
# 累積度数を求める
def cumul(c)
x = num = 0
for x in 0 ... (c/GR)
num += @count_group[x]
end
for y in ((c/GR)*GR) ... c
num += @count[y]
end
num
end
# 記号を探す
def search(value)
x = num = 0
for x in 0 ... @count_group.size
break if value < (num + @count_group[x])
num += @count_group[x]
end
for c in x*GR ... @count.size
break if value < (num + @count[c])
num += @count[c]
end
[c, num]
end
# 符号化
def encode(rc, c)
temp = rc.range / @sum
rc.low += cumul(c) * temp
rc.range = temp * @count[c]
update(c)
rc.encode_normalize
end
# 復号
def decode(rc)
temp = rc.range / @sum
c, cum = search(rc.low / temp)
rc.low -= temp * cum
rc.range = temp * @count[c]
update(c)
rc.decode_normalize
c
end
end
# coding: utf-8
#
# rc.rb : レンジコーダによるファイルの圧縮
#
# Copyright (C) 2006-2023 Makoto Hiroi
#
require "optparse"
require "./rangecoder"
# ファイルの終了
EOF = 256
# 符号化
def encode(name1, name2)
infile = open(name1, "rb")
outfile = open(name2, "wb")
rc = RangeCoder.new(outfile, ENCODE)
freq = Frequency.new(257)
infile.each_byte do |c|
freq.encode(rc, c)
end
freq.encode(rc, EOF)
rc.finish
infile.close
outfile.close
end
# 復号
def decode(name1, name2)
infile = open(name1, "rb")
outfile = open(name2, "wb")
rc = RangeCoder.new(infile, DECODE)
freq = Frequency.new(257)
while (c = freq.decode(rc)) != EOF
outfile.putc(c)
end
infile.close
outfile.close
end
def main
eflag = false
dflag = false
opts = OptionParser.new
opts.on("-e"){|v| eflag = true}
opts.on("-d"){|v| dflag = true}
opts.parse!(ARGV)
if eflag && !dflag
encode(ARGV[0], ARGV[1])
elsif dflag && !eflag
decode(ARGV[0], ARGV[1])
else
print "option error"
end
end
# 実行
s = Time.now
main
e = Time.now
printf "%.3f\n", e - s
テストデータは Canterbury Corpus で配布されている The Canterbury Corpus です。
ファイル名 サイズ Range 符号化 復号 -------------------------------------------------- alice29.txt 152,089 87,655 0.287 0.392 asyoulik.txt 125,179 75,960 0.239 0.321 cp.html 24,603 16,266 0.053 0.071 fields.c 11,150 6,983 0.024 0.033 grammar.lsp 3,721 2,220 0.011 0.012 kennedy.xls 1,029,744 422,839 1.317 1.911 lcet10.txt 426,754 248,272 0.813 1.099 plrabn12.txt 481,861 276,389 0.909 1.236 ptt5 513,216 72,278 0.537 0.861 sum 38,240 22,316 0.067 0.087 xargs.1 4,227 2,671 0.012 0.014 -------------------------------------------------- 合計 2,810,784 1,233,849 4.269 6.037 符号化と復号の単位 : 秒 実行環境 : Ruby 3.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz