An implementation of the Burrows–Wheeler transform that satisfies https://github.com/zetter/burrows-wheeler-transform

bwt.rb

class BWT
  def encode(string)
    chars = string.chars + ['$']
    chars.each_index.map(&chars.method(:rotate)).sort.map(&:last).join
  end

  def decode(string)
    chars = string.chars
    chars.inject([]) { |table| chars.zip(table).sort }.
      map(&:join).detect { |s| s.end_with?('$') }.chop
  end
end