Burrows–Wheeler transform: Difference between revisions
Content added Content deleted
(Added solution for Pascal (Lazarus)) |
|||
| Line 1,120: | Line 1,120: | ||
--> |
--> |
||
</pre> |
</pre> |
||
=={{header|Lua}}== |
|||
{{trans|Java}} |
|||
<lang lua>STX = string.char(tonumber(2,16)) |
|||
ETX = string.char(tonumber(3,16)) |
|||
function bwt(s) |
|||
if s:find(STX, 1, true) then |
|||
error("String cannot contain STX") |
|||
end |
|||
if s:find(ETX, 1, true) then |
|||
error("String cannot contain ETX") |
|||
end |
|||
local ss = STX .. s .. ETX |
|||
local tbl = {} |
|||
for i=1,#ss do |
|||
local before = ss:sub(i + 1) |
|||
local after = ss:sub(1, i) |
|||
table.insert(tbl, before .. after) |
|||
end |
|||
table.sort(tbl) |
|||
local sb = "" |
|||
for _,v in pairs(tbl) do |
|||
sb = sb .. string.sub(v, #v, #v) |
|||
end |
|||
return sb |
|||
end |
|||
function ibwt(r) |
|||
local le = #r |
|||
local tbl = {} |
|||
for i=1,le do |
|||
table.insert(tbl, "") |
|||
end |
|||
for j=1,le do |
|||
for i=1,le do |
|||
tbl[i] = r:sub(i,i) .. tbl[i] |
|||
end |
|||
table.sort(tbl) |
|||
end |
|||
for _,row in pairs(tbl) do |
|||
if row:sub(le,le) == ETX then |
|||
return row:sub(2, le - 1) |
|||
end |
|||
end |
|||
return "" |
|||
end |
|||
function makePrintable(s) |
|||
local a = s:gsub(STX, '^') |
|||
local b = a:gsub(ETX, '|') |
|||
return b |
|||
end |
|||
function main() |
|||
local tests = { |
|||
"banana", |
|||
"appellee", |
|||
"dogwood", |
|||
"TO BE OR NOT TO BE OR WANT TO BE OR NOT?", |
|||
"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES", |
|||
STX .. "ABC" .. ETX |
|||
} |
|||
for _,test in pairs(tests) do |
|||
print(makePrintable(test)) |
|||
io.write(" --> ") |
|||
local t = "" |
|||
if xpcall( |
|||
function () t = bwt(test) end, |
|||
function (err) print("ERROR: " .. err) end |
|||
) then |
|||
print(makePrintable(t)) |
|||
end |
|||
local r = ibwt(t) |
|||
print(" --> " .. r) |
|||
print() |
|||
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| |
|||
--> ERROR: bwt.lua:6: String cannot contain STX |
|||
--></pre> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||