Skip to content

Instantly share code, notes, and snippets.

@ktym

ktym/bwt.rb

Created Sep 29, 2018
Embed
What would you like to do?
#!/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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment