class lzw
    -- Compress a string to a list of output symbols.
    static function compress(uncompressed)
        -- Build the dictionary.
        local dict_size = 256
        local dictionary = {}
        for i = 0, dict_size - 1 do dictionary[string.char(i)] = i end
        local w = ""
        local result = {}
        local len = #uncompressed
        for {string.byte(uncompressed, 1, len)} as c do
            local cs = string.char(c)
            local wc = w .. cs
            if dictionary[wc] then
                w = wc
            else
                result:insert(dictionary[w])
                -- Add wc to the dictionary.
                dictionary[wc] = dict_size
                dict_size += 1
                w = cs
            end
        end

        -- Output the code for w
        if w != "" then result:insert(dictionary[w]) end
        return result
    end

    -- Decompress a list of output symbols to a string.
    static function decompress(compressed)
        -- Build the dictionary.
        local dict_size = 256
        local dictionary = {}
        for i = 0, dict_size - 1 do dictionary[i] = string.char(i) end
        local w = string.char(compressed[1])
        local result = w
        for i = 2, #compressed do
            local k = compressed[i]
            local entry
            if dictionary[k] then
                entry = dictionary[k]
            elseif k == dict_size then
                entry = w .. string.char(string.byte(w[1]))
            else
                error($"Bad compressed k: {k}")
            end
            result ..= entry

            -- Add w .. entry[1] to the dictionary.
            dictionary[dict_size] = w .. string.char(string.byte(entry[1]))
            dict_size += 1
            w = entry
        end
        return result
    end
end

local compressed = lzw.compress("TOBEORNOTTOBEORTOBEORNOT")
print(compressed:concat(", "))
local decompressed = lzw.decompress(compressed)
print(decompressed)