Homework 3

Due 29 September, 2016

Give reasons for all answers.

  1. Show how LZ77 encodes the string TENTENNESSEETENTS if the search buffer has length 8 and the lookahead buffer has length 4. Show that your encoding decodes correctly.
  2. Encode and decode the same string with LZ78.
  3. Encode and decode the same string with LZW with initial dictionary entries E, N, S, T numbered 1, 2, 3, 4 respectively.
  4. In class we saw that LZ77 can encode a long repeating pattern as a single codeword, up to the length permitted by the search and lookahead buffers. What happens with LZ78 if it encounters a long repetition of the same character?