データ圧縮
データ圧縮関連のプログラムです。
●参考文献
- 植松友彦, 『文書データ圧縮アルゴリズム入門』, ＣＱ出版社, 1994
- 奥村晴彦, 『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991
- 奥村晴彦, 『データ圧縮の基礎から応用まで』, C MAGAZINE 2002 年 7 月号, ソフトバンク
●ランレングス
「ランレングス (Run Length)」とは「連続して現れるものの長さ」という意味です。データ内で同じ値が並んでいる場合はその値と個数で符号化する方法を「ランレングス圧縮」または「ランレングス符号化」といいます。ランレングスはとても簡単な符号化ですが、それでもいくつかの方法が考えられます。いちばん簡単な方法は、データの値とデータの個数で表す方法です。たとえば、次の文字列を考えてみましょう。
文字列 abccddeeeeffffgggggggghhhhhhhh (30)
同じ文字が連続して並んでいますね。これを文字と個数で表すと、次のようになります。
=> a1b1c2d2e4f4g8h8 (16)
元データ 30 文字を 16 文字で表すことができます。また、復号も簡単にできることは直ぐにわかると思います。このように、ランレングスはとても単純な方法ですが、画像データには大きな効果を発揮する場合があります。たとえば、白黒の画像ではデータが 2 種類しかないので、最初のデータが白か黒のどちらであるか区別できれば、あとは個数だけの情報でデータを圧縮することができます。
ところが、通常のテキストファイルでは、同じ文字が続くことはあまりないので、この方法ではほとんど効果がありません。たとえば、先ほどの文字列の前半 4 文字に注目してください。
abccdd (6) => a1b1c2d2 (8)
ランレングスを使うと、6 文字のデータが 8 文字に増えてしまいます。これでは、サイズを小さくするどころか、かえって膨らませることになってしまいます。同じデータが一つも連続していない場合、たとえば "abcdefgh" をランレングスで符号化すると、"a1b1c1d1e1f1g1h1" のようにデータ数は 2 倍にまで増えてしまいます。
そこで、同じデータが数個以上続いていたらランレングスで符号化することにします。たとえば、同じデータが 3 つ以上続いていたら符号化することにしましょう。すると、データが "aaaaa" の場合は [a, a, a, 2] と表すことができます。逆に、"aaa" は [a, a, a, 0] と符号化されるので、1 バイト増えることになります。ですが、連続していないデータをランレングスで符号化することはないので、単純なランレングスよりもデータが膨らむ危険性は小さくなります。
●プログラム
# coding: utf-8
#
# rle.rb : run length encoding
#
# Copyright (C) 2006-2023 Makoto Hiroi
#
require "optparse"
MAX_LEN = 255
# 単純なランレングス
# 符号化
def rle_encode(fin, fout)
c = fin.getbyte
while c
len = 0
while len < MAX_LEN
c1 = fin.getbyte
break if c != c1
len += 1
end
fout.putc(c)
fout.putc(len)
if len == MAX_LEN
c = fin.getbyte
else
c = c1
end
end
end
# 復号
def rle_decode(fin, fout)
while c = fin.getbyte
len = fin.getbyte
(len + 1).times do
fout.putc(c)
end
end
end
# 同じ記号が n 個続いたらランレングス
# 符号化
def rlen_encode(fin, fout, n)
c = fin.getbyte
while c
len = 1
while len < MAX_LEN + n
c1 = fin.getbyte
break if c != c1
len += 1
end
if len >= n
n.times do
fout.putc(c)
end
fout.putc(len - n)
else
len.times do
fout.putc(c)
end
end
if len == MAX_LEN + n
c = fin.getbyte
else
c = c1
end
end
end
# 復号
def rlen_decode(fin, fout, n)
c = fin.getbyte
while c
len = 1
while len < n
c1 = fin.getbyte
break if c1 != c
len += 1
end
if len == n
len += fin.getbyte
c1 = fin.getbyte
end
len.times do
fout.putc(c)
end
c = c1
end
end
def encode_file(name1, name2, num)
open(name1, "rb") do |fin|
open(name2, "wb") do |fout|
if num == 0
rle_encode(fin, fout)
else
rlen_encode(fin, fout, num)
end
end
end
end
def decode_file(name1, name2, num)
open(name1, "rb") do |fin|
open(name2, "wb") do |fout|
if num == 0
rle_decode(fin, fout)
else
rlen_decode(fin, fout, num)
end
end
end
end
def main
eflag = false
dflag = false
nflag = 0
opts = OptionParser.new
opts.on("-e"){|v| eflag = true}
opts.on("-d"){|v| dflag = true}
opts.on("-n NUM"){|v|
nflag = v.to_i if v
}
opts.parse!(ARGV)
if eflag && !dflag
encode_file(ARGV[0], ARGV[1], nflag)
elsif dflag && !eflag
decode_file(ARGV[0], ARGV[1], nflag)
else
print "option error"
end
end
# 実行
s = Time.now
main
e = Time.now - s
print e, "\n"
●実行結果
テストデータは Canterbury Corpus で配布されている The Canterbury Corpus です。
# RLE : 単純なランレングス # RLE-3 : 3 文字続いたらランレングス ファイル名 サイズ RLE RLE-3 --------------------------------------------- alice29.txt 152,089 289,852 150,130 asyoulik.txt 125,179 243,066 125,114 cp.html 24,603 46,474 24,722 fields.c 11,150 19,838 11,176 grammar.lsp 3,721 6,622 3,710 kennedy.xls 1,029,744 1,731,778 1,032,453 lcet10.txt 426,754 804,622 415,099 plrabn12.txt 481,861 944,618 481,221 ptt5 513,216 152,564 116,342 sum 38,240 58,594 35,772 xargs.1 4,227 8,294 4,227 --------------------------------------------- 合計 2,810,784 4,306,322 2,399,966
●Switched Run Length Encoding
Switched Run Length Encoding (SRLE) はランレングスとそうでない部分に分けて符号化します。SRLE の特徴は、2 つの部分を区別するためのフラグをデータに追加するのではなく、LITERAL と FILL という 2 つのモードを使って管理するところです。次の例を見てください。
モードは最初 LITERAL です。LITERAL は記号が不連続でそのまま出力するモードです。LITERAL モードでは、記号が連続しているところを探し、そこまでの個数と記号列をそのまま出力します。(1) では e が連続しているので、a b c d e までの 5 文字を出力します。a b c d の 4 文字ではないことに注意してください
次に、モードを FILL に切り替えます。FILL は同じ記号が続くことを表すモードです。このとき、連続する記号は LITERAL モードで最後に出力した記号になります。(2) では e が 4 文字続いていますが、LITERAL モードで最初の e が出力されているので、残りの e を数えて 3 を出力します。そして、モードを LITERAL に切り替えます。
(3) では f が続いているので、LITERAL モードの出力は f の 1 文字だけになります。そして、FILL モードに切り替えて、残りの f を数えて 6 を出力します。このように、モードを切り替えることから Switched Run Length Encoding と呼ばれています。
●参考文献
Switched Run Length Encoding は、Stephan T. Lavavej さんのページ bwtzip にあるプログラムを参考にさせていただきました。Stephan T. Lavavej さんに感謝いたします。
●プログラム
# coding: utf-8
#
# srle.rb : Switched Run Length Encoding
#
# Copyright (C) 2006-2023 Makoto Hiroi
#
require 'optparse'
# 定数
MAX_LEN = 255
LITERAL = 1
FILL = 0
# 符号化
def srle_encode(fin, fout)
mode = LITERAL
buff = []
c = fin.getbyte
while c
if mode == LITERAL
buff.clear
buff << c
while buff.size < MAX_LEN
c1 = fin.getbyte
break if c == c1 || c1 == nil
buff << c1
c = c1
end
fout.putc(buff.size)
buff.each do |x|
fout.putc(x)
end
if buff.size == MAX_LEN
c = fin.getbyte
else
mode = FILL
c = c1
count = 1
end
else
while count < MAX_LEN
c1 = fin.getbyte
break if c != c1
count += 1
end
fout.putc(count)
if count == MAX_LEN
count = 0
else
mode = LITERAL
c = c1
end
end
end
end
# 復号
def srle_decode(fin, fout)
mode = LITERAL
c = nil
while len = fin.getbyte
if mode == LITERAL
len.times do
c = fin.getbyte
fout.putc(c)
end
if len < MAX_LEN
mode = FILL
end
else
len.times do
fout.putc(c)
end
if len < MAX_LEN
mode = LITERAL
end
end
end
end
def encode_file(name1, name2)
open(name1, "rb") do |fin|
open(name2, "wb") do |fout|
srle_encode(fin, fout)
end
end
end
def decode_file(name1, name2)
open(name1, "rb") do |fin|
open(name2, "wb") do |fout|
srle_decode(fin, fout)
end
end
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 - s
print e, "\n"
●実行結果
テストデータは Canterbury Corpus で配布されている The Canterbury Corpus です。
# RLE : 単純なランレングス # RLE-3 : 3 文字続いたらランレングス # SRLE : Switched Run Length Encoding ファイル名 サイズ RLE RLE-3 SRLE -------------------------------------------------------- alice29.txt 152,089 289,852 150,130 154,236 asyoulik.txt 125,179 243,066 125,114 128,227 cp.html 24,603 46,474 24,722 25,600 fields.c 11,150 19,838 11,176 11,334 grammar.lsp 3,721 6,622 3,710 3,790 kennedy.xls 1,029,744 1,731,778 1,032,453 1,186,806 lcet10.txt 426,754 804,622 415,099 422,092 plrabn12.txt 481,861 944,618 481,221 490,117 ptt5 513,216 152,564 116,342 107,932 sum 38,240 58,594 35,772 35,743 xargs.1 4,227 8,294 4,227 4,308 -------------------------------------------------------- 合計 2,810,784 4,306,322 2,399,966 2,570,185
●Zero Length Encoding
記号 0 をランレングスで符号化する方法を「ゼロランレングス」といいます。ゼロランレングスは他の圧縮法、たとえばブロックソート法と組み合わせると、圧縮率が向上する場合があります。Zero Lenght Encoding はゼロランレングスの一種ですが、0 と 1 を使って記号 0 の個数を 2 進数で表すところがポイントです。つまり、1 bit を 1 byte で表して、数値を 0 と 1 の記号列で表すのです。0 と 1 を使って数値を表すので、ほかの記号も変換が必要になります。これはあとで説明します。
数を 2 進数で表す場合、最上位ビットは常に 1 なるので省略することが可能です。Zero Lenght Encoding では、個数 N に 1 を加えて最上位以外のビットを出力しています。たとえば、1 から 10 までの変換結果を示します。
1 => 2 (10) => 0 2 => 3 (11) => 1 3 => 4 (100) => 0 0 4 => 5 (101) => 0 1 5 => 6 (110) => 1 0 6 => 7 (111) => 1 1 7 => 8 (1000) => 0 0 0 8 => 9 (1001) => 0 0 1 9 => 10 (1010) => 0 1 0 0 => 11 (1011) => 0 1 1
0 と 1 を個数の符号に使うため、ほかのデータは次のように変換します。
0x01 - 0xFD => +1 (0x02 - 0xFE) 0xFE => 0xFF, 0x00 0xFF => 0xFF, 0x01
これで、記号 0 をランレングスで符号化することができます。
●参考文献
Zero Length Encoding は、Stephan T. Lavavej さんのページ bwtzip にあるプログラムを参考にさせていただきました。Stephan T. Lavavej さんに感謝いたします。
●プログラム
# coding: utf-8
#
# zle.rb : Zero Length Encoding
#
# Copyright (C) 2006-2023 Makoto Hiroi
#
require 'optparse'
# 符号化
def zle_encode(fin, fout)
c = fin.getbyte
while c
if c == 0
count = 1
count += 1 while (c = fin.getbyte) == 0
count += 1
while count != 1
fout.putc(count & 1)
count >>= 1
end
else
case c
when 0xfe
fout.putc(0xff)
fout.putc(0)
when 0xff
fout.putc(0xff)
fout.putc(1)
else
fout.putc(c + 1)
end
c = fin.getbyte
end
end
end
# 復号
def zle_decode(fin, fout)
c = fin.getbyte
buff = []
while c
if c <= 1
count = 1
buff << c
loop do
c = fin.getbyte
break if c == nil || c > 1
buff << c
end
count = (count << 1) + buff.pop while buff.size > 0
fout.putc(0) while (count -= 1) > 0
else
if c == 0xff
c = fin.getbyte
if c == 0
fout.putc(0xfe)
else
fout.putc(0xff)
end
else
fout.putc(c - 1)
end
c = fin.getbyte
end
end
end
def encode_file(name1, name2)
open(name1, "rb") do |fin|
open(name2, "wb") do |fout|
zle_encode(fin, fout)
end
end
end
def decode_file(name1, name2)
open(name1, "rb") do |fin|
open(name2, "wb") do |fout|
zle_decode(fin, fout)
end
end
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 - s
print e, "\n"
●実行結果
テストデータは Canterbury Corpus で配布されている The Canterbury Corpus です。
# RLE : 単純なランレングス # RLE-3 : 3 文字続いたらランレングス # SRLE : Switched RunLength Encoding # ZLE : Zero Length Encoding ファイル名 サイズ RLE RLE-3 SRLE ZLE ------------------------------------------------------------------- alice29.txt 152,089 289,852 150,130 154,236 152,089 asyoulik.txt 125,179 243,066 125,114 128,227 125,179 cp.html 24,603 46,474 24,722 25,600 24,603 fields.c 11,150 19,838 11,176 11,334 11,150 grammar.lsp 3,721 6,622 3,710 3,790 3,721 kennedy.xls 1,029,744 1,731,778 1,032,453 1,186,806 948,310 lcet10.txt 426,754 804,622 415,099 422,092 426,754 plrabn12.txt 481,861 944,618 481,221 490,117 481,861 ptt5 513,216 152,564 116,342 107,932 125,729 sum 38,240 58,594 35,772 35,743 32,376 xargs.1 4,227 8,294 4,227 4,308 4,227 ------------------------------------------------------------------- 合計 2,810,784 4,306,322 2,399,966 2,570,185 2,335,999
●整数の符号化とビット入出力
ランレングス符号化 (run length encoding) は記号とその連長で符号化する方式です。連長は 8 ビット (0 - 255) の固定長で符号化しましたが、長い連長が少なくて短い連長が多くなる場合、固定長の符号語では無駄が多くなるので効率的に圧縮することはできません。そこで、任意の正整数またはある範囲の正整数をできるだけ短い符号語で符号化する方法が考案されています。これを「整数の符号化」といいます。
有名なところでは P. Elias 氏が開発した「γ符号」と「δ符号」があります。これらの符号はランレングスの連長だけではなく、他のデータ圧縮アルゴリズムにも応用することができます。今回は整数の符号化とともに、必要となるビット単位の入出力ルーチンを作成します。詳しい説明は拙作のページ Algorithms with Python: 整数の符号化 をお読みください。
●仕様
- クラス名: BitIO
- コンストラクタ: BitIO.new(name, mode)
ビットストリームをオープンします。name はオープンするファイル名です。
mode は ROPEN がリードオープンで、WOPEN がライトオープンです。 - close()
ビットストリームをクローズします。 - getbit()
ビットストリームより 1 ビット読み込みます。ファイルの終了は nil を返します。 - getbits(n)
ビットストリームより n ビット読み込みます。ファイルの終了は nil を返します。 - putbit(bit)
ビットストリームへ 1 ビット出力します。 - putbits(n, code)
ビットストリームへ code の下位 n ビットを出力します。 - alpha_encode(n), alpha_decode(), α符号化と復号
- gamma_encode(n), gamma_decode(), γ符号化と復号
- delta_encode(n), delta_decode(), δ符号化と復号
- cbt_encode(n, m, k), cbt_decode(m, k), CBT 符号化と復号
●プログラム
# coding: utf-8
#
# bitio.rb : ビット入出力
#
# Copyright (C) 2006-2023 Makoto Hiroi
#
# 定数の定義
WOPEN = "wb"
ROPEN = "rb"
# クラス定義
class BitIO
def initialize(name, mode)
if mode == ROPEN
@cnt = 0
elsif mode == WOPEN
@cnt = 8
else
raise "BitIO: file mode error"
end
@mode = mode
@file = open(name, mode)
@buff = 0
end
def close
@file.putc(@buff) if @mode == WOPEN && @cnt < 8
@file.close
end
# 1 bit input
def getbit
@cnt -= 1
if @cnt < 0
@buff = @file.getbyte
return nil if @buff == nil
@cnt = 7
end
(@buff >> @cnt) & 1
end
# n bit input
def getbits(n)
v = 0
p = 1 << (n - 1)
while p > 0
v |= p if getbit == 1
p >>= 1
end
v
end
# 1 bit output
def putbit(bit)
@cnt -= 1
@buff |= (1 << @cnt) if bit > 0
if @cnt == 0
@file.putc(@buff)
@buff = 0
@cnt = 8
end
end
# n bits output
def putbits(n, code)
p = 1 << (n - 1)
while p > 0
putbit(p & code)
p >>= 1
end
end
# Elias 符号 (0 を含む)
# α符号
def alpha_encode(n)
putbits(n, 0) if n > 0
putbit(1)
end
def alpha_decode
n = 0
n += 1 while getbit == 0
n
end
# γ符号
def gamma_encode(n)
n1 = 0
n2 = n + 1
n1 += 1 while (n2 >>= 1) > 0
alpha_encode(n1)
putbits(n1, n + 1) if n1 > 0
end
def gamma_decode
n1 = alpha_decode
if n1 > 0
n2 = getbits(n1)
n1 = (1 << n1) + n2 - 1
end
n1
end
# δ符号
def delta_encode(n)
n1 = 0
n2 = n + 1
n1 += 1 while (n2 >>= 1) > 0
gamma_encode(n1)
putbits(n1, n + 1) if n1 > 0
end
def delta_decode
n1 = gamma_decode
if n1 > 0
n2 = getbits(n1)
n1 = (1 << n1) + n2 - 1
end
n1
end
# CBT 符号
def cbt_encode(n, m, k)
limit = (1 << k) - m
if n < limit
putbits(k - 1, n)
else
putbits(k, n + limit)
end
end
def cbt_decode(m, k)
limit = (1 << k) - m
n = getbits(k - 1)
if n >= limit
n = (n << 1) + getbit - limit
end
n
end
end
if __FILE__ == $0
a = BitIO.new("test.dat", WOPEN)
for x in 0...10
a.putbits(8, x)
end
for x in 0...10
a.putbit(x & 1)
end
a.close
b = BitIO.new("test.dat", ROPEN)
for x in 0...10
print b.getbits(8), "\n"
end
for x in 0...10
print b.getbit(), "\n"
end
b.close
a = BitIO.new("test.dat", WOPEN)
for x in 0...33
a.alpha_encode(x)
a.gamma_encode(x)
a.delta_encode(x)
# a.rice_encode(x, 2)
end
a.close
b = BitIO.new("test.dat", ROPEN)
for x in 0...33
print b.alpha_decode(), " ", b.gamma_decode(), " ", b.delta_decode(), "\n" #b.rice_decode(2))
end
b.close
a = BitIO.new("test.dat", WOPEN)
for k, m in [[4, 10], [4, 11], [4, 12]]
for n in 0...m
a.cbt_encode(n, m, k)
end
end
a.close
b = BitIO.new("test.dat", ROPEN)
for k, m in [[4, 10], [4, 11], [4, 12]]
for n in 0...m
print b.cbt_decode(m, k), "\n"
end
end
b.close
end
●ハフマン符号
ハフマン符号でファイルを圧縮するプログラムです。ハフマン符号は 1952 年にハフマン (D.Huffman) が考案した、平均符号長を最小にすることができる符号化法です。詳しい説明は拙作のページ Algorithms with Python: シャノン・ファノ符号とハフマン符号 をお読みください。
●プログラム
# coding: utf-8
#
# huff.rb : ハフマン符号
#
# Copyright (C) 2006-2023 Makoto Hiroi
#
require "optparse"
require "./heap"
require "./bitio"
# 定数
CHAR = 256
# ハフマン木の節
class Sym
include Comparable
attr_accessor :code, :count, :left, :right
def initialize(code, count = 0, left = nil, right = nil)
@code = code
@count = count
@left = left
@right = right
end
def <=>(a)
@count <=> a.count
end
end
# 符号を格納するテーブル
$code_table = Array.new(CHAR)
$code_len = Array.new(CHAR)
# 符号語の生成
def make_code(node, n, code)
if node.code
# leaf
$code_table[node.code] = code
$code_len[node.code] = n
else
make_code(node.left, n + 1, code << 1) # left is 0
make_code(node.right, n + 1, (code << 1) | 1) # right is 1
end
end
# ハフマン木の出力
def write_tree(node, o)
if node.code
# leaf
o.putbit(1)
o.putbits(8, node.code)
else
o.putbit(0)
write_tree(node.left, o)
write_tree(node.right, o)
end
end
# ハフマン木の読み込み
def read_tree(i)
if i.getbit == 1
# leaf
node = Sym.new(i.getbits(8))
else
node = Sym.new(nil)
node.left = read_tree(i)
node.right = read_tree(i)
end
node
end
# ハフマン木の生成
def make_tree(sym_table)
# ヒープの生成
pq = PQueue.new
sym_table.each do |sym|
pq.insert(sym) if sym.count > 0
end
loop do
n1 = pq.delete_min
n2 = pq.delete_min
return n1 unless n2
pq.insert(Sym.new(nil, n1.count + n2.count, n1, n2))
end
end
# 符号化
def encode(infile, outfile)
# 出現頻度表の生成
sym_table = Array.new(CHAR)
for x in 0 ... CHAR
sym_table[x] = Sym.new(x)
end
infile.each_byte do |c|
sym_table[c].count += 1
end
# ハフマン木の生成
root = make_tree(sym_table)
# 符号語の生成
make_code(root, 0, 0)
# ハフマン木の出力
write_tree(root, outfile)
# 符号化
infile.rewind
infile.each_byte do |c|
outfile.putbits($code_len[c], $code_table[c])
end
end
# 符号化
def encode_file(name1, name2)
size = File.size(name1)
infile = open(name1, "rb")
outfile = BitIO.new(name2, WOPEN)
outfile.putbits(32, size)
encode(infile, outfile) if size > 0
infile.close
outfile.close
end
# 復号
def decode(infile, outfile, size)
# ハフマン木の読み込み
root = read_tree(infile)
# 復号
while size > 0
node = root
# 木をたどる
while !node.code
if infile.getbit == 0
node = node.left
else
node = node.right
end
end
# 出力
outfile.putc(node.code)
size -= 1
end
end
# 復号
def decode_file(name1, name2)
infile = BitIO.new(name1, ROPEN)
outfile = open(name2, "wb")
size = infile.getbits(32)
decode(infile, outfile, size) if size > 0
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_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 です。
ファイル名 サイズ Huff 符号化 復号 ------------------------------------------------- alice29.txt 152,089 87,785 0.158 0.182 asyoulik.txt 125,179 75,895 0.137 0.152 cp.html 24,603 16,310 0.030 0.033 fields.c 11,150 7,143 0.015 0.016 grammar.lsp 3,721 2,269 0.006 0.005 kennedy.xls 1,029,744 462,856 0.876 1.014 lcet10.txt 426,754 250,673 0.441 0.507 plrabn12.txt 481,861 275,690 0.499 0.557 ptt5 513,216 106,754 0.271 0.318 sum 38,240 25,968 0.048 0.051 xargs.1 4,227 2,698 0.006 0.006 ------------------------------------------------- 合計 2,810,784 1,314,041 2.487 2.841 符号化と復号の単位 : 秒 実行環境 : Ruby 3.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
●LZSS 符号
LZ 符号は J.Zip と A.Lempel が開発した圧縮法で、「適応型辞書法 (adaptive dictionary method) 」と呼ばれるアルゴリズムです。LZ 符号には多数のバリエーションが存在しますが、「LZ77 符号」と「LZ78 符号」の 2 つに大別されます。LZ77 符号は 1977 年に、LZ78 符号は 1978 年に発表されました。LZ77 符号を「スライド辞書法」、 LZ78 符号を「動的辞書法」と呼ぶ場合があります。
LZ77 符号にも多数のバリエーションがありますが、その中で最も基本的で広く用いられている方法が LZSS 符号です。詳しい説明は拙作のページ Algorithms with Python: LZ77 符号 (LZSS 符号) をお読みください。
●プログラム
# coding: utf-8
#
# lzss.rb : LZSS 符号
#
# Copyright (C) 2006-2023 Makoto Hiroi
#
require "optparse"
require "./bitio"
# 定数
MIN_LEN = 3
MAX_LEN = 18
LEN_BITS = 4
POS_BITS = 13 # スライド窓の大きさ (8192 byte)
# スライド窓
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
# 符号化
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.putbits(LEN_BITS, len - MIN_LEN)
fout.putbits(POS_BITS, rp - s.match_pos - 1)
end
len.times do
s.insert(rp)
rp += 1
rp = s.update(rp) if rp >= s.limit
end
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.getbits(LEN_BITS) + MIN_LEN
pos = rp - (fin.getbits(POS_BITS) + 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
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 です。
ファイル名 サイズ LZSS 符号化 復号 ------------------------------------------------ alice29.txt 152,089 68,332 0.286 0.159 asyoulik.txt 125,179 61,789 0.257 0.137 cp.html 24,603 10,278 0.057 0.026 fields.c 11,150 3,859 0.018 0.013 grammar.lsp 3,721 1,594 0.010 0.007 kennedy.xls 1,029,744 291,968 1.600 0.779 lcet10.txt 426,754 184.684 0.811 0.426 plrabn12.txt 481,861 247,780 1.016 0.538 ptt5 513,216 107,289 2.489 0.338 sum 38,240 17,500 0.128 0.042 xargs.1 4,227 2,198 0.010 0.008 ------------------------------------------------ 合計 2,810,784 997,271 6.682 2.473 符号化と復号の単位 : 秒 実行環境 : Ruby 3.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
●LZW 符号
LZW 符号でファイルを圧縮するプログラムです。LZ78 符号には多数のバリエーションがありますが、その中で最も基本的で広く用いられている符号が、1984 年に T. Welch が開発した LZW 符号です。詳しい説明は拙作のページ Algorithms with Python: LZ78 符号 (LZW 符号) をお読みください。
●プログラム
# coding: utf-8
#
# lzw.rb : LZW 符号
#
# Copyright (C) 2006-2023 Makoto Hiroi
#
require "optparse"
require "./bitio"
# 辞書の大きさ (8192)
DIC_SIZE = 13
# 節
class Node
attr_accessor :code, :parent
def initialize(code, parent)
@code = code
@parent = parent
end
end
# トライはハッシュ法で実装
class Dic
attr_reader :len
def initialize(size)
@dic_size = size
@buff = []
@hash = {}
@len = 0
256.times do |c|
@buff << Node.new(c, nil)
end
end
# 符号化
def encode(file, c)
file.putbits(@dic_size, c)
end
# 復号
def decode(file)
file.getbits(@dic_size)
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 << @dic_size)
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 です。
ファイル名 サイズ LZW 符号化 復号 ------------------------------------------------ alice29.txt 152,089 68,448 0.131 0.205 asyoulik.txt 125,179 59,085 0.119 0.176 cp.html 24,603 12,150 0.030 0.041 fields.c 11,150 5,760 0.016 0.019 grammar.lsp 3,721 2,294 0.008 0.010 kennedy.xls 1,029,744 339,542 0.650 1.072 lcet10.txt 426,754 194,996 0.350 0.548 plrabn12.txt 481,861 220,850 0.402 0.607 ptt5 513,216 66,101 0.194 0.400 sum 38,240 30,163 0.057 0.079 xargs.1 4,227 2,916 0.008 0.011 ------------------------------------------------ 合計 2,810,784 1,002,305 1.965 3.168 符号化と復号の単位 : 秒 実行環境 : Ruby 3.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz