

 This page uses content from Wikipedia. The original article was at Burrows–Wheeler_transform. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



The Burrows–Wheeler transform (BWT, also called block-sorting compression) rearranges a character string into runs of similar characters.

This is useful for compression, since it tends to be easy to compress a string that has runs of repeated characters by techniques such as move-to-front transform and run-length encoding.

More importantly, the transformation is reversible, without needing to store any additional data.

The BWT is thus a "free" method of improving the efficiency of text compression algorithms, costing only some extra computation.



Source: Burrows–Wheeler transform

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()