データ圧縮関連のプログラムです。
「ランレングス (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 --------------------------------------------- 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 (SRLE) はランレングスとそうでない部分に分けて符号化します。SRLE の特徴は、2 つの部分を区別するためのフラグをデータに追加するのではなく、LITERAL と FILL という 2 つのモードを使って管理するところです。次の例を見てください。
(1) LITERAL : a b c d e e e e f f f f f f f => 5 a b c d e ----------- 記号が連続しているところを探す (2) FILL : a b c d e e e e f f f f f f f => 5 a b c d e 3 ----- 記号 e の数を数える (3) LITERAL : a b c d e e e e f f f f f f f => 5 a b c d e 3 1 f --- 記号が連続しているところを探す (4) FILL : a b c d e e e e f f f f f f f => 5 a b c d e 3 1 f 6 ----------- 記号 f の数を数える
モードは最初 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 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
記号 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 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: 整数の符号化 をお読みください。
# 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
ファイル名 サイズ 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
テストデータは Canterbury Corpus で配布されている The Canterbury Corpus です。
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 符号でファイルを圧縮するプログラムです。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