62 lines
1.9 KiB
Text
62 lines
1.9 KiB
Text
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)
|