Burrows–Wheeler transform: Difference between revisions
Content added Content deleted
| Line 1,501: | Line 1,501: | ||
***error*** BWT: The input string contains an invalid character at position 15. |
***error*** BWT: The input string contains an invalid character at position 15. |
||
</pre> |
</pre> |
||
=={{header|Ruby}}== |
|||
{{trans|C#}} |
|||
<lang ruby>STX = "\u0002" |
|||
ETX = "\u0003" |
|||
def bwt(s) |
|||
for c in s.split('') |
|||
if c == STX or c == ETX then |
|||
raise ArgumentError.new("Input can't contain STX or ETX") |
|||
end |
|||
end |
|||
ss = ("%s%s%s" % [STX, s, ETX]).split('') |
|||
table = [] |
|||
for i in 0 .. ss.length - 1 |
|||
table.append(ss.join) |
|||
ss = ss.rotate(-1) |
|||
end |
|||
table = table.sort |
|||
return table.map{ |e| e[-1] }.join |
|||
end |
|||
def ibwt(r) |
|||
len = r.length |
|||
table = [""] * len |
|||
for i in 0 .. len - 1 |
|||
for j in 0 .. len - 1 |
|||
table[j] = r[j] + table[j] |
|||
end |
|||
table = table.sort |
|||
end |
|||
for row in table |
|||
if row[-1] == ETX then |
|||
return row[1 .. -2] |
|||
end |
|||
end |
|||
return "" |
|||
end |
|||
def makePrintable(s) |
|||
s = s.gsub(STX, "^") |
|||
return s.gsub(ETX, "|") |
|||
end |
|||
def main |
|||
tests = [ |
|||
"banana", |
|||
"appellee", |
|||
"dogwood", |
|||
"TO BE OR NOT TO BE OR WANT TO BE OR NOT?", |
|||
"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES", |
|||
"\u0002ABC\u0003" |
|||
] |
|||
for test in tests |
|||
print makePrintable(test), "\n" |
|||
print " --> " |
|||
begin |
|||
t = bwt(test) |
|||
print makePrintable(t), "\n" |
|||
r = ibwt(t) |
|||
print " --> ", r, "\n\n" |
|||
rescue ArgumentError => e |
|||
print e.message, "\n" |
|||
print " -->\n\n" |
|||
end |
|||
end |
|||
end |
|||
main()</lang> |
|||
{{out}} |
|||
<pre>banana |
|||
--> |annb^aa |
|||
--> banana |
|||
appellee |
|||
--> |e^elplepa |
|||
--> appellee |
|||
dogwood |
|||
--> |do^oodwg |
|||
--> dogwood |
|||
TO BE OR NOT TO BE OR WANT TO BE OR NOT? |
|||
--> |?OOORREEETTRTW BBB ATTT NNOOONOO^ |
|||
--> TO BE OR NOT TO BE OR WANT TO BE OR NOT? |
|||
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES |
|||
--> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT |
|||
--> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES |
|||
^ABC| |
|||
--> Input can't contain STX or ETX |
|||
--></pre> |
|||
=={{header|Scala}}== |
=={{header|Scala}}== |
||