LZW Compression

local let=" !#$%&'\"()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
local dict,dlen=let,#let
do local t={}for x in let:gmatch'.'do t[x]=#t t[#t+1]=x end let=t end
function short(n)local s=''repeat s,n=let[n%dlen+1]..s,math.floor(n/dlen)until n==0 return s end
function long(n)local r=0 for i=1,#n do r=r+dlen^(i-1)*let[n:sub(-i,-i)]end return r end

function compress(text)
    local dict=dict
    do local t={}for x in dict:gmatch'.'do t[#t+1]=x t[x]=#t end dict=t end
    local s,result='',{}
    for c in text:gmatch'.'do
        local x=s..c
        if dict[x]then
            s=x
        else
            result[#result+1]=dict[s]
            dict[x]=#dict+1
            s=c
        end
    end
    result[#result+1]=dict[s]
    local width,r=1
    for i,v in ipairs(result)do
        r=short(v)
        if #r>width then width=#r end
        result[i]=r
    end
    if width>1 then
        for i,v in ipairs(result)do
            result[i]=(' '):rep(width-#v)..v
        end
    end
    return width..'|'..table.concat(result)
end

function decompress(text)
    local dict=dict
    do local t={}for x in dict:gmatch'.'do t[#t+1]=x t[x]=#t end dict=t end
    local data,width,text={},text:match("(%d+)|(.*)")
    for c in text:gmatch(('.'):rep(width))do data[#data+1]=long(c)end
    local prev,curr,entry=data[1]
    local result={dict[prev]}
    for i=2,#data do
        curr=data[i]
        entry=dict[curr]
        if entry then
            result[i]=entry
            dict[#dict+1]=dict[prev]..entry:sub(1,1)
        else
            result[i]=dict[prev]..dict[prev]:sub(1,1)
            dict[#dict+1]=result[i]
        end
        prev=curr
    end
    return table.concat(result)
end

local a=[=[long example text]=]

local b=compress(a)
print(#a,#b,#a-#b,(#a-#b)*100/#a)
print(b:sub(1,200))
print(decompress(b)==a)
print(os.clock())