62 lines
1.9 KiB
Text
62 lines
1.9 KiB
Text
// version 1.1.2
|
|
|
|
object Lzw {
|
|
/** Compress a string to a list of output symbols. */
|
|
fun compress(uncompressed: String): MutableList<Int> {
|
|
// Build the dictionary.
|
|
var dictSize = 256
|
|
val dictionary = mutableMapOf<String, Int>()
|
|
(0 until dictSize).forEach { dictionary.put(it.toChar().toString(), it)}
|
|
|
|
var w = ""
|
|
val result = mutableListOf<Int>()
|
|
for (c in uncompressed) {
|
|
val wc = w + c
|
|
if (dictionary.containsKey(wc))
|
|
w = wc
|
|
else {
|
|
result.add(dictionary[w]!!)
|
|
// Add wc to the dictionary.
|
|
dictionary.put(wc, dictSize++)
|
|
w = c.toString()
|
|
}
|
|
}
|
|
|
|
// Output the code for w
|
|
if (!w.isEmpty()) result.add(dictionary[w]!!)
|
|
return result
|
|
}
|
|
|
|
/** Decompress a list of output symbols to a string. */
|
|
fun decompress(compressed: MutableList<Int>): String {
|
|
// Build the dictionary.
|
|
var dictSize = 256
|
|
val dictionary = mutableMapOf<Int, String>()
|
|
(0 until dictSize).forEach { dictionary.put(it, it.toChar().toString())}
|
|
|
|
var w = compressed.removeAt(0).toChar().toString()
|
|
val result = StringBuilder(w)
|
|
for (k in compressed) {
|
|
var entry: String
|
|
if (dictionary.containsKey(k))
|
|
entry = dictionary[k]!!
|
|
else if (k == dictSize)
|
|
entry = w + w[0]
|
|
else
|
|
throw IllegalArgumentException("Bad compressed k: $k")
|
|
result.append(entry)
|
|
|
|
// Add w + entry[0] to the dictionary.
|
|
dictionary.put(dictSize++, w + entry[0])
|
|
w = entry
|
|
}
|
|
return result.toString()
|
|
}
|
|
}
|
|
|
|
fun main(args: Array<String>) {
|
|
val compressed = Lzw.compress("TOBEORNOTTOBEORTOBEORNOT")
|
|
println(compressed)
|
|
val decompressed = Lzw.decompress(compressed)
|
|
println(decompressed)
|
|
}
|