45 lines
1.2 KiB
Text
45 lines
1.2 KiB
Text
type LzwCompression
|
|
fun compress ← List by text uncompressed
|
|
List output ← int[]
|
|
text working ← Text.EMPTY
|
|
Map symbolTable ← text%int[].with(256, <int i|text%int(chr(i) => i))
|
|
for each text c in uncompressed
|
|
text augmented ← working + c
|
|
if symbolTable.has(augmented)
|
|
working ← augmented
|
|
else
|
|
symbolTable.insert(augmented, symbolTable.length)
|
|
int i ← symbolTable[working]
|
|
output.append(i)
|
|
working ← c
|
|
end
|
|
end
|
|
if not working.isEmpty()
|
|
int i ← symbolTable[working]
|
|
output.append(i)
|
|
end
|
|
return output
|
|
end
|
|
fun decompress ← text by List compressed
|
|
Map symbolTable ← int%text[].with(256, <int i|int%text(i => chr(i)))
|
|
text working ← symbolTable[compressed[0]]
|
|
text output ← *working
|
|
for each int i in compressed.extract(1)
|
|
text s
|
|
if symbolTable.has(i)
|
|
s ← symbolTable[i]
|
|
else if i æ symbolTable.length # cScSc problem
|
|
s ← working + working[0]
|
|
else
|
|
error(65, "Error decompressing")
|
|
end
|
|
output.append(s)
|
|
symbolTable.insert(symbolTable.length, working + s[0])
|
|
working ← s
|
|
end
|
|
return output
|
|
end
|
|
List compressed = compress("TOBEORNOTTOBEORTOBEORNOT")
|
|
writeLine(compressed)
|
|
text decompressed = decompress(compressed)
|
|
writeLine(decompressed)
|