LZW decoding process

Question

I'm trying to understand how LZW decodes a string.

For example suppose that we have a dictionary where:

• a=0
• b=1

and we have to encode the string "aabbabaabb", so the output of the encoding process (if I have not made mistakes) produces the string "0011324" and the dictionary became(using a tree representation):

_{(source: f.cl.ly)}

The decoder will just know "0011324" and the starting dictionary where there are just a=0 and b=1.

How does it work the decoding process with just these 2 informations?

Answer 1

Short answer: the decoding algorithm follows the same steps as the coder: it actually builds the tree. E.g., in your example the first two 0's mean two a's have been read, This then implies the code for aa was added to the tree as number 2. This continues, but necessarily the decoder always is one step behind the coder. In most cases all information is present to make decisions in the next move. Unfortunately there is the possibility that the decoder needs the code that has been just inserted in the tree (and is not available for the decoder since it lags behind). That case is so specific that it can be reconstructed from the other information (then the unknown letter must be the first letter of the last code).

That is the global view. Wikipedia has a larger example.