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?


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.

  • $\begingroup$ Note that the wikipedia encoding example is messed up, but the decoding example looks right. $\endgroup$ – Wandering Logic Nov 22 '13 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.