LZW compression algorithm

Code table with variable sized strings -> fixed size code words
  

string  code
a       12 
ab      23 
aab     34 
d       11 
dd      54 
dde     21 
General principle -
The code table is initialized with all single characters
The source is scanned and code words are searched in the code table
When the longest code word is found (= w) read also the next character (=K) and add in the code table the new code word( wK)

The code table is reconstructer again during decompression - no need to store the table

Complete algorithm (Welch: A Technique for High-Performance Data Compression: Computer, June 1984, pp. 8-19)


Initialize the code table to contain single-character strings
Read first input character -> w
Step: Read next input character -> K
    if no such K (input exhausted): code(w) -> output: EXIT
    If wK exists in string table: wK -> w: repeat Step
    else wK is not in string table :{ code(w) -> output
        wK -> string table
        K-> w; repeat Step;}