The Lempel-Ziv-Welch (LZW) algorithm provides loss-less data compression.

You can read a complete description of it in the   Wikipedia article   on the subject.   It was patented, but it entered the public domain in 2004.




with javascript_semantics
function compress(string uncompressed)
integer dict = new_dict()
sequence result = {}
integer dictSize = 255, c
string word = ""
    for i=0 to 255 do
        setd(""&i,i,dict)
    end for
    for i=1 to length(uncompressed) do
        c = uncompressed[i]
        if getd_index(word&c,dict) then
            word &= c
        else
            result &= getd(word,dict)
            dictSize += 1
            setd(word&c,dictSize,dict)
            word = ""&c
        end if
    end for
    if word!="" then
        result &= getd(word,dict)
    end if
    destroy_dict(dict)
    return result
end function
 
function decompress(sequence compressed)
integer dict = new_dict()
integer dictSize = 255, k, ki
string dent = "", result = "", word = ""
    for i=0 to 255 do
        setd(i,""&i,dict)
    end for
    for i=1 to length(compressed) do
        k = compressed[i]
        ki = getd_index(k,dict)
        if ki then
            dent = getd_by_index(ki,dict)
        elsif k=dictSize then
            dent = word&word[1]
        else
            return {NULL,i}
        end if
        result &= dent
        setd(dictSize,word&dent[1],dict)
        dictSize += 1
        word = dent
    end for
    destroy_dict(dict)
    return result
end function
 
constant example = "TOBEORNOTTOBEORTOBEORNOT"
sequence com = compress(example)
pp(com,{pp_IntCh,true,pp_Maxlen,90})
?decompress(com)
