Hello i am studying about LZW algorithm by watching this video: https://www.youtube.com/watch?v=j2HSd3HCpDs&t=481s

I couldnt fully understand decoding process. At current 258,how does 116 come at add to dictionary part ? At current 256,how does 101 come at add to dictionary part ?

enter image description here

  • $\begingroup$ The add to dictionary lines don't seem to line up with the input/output they would be added by. $\endgroup$ – ratchet freak Nov 12 '18 at 16:49
  • $\begingroup$ If you understand encoding, you should be able to figure out decoding. So perhaps it's best to first thoroughly understand encoding, and then to work out on your own how decoding would work. $\endgroup$ – Yuval Filmus Nov 12 '18 at 18:51

Let us look at the very first line. There is a 104 at the end of the line. Where does that 104 come from? It is the first number of the number(s) that are represented by 104 in the next column. Since 104 is in the 0-255 range, 104 just represents itself.

The same procedure happens on the line at the end of which you see a 106. Where does that 106 come from? That 106 is the first number of the number(s) that are represented by 256 in the next column. How? Since 256 is outside of 0-255 range, we have to consult the dictionary we have built. As given by the last column of the first line, 256 represents for two numbers, 116 104, of which 106 is the first one.

I will let you figure out why the above procedure is correct, where 101 on the last line come from and why the numbers in the output column are correct.

By the way, it should be helpful if you can also take a look at the encoding procedure at the nearby lines when you try to understand the decoding procedure.


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.