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
?
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."