bwt.rb

#!/usr/bin/env ruby
#
# https://qiita.com/erukiti/items/f11f448d3f4d73fbc1f9
# https://research.preferred.jp/2012/11/burrows-wheeler-transform-lf-mapping/
#

class BWT

  def initialize(str)
    @str = str + '$'
    @len = @str.length

    @ary = permute.sort
    puts @ary if $DEBUG
    @bwt = make_bwt
    @l = @bwt.split('')
    @f = @l.sort
    puts "L: " + @l.join('')
    puts "F: " + @f.join('')
  end

  def permute
    ary = []
    @len.times do |i|
      ary << @str[i, @len - i] + @str[0, i]
    end
    return ary
  end

  def make_bwt
    bwt = ''
    @ary.each do |str|
      bwt += str[-1]
    end
    return bwt
  end

  def rank(i, c)
    @l[0, i].count(c)
  end

  def rank_less_than(c)
    unless @cache
      @cache = {}
      count = 0
      prev_x = ''
      @f.each do |x|
        if x != prev_x
          @cache[x] = count
        end
        prev_x = x
        count += 1
      end
      puts @cache.inspect if $DEBUG
    end
    @cache[c]
  end

  def search(str, b = 0, e = @len)
    c = str[-1]
    b = rank(b, c) + rank_less_than(c)
    e = rank(e, c) + rank_less_than(c)
    puts [c, b, e].inspect if $DEBUG
    if b < e
      if str.length > 1
        str_next = str[0, str.length - 1]
        search(str_next, b, e)
      else
        return @ary[b..(e-1)]
      end
    end
  end

end

string = ARGV.shift || 'abracadabra'
query  = ARGV.shift || 'bra'

bwt = BWT.new(string)
puts bwt.search(query)