Due 5/18/99

It is interesting to compare LZW and Sequitur on some simple examples to compare their performance.  For LZW assume that a string of length n can be compressed to k log₂ m bits where m is the size of the dictionary produced by the encoder and k is the number encoded symbols in the compressed string.  For Sequitur assume that a string of length n can be compressed to (s + r -1) log₂ (a + r +1) bits where s is the sum of the lengths of the right hand sides of productions, r is the number of productions, and a is the size of the orignial alphabet.  In this application log₂ k is the integer ceiling of the logarithm base 2 of k.  Use LZW and Sequitur to compress the string 0³²  (32 0's).  Assume an original alphabet of {0,1}.  Show the resulting dictionary for LZW and the resulting grammar for Sequitur.   Give the compression achieved for both algorithms.

Use both LZW and Sequitur to compress the string 0ⁿ  (n 0's) in the alphabet {0,1}.  Describe the resulting dictionary for LZW and the resulting grammar for Sequitur.  What is the compression ratio for LZW and for Sequitur as functions of n?  If it helps to assume that n is a power of two go ahead and do so.

With information from this study, can you describe an advantage of LZW over Sequitur and an avantage of Sequitur over LZW?