Skip to content

Instantly share code, notes, and snippets.

@Najaf

Najaf/bwt.rb

Created May 2, 2017
Embed
What would you like to do?
Rough implementation of Burrows-Wheeler
# Rough implementation of BW transform
# As described at the wikipedia page: https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform
EOF_CHAR = '|'
def bwt(string)
string_with_eof = string + EOF_CHAR
rotations = []
0.upto(string_with_eof.length - 1) do |i|
rotations << string_with_eof.chars.rotate(i).join
end
rotations.sort.reduce('') do |memo, rotation|
memo += rotation.chars.last
memo
end
end
def inverse_bwt(string)
rotations = []
string.length.times { rotations << [] }
string.length.times do
rotations.each_with_index do |rotation, index|
rotations[index].unshift(string[index])
end
rotations.sort_by! do |rotation|
rotation.join
end
end
inverse_array = rotations.select do |rotation|
rotation.last == EOF_CHAR
end
inverse = inverse_array.first.join
inverse.chomp(EOF_CHAR)
end
string = "^BANANA"
puts inverse_bwt(bwt(string)).inspect
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment