お気楽 Ruby プログラミング入門

●LZB 符号

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

●LZW 符号の改良

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 符号

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

●参考文献

• 井谷宣子, 吉田茂, 『圧縮ソフト SLC/ELC のアルゴリズム』, C MAGAZINE 2004 年 10 月号, ソフトバンク

●レンジコーダ

レンジコーダ (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