29 lines
756 B
Text
29 lines
756 B
Text
class BurrowsWheelerTransform (String L = "\002") {
|
|
|
|
method encode(String s) {
|
|
assert(!s.contains(L), "String cannot contain `#{L.dump}`")
|
|
s = (L + s)
|
|
s.len.of{|i| s.substr(i) + s.substr(0, i) }.sort.map{.last}.join
|
|
}
|
|
|
|
method decode(String s) {
|
|
var t = s.len.of("")
|
|
var c = s.chars
|
|
{ t = (c »+« t).sort } * s.len
|
|
t.first { .begins_with(L) }.substr(L.len)
|
|
}
|
|
}
|
|
|
|
var tests = [
|
|
"banana", "appellee", "dogwood", "TOBEORNOTTOBEORTOBEORNOT"
|
|
"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
|
|
]
|
|
|
|
var bwt = BurrowsWheelerTransform(L: '$')
|
|
|
|
tests.each { |str|
|
|
var enc = bwt.encode(str)
|
|
var dec = bwt.decode(enc)
|
|
say "BWT(#{dec.dump}) = #{enc.dump}"
|
|
assert_eq(str, dec)
|
|
}
|