M.Hiroi's Home Page
http://www.geocities.jp/m_hiroi/

Ruby Programming

Ruby Junk Scripts

[ PrevPage | R u b y | NextPage ]

LZB 符号

LZB 符号でファイルを圧縮するプログラムです。1987 年に T. C. Bell が開発した LZB 符号は、一致長の符号化にγ符号を、位置の符号化に可変長符号 (CBT 符号) を用いて LZSS 符号の圧縮率を改善する方法です。

●プログラム

#
# lzb.rb : LZB 符号
#
#           Copyright (C) 2006 Makoto Hiroi
#
require "bitio"
require "optparse"

# 定数
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.getc
      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
    print "option error"
  elsif eflag
    encode_file(ARGV[0], ARGV[1])
  elsif dflag
    decode_file(ARGV[0], ARGV[1])
  else
    print "option error"
  end
end

# 実行
s = Time.now
main
e = Time.now
print 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    9.42   2,77
  asyoulik.txt   125,179   54,736    7.50   2.44
  cp.html         24,603    8,973    0.88   0.44
  fields.c        11,150    3,513    0.39   0.17
  grammar.lsp      3,721    1,424    0.13   0.06
  kennedy.xls  1,029,744  328,111   47.41  15.72
  lcet10.txt     426,754  162,247   25.56   7.50
  plrabn12.txt   481,861  218,902   34.83   9.69
  ptt5           513,216   69,737  453.31   4.89
  sum             38,240   15,078    3.89   0.69
  xargs.1          4,227    1,985    0.16   0.09
  -----------------------------------------------
  合計         2,810,784  925,143  583.48  44.46

# 符号化と復号の単位 : 秒
# Windows XP, Celeron 1,40 GHz, Ruby 1.8.3 で実行

LZW 符号の改良

CBT 符号を用いて LZW 符号の圧縮率を改善します。

●プログラム

#
# lzw1.rb : LZW 符号 + CBT 符号
#
#          Copyright (C) 2006 Makoto Hiroi
#
require "bitio"
require "optparse"

# 辞書の大きさ
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)
    @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.getc
  while c = fin.getc
    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 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
    print "option error"
  elsif eflag
    encode_file(ARGV[0], ARGV[1])
  elsif dflag
    decode_file(ARGV[0], ARGV[1])
  else
    print "option error"
  end
end

# 実行
s = Time.now
main
e = Time.now - s
print e

●実行結果

テストデータは 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   2.83   3.44
  asyoulik.txt   125,179    54,117   2.50   2.95
  cp.html         24,603    10,877   0.55   0.63
  fields.c        11,150     4,810   0.27   0.27
  grammar.lsp      3,721     1,747   0.11   0.89
  kennedy.xls  1,029,744   338,206  14.58  19.11
  lcet10.txt     426,754   168,556   7.22   9.05
  plrabn12.txt   481,861   200,493   8.48  10.50
  ptt5           513,216    61,101   3.77   6.14
  sum             38,240    19,473   0.92   1.06
  xargs.1          4,227     2,249   0.13   0.13
  -----------------------------------------------
  合計         2,810,784   922,752  41.36  54.17

# 符号化と復号の単位 : 秒
# Windows XP, Celeron 1,40 GHz, Ruby 1.8.3 で実行

LZT 符号

LZT 符号によるファイルの圧縮プログラムです。LZT 符号は 1987 年に Tischer によって開発されました。LZT 符号のおもな改良点は、辞書が満杯になった場合、長い間使われていない (最長時間未使用 : Least Recently Used) 語を取り除くことで辞書の空きスペースを作るところです。このような操作を「LRU スキーム」と呼びます。LZT 符号は LRU スキームを行うため符号化と復号に時間がかかることになりますが、少ないメモリでも高い圧縮率を期待することができます。

●プログラム

#
# lzt.rb : LZT 符号 + CBT 符号
#
#          Copyright (C) 2006 Makoto Hiroi
#
require "bitio"
require "optparse"

# 辞書の大きさ
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.getc
  while c = fin.getc
    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
    print "option error"
  elsif eflag
    encode_file(ARGV[0], ARGV[1])
  elsif dflag
    decode_file(ARGV[0], ARGV[1])
  else
    print "option error"
  end
end

# 実行
s = Time.now
main
e = Time.now - s
print e

●実行結果

テストデータは 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   3.91   4.58
  asyoulik.txt   125,179    54,117   3.31   3.91
  cp.html         24,603    10,877   0.69   0.81
  fields.c        11,150     4,810   0.30   0.36
  grammar.lsp      3,721     1,747   0.11   0.14
  kennedy.xls  1,029,744   303,277  22.86  28.17
  lcet10.txt     426,754   163,278  11.02  13.38
  plrabn12.txt   481,861   198,821  13.08  15.73
  ptt5           513,216    61,064   7.39   9.78
  sum             38,240    19,473   1.16   1.36
  xargs.1          4,227     2,249   0.14   0.16
  -----------------------------------------------
  合計         2,810,784   880,810  63.97  78.38

# 符号化と復号の単位 : 秒
# Windows XP, Celeron 1,40 GHz, Ruby 1.8.3 で実行

Copyright (C) 2006 Makoto Hiroi
All rights reserved.

[ PrevPage | R u b y | NextPage ]