class BurrowsWheeler::Transform

Public Class Methods

decode(inp, out) click to toggle source
# File lib/burrows_wheeler/transform.rb, line 29
def decode(inp, out)
  # read uint64_t
  first = inp.read(8).unpack('Q').first
  data = inp.read.split('')
  column = data.sort

  length = data.length

  index = {}
  nxt = Array.new(length)

  j = 0
  while j < length
    index[column[j]] = j
    j += 1 while j < length - 1 && column[j] == column[j + 1]
    j += 1
  end

  (0..length - 1).each do |i|
    char = data[i]
    nxt[index[char]] = i
    index[char] += 1
  end

  (0..length - 1).each do
    out.write(column[first])
    first = nxt[first]
  end

  out.flush
end
encode(inp, out) click to toggle source
# File lib/burrows_wheeler/transform.rb, line 7
def encode(inp, out)
  str = inp.read
  csa = CircularSuffixArray.new(str)
  first = -1

  symbols = []

  (0..str.length - 1).each do |i|
    idx = csa[i]
    cs = CircularString.new(str, idx)
    symbols << cs.last
    first = i if idx == 0
  end

  # write uint64_t
  out.write([first].pack('Q'))

  symbols.each { |c| out.write(c) }

  out.flush
end