local k,d={},0 for N=32,127,1 do if N~=34 and N~=92 then local y=string.char(N)k[y],k[d]=d,y d=d+1 end end local N={}for k=1,34,1 do k=({34;92,127})[k-31]or k local d,y=string.char(k),string.char(k+31)N[d],N[y]=y,d end local function y(k)return k:gsub("\091\037\099\"\092\093",function(k)return"\127"..N[k]end)end local function u(k)return k:gsub("\127\040\046\041",function(k)return N[k]end)end local function h(k)local d={}for k,N in pairs(k)do d[k]=N end return d end local function n(d)local N=""repeat local y=d%93 N=k[y]..N d=(d-y)/93 until d==0 return N end local function c(d)local N=0 for y=1,#d,1 do N=N+93^(y-1)*k[d:sub(-y,-y)]end return N end local function C(d)local N=h(k)local u,c,C="",{},#N local B,o,t=1,{},0 local function w(k)local d=n(N[k])if#d>B then B,t,o[B]=#d,0,t end c[#c+1]=(" "):rep(B-#d)..d t=t+1 end d=y(d)for k=1,#d,1 do local y=d:sub(k,k)local h=u..y if N[h]then u=h else w(u)u,C=y,C+1 N[h],N[C]=C,h end end w(u)o[B]=t return table.concat(o,"\044")..("\124"..table.concat(c))end local function B(d)local N=h(k)local y,n,C={},d:match("\040\046-\041\124\040\046\042\041")local B,o={},1 for k in n:gmatch("\037\100\043")do local d=#B+1 B[d]=C:sub(o,(o+k*d)-1)o=o+k*d end local t for k=1,#B,1 do for k in B[k]:gmatch(("\046"):rep(k))do local d=N[c(k)]if t then if d then y[#y+1]=d N[#N+1]=t..d:sub(1,1)else d=t..t:sub(1,1)y[#y+1]=d N[#N+1]=d end else y[1]=d end t=d end end return u(table.concat(y))end return{compress=C,decompress=B}
local dictionary, length = {}, 0
for i = 32, 127 do
	if i ~= 34 and i ~= 92 then
		local c = string.char(i)
		dictionary[c], dictionary[length] = length, c
		length = length + 1
	end
end

local escapemap = {}
for i = 1, 34 do
	i = ({34, 92, 127})[i-31] or i
	local c, e = string.char(i), string.char(i + 31)
	escapemap[c], escapemap[e] = e, c
end
local function escape(s)
	return (s:gsub("[%c\"\\]", function(c)
		return "\127"..escapemap[c]
	end))
end

local function unescape(s)
	return (s:gsub("\127(.)", function(c)
		return escapemap[c]
	end))
end

local function copy(t)
	local new = {}
	for k, v in pairs(t) do
		new[k] = v
	end
	return new
end

local function tobase93(n)
	local value = ""
	repeat
		local remainder = n%93
		value = dictionary[remainder]..value
		n = (n - remainder)/93
	until n == 0
	return value
end

local function tobase10(value)
	local n = 0
	for i = 1, #value do
		n = n + 93^(i-1)*dictionary[value:sub(-i, -i)]
	end
	return n
end

local function compress(text)
	local dictionary = copy(dictionary)
	local key, sequence, size = "", {}, #dictionary
	local width, spans, span = 1, {}, 0
	local function listkey(key)
		local value = tobase93(dictionary[key])
		if #value > width then
			width, span, spans[width] = #value, 0, span
		end
		sequence[#sequence+1] = (" "):rep(width - #value)..value
		span = span + 1
	end
	text = escape(text)
	for i = 1, #text do
		local c = text:sub(i, i)
		local new = key..c
		if dictionary[new] then
			key = new
		else
			listkey(key)
			key, size = c, size+1
			dictionary[new], dictionary[size] = size, new
		end
	end
    listkey(key)
	spans[width] = span
    return table.concat(spans, ",").."|"..table.concat(sequence)
end

local function decompress(text)
	local dictionary = copy(dictionary)
	local sequence, spans, content = {}, text:match("(.-)|(.*)")
	local groups, start = {}, 1
	for span in spans:gmatch("%d+") do
		local width = #groups+1
		groups[width] = content:sub(start, start + span*width - 1)
		start = start + span*width
	end
	local previous;
	for width = 1, #groups do
		for value in groups[width]:gmatch(('.'):rep(width)) do
			local entry = dictionary[tobase10(value)]
			if previous then
				if entry then
					sequence[#sequence+1] = entry
					dictionary[#dictionary+1] = previous..entry:sub(1, 1)
				else
					entry = previous..previous:sub(1, 1)
					sequence[#sequence+1] = entry
					dictionary[#dictionary+1] = entry
				end
			else
				sequence[1] = entry
			end
			previous = entry
		end
	end
	return unescape(table.concat(sequence))
end

return {
	compress = compress;
	decompress = decompress;
}