Search code examples
algorithmstring-matchingcompressionlzw

Understanding an example of LZW decompression algorithm


I'm trying to understand this example of decompression using the LZW algorithm.

I would like to undestand why we insert ba in row 4; we're currently at i=3, so the index s=ab as shown in row 3; we previously had a and b so aren't we supposed to look for abab in the dictionary? So why is the result ba and not abba?

[1]: http://hpics.li/6ae07fa "LZW decompression"


Solution

  • From the English version of Wikipedia: "Buffer input characters in a sequence ω until ω + next character is not in the dictionary. Emit the code for ω, and add ω + next character to the dictionary. Start buffering again with the next character."