68 lines
2.2 KiB
Java
68 lines
2.2 KiB
Java
import java.util.*;
|
|
|
|
public class LZW {
|
|
/** Compress a string to a list of output symbols. */
|
|
public static List<Integer> compress(String uncompressed) {
|
|
// Build the dictionary.
|
|
int dictSize = 256;
|
|
Map<String,Integer> dictionary = new HashMap<String,Integer>();
|
|
for (int i = 0; i < 256; i++)
|
|
dictionary.put("" + (char)i, i);
|
|
|
|
String w = "";
|
|
List<Integer> result = new ArrayList<Integer>();
|
|
for (char c : uncompressed.toCharArray()) {
|
|
String wc = w + c;
|
|
if (dictionary.containsKey(wc))
|
|
w = wc;
|
|
else {
|
|
result.add(dictionary.get(w));
|
|
// Add wc to the dictionary.
|
|
dictionary.put(wc, dictSize++);
|
|
w = "" + c;
|
|
}
|
|
}
|
|
|
|
// Output the code for w.
|
|
if (!w.equals(""))
|
|
result.add(dictionary.get(w));
|
|
return result;
|
|
}
|
|
|
|
/** Decompress a list of output ks to a string. */
|
|
public static String decompress(List<Integer> compressed) {
|
|
// Build the dictionary.
|
|
int dictSize = 256;
|
|
Map<Integer,String> dictionary = new HashMap<Integer,String>();
|
|
for (int i = 0; i < 256; i++)
|
|
dictionary.put(i, "" + (char)i);
|
|
|
|
String w = "" + (char)(int)compressed.remove(0);
|
|
StringBuffer result = new StringBuffer(w);
|
|
for (int k : compressed) {
|
|
String entry;
|
|
if (dictionary.containsKey(k))
|
|
entry = dictionary.get(k);
|
|
else if (k == dictSize)
|
|
entry = w + w.charAt(0);
|
|
else
|
|
throw new IllegalArgumentException("Bad compressed k: " + k);
|
|
|
|
result.append(entry);
|
|
|
|
// Add w+entry[0] to the dictionary.
|
|
dictionary.put(dictSize++, w + entry.charAt(0));
|
|
|
|
w = entry;
|
|
}
|
|
return result.toString();
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
List<Integer> compressed = compress("TOBEORNOTTOBEORTOBEORNOT");
|
|
System.out.println(compressed);
|
|
String decompressed = decompress(compressed);
|
|
System.out.println(decompressed);
|
|
}
|
|
}
|