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

Ruby Programming

Ruby Junk Scripts

[ PrevPage | R u b y | NextPage ]

データ圧縮

データ圧縮関連のプログラムです。

●参考文献

  1. 植松友彦, 『文書データ圧縮アルゴリズム入門』, CQ出版社, 1994
  2. 奥村晴彦, 『C言語による最新アルゴリズム事典』, 技術評論社, 1991
  3. 奥村晴彦, 『データ圧縮の基礎から応用まで』, C MAGAZINE 2002 年 7 月号, ソフトバンク
  4. 井谷宣子, 吉田茂, 『圧縮ソフト SLC/ELC のアルゴリズム』, C MAGAZINE 2004 年 10 月号, ソフトバンク

●ビット入出力

ビット単位で入出力を行うプログラムです。

●プログラム

#
# bitio.rb : ビット入出力
#
#            Copyright (C) 2006 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.getc
      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

ハフマン符号

ハフマン符号でファイルを圧縮するプログラムです。ハフマン符号は 1952 年にハフマン (D.Huffman) が考案した、平均符号長を最小にすることができる符号化法です。

●プログラム

#
# huff.rb : ハフマン符号
#
#           Copyright (C) 2006 Makoto Hiroi
#
require "heap"
require "bitio"
require "optparse"

# 定数
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)
  # ヒープの生成
  heap = Heap.new
  sym_table.each do |sym|
    heap.insert(sym) if sym.count > 0
  end
  loop do
    n1 = heap.delete_min
    n2 = heap.delete_min
    return n1 unless n2
    heap.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
    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 です。

  ファイル名      サイズ      Huff   符号化  復号 
  ------------------------------------------------
  alice29.txt    152,089     87,785   3.31   2.81
  asyoulik.txt   125,179     75,895   2.83   2.42
  cp.html         24,603     16,310   0.61   0.52
  fields.c        11,150      7,143   0.28   0.22
  grammar.lsp      3,721      2,269   0.11   0.06
  kennedy.xls  1,029,744    462,856  18.39  15.67
  lcet10.txt     426,754    250,673   9.36   8.00
  plrabn12.txt   481,861    275,690  10.36   8.86
  ptt5           513,216    106,754   5.75   4.58
  sum             38,240     25,968   0.98   0.83
  xargs.1          4,227      2,698   0.11   0.09
  ------------------------------------------------
  合計         2,810,784  1,314,041  52.09  44.06

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

スプレイ符号

スプレイ符号 (Splay Tree Coding) でファイルを圧縮するプログラムです。スプレイ符号は「動的符号化」の一種で、符号木に対して出現した記号の符号語長が半分になるようにスプレイ操作を適用することにより、頻繁に現れる記号に短い符号語を割り当てることができます。

●プログラム

#
# splay.rb : スプレイ符号
#
#            Copyright (C) 2006 Makoto Hiroi
#
require "bitio"
require "optparse"

# ファイルの終了
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
    print "option error"
  elsif eflag
    encode(ARGV[0], ARGV[1])
  elsif dflag
    decode(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 です。

  ファイル名      サイズ     Splay   符号化  復号 
  ------------------------------------------------
  alice29.txt    152,089    104,800   6.92   6.25
  asyoulik.txt   125,179     90,108   5.95   5.34
  cp.html         24,603     18,931   1.25   1.11
  fields.c        11,150      7,875   0.52   0.47
  grammar.lsp      3,721      2,497   0.17   0.16
  kennedy.xls  1,029,744    501,392  33.88  31.36
  lcet10.txt     426,754    289,971  19.16  17.31
  plrabn12.txt   481,861    336,093  22.19  20.00
  ptt5           513,216    109,677   7.64   7.67
  sum             38,240     23,580   1.64   1.42
  xargs.1          4,227      3,047   0.20   0.19
  ------------------------------------------------
  合計         2,810,784  1,487,971  99.52  91.28

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

LZSS 符号

LZSS 符号でファイルを圧縮するプログラムです。LZ 符号は J.Zip と A.Lempel が開発した圧縮法で、「適応型辞書法 (adaptive dictionary method) 」と呼ばれるアルゴリズムです。LZ 符号には多数のバリエーションが存在しますが、「LZ77 符号」と「LZ78 符号」の 2 つに大別されます。LZ77 符号は 1977 年に、LZ78 符号は 1978 年に発表されました。LZ77 符号を「スライド辞書法」、 LZ78 符号を「動的辞書法」と呼ぶ場合があります。

LZ77 符号には多数のバリエーションがありますが、その中で最も基本的で広く用いられている方法が LZSS 符号です。

●プログラム

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

# 定数
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.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

# 符号化
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
    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 です。

  ファイル名      サイズ     LZSS   符号化  復号
  -----------------------------------------------
  alice29.txt    152,089    68,332   6.88   2.91
  asyoulik.txt   125,179    61,789   5.70   2.56
  cp.html         24,603    10,278   0.92   0.45
  fields.c        11,150     3,859   0.39   0.17
  grammar.lsp      3,721     1,594   0.13   0.08
  kennedy.xls  1,029,744   291,968  36.36  14.39
  lcet10.txt     426,754   184.684  18.77   7.94
  plrabn12.txt   481,861   247,780  23.70  10.20
  ptt5           513,216   107,289  94.95   5.95
  sum             38,240    17,500   3.16   0.73
  xargs.1          4,227     2,198   0.16   0.09
  -----------------------------------------------
  合計         2,810,784   997,271 191.12  45.57

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

LZW 符号

LZW 符号でファイルを圧縮するプログラムです。LZ78 符号には多数のバリエーションがありますが、その中で最も基本的で広く用いられている符号が、1984 年に T. Welch が開発した LZW 符号です。

●プログラム

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

# 辞書の大きさ (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.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 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 です。

  ファイル名      サイズ     LZW    符号化  復号
  ------------------------------------------------
  alice29.txt    152,089    68,448   2.72   3.30
  asyoulik.txt   125,179    59,085   2.34   2.80
  cp.html         24,603    12,150   0.52   0.61
  fields.c        11,150     5,760   0.25   0.28
  grammar.lsp      3,721     2,294   0.11   0.11
  kennedy.xls  1,029,744   339,542  13.89  18.08
  lcet10.txt     426,754   194,996   7.63   9.23
  plrabn12.txt   481,861   220,850   8.66  10.44
  ptt5           513,216    66,101   3.63   5.84
  sum             38,240    30,163   1.13   1.28
  xargs.1          4,227     2,916   0.13   0.14
  ------------------------------------------------
  合計         2,810,784 1,002,305  41.01  52.11

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

Copyright (C) 2006 Makoto Hiroi
All rights reserved.

[ PrevPage | R u b y | NextPage ]