(d) The Cat in the Hat compresses Green Eggs and Ham with the LZW compression method described in 6.02 (codewords from 0 to 255 are initialized to the corre- sponding ASCII characters, which includes all the letters of the alphabet and the space character). The book begins with these lines: Iam Sam I am Sam Sam Iam We have replaced each space with an underscore (-) for clarity, and eliminated punctuation marks. i. What are the strings corresponding to codewords 256 and 257 in the string table? ii. When compressed, the sequence of codewords starts with the codeword 73, in this sequence will all be 255, and then one codeword > 255 will appear. What string which is the ASCII value of I. The initial few codewords does that codeword correspond to? iii. Cat finds that codeword 700 corresponds to the string LO-not. This string comes from the sentence Idonot ike them with a mouse in the book. What are the first two letters of the codeword numbered 701 in the string table? Thanks to a stuck keyboard (or because Cat is an ABBA fan), the phrase Idoldoldoldoldo shows up at the input to the LZW compressor. The decom- pressor gets a codeword, already in its string table, and finds that it cor- responds to the string Ido. This codeword is followed immediately by a CHAPTER 3. COMPRESSION ALGORITHMS: HUFFMAN AND LEMPEL-ZIV-WELCH (LZW) new codeword not in its string table. What string should the decompressor return for this new codeword? (d) The Cat in the Hat compresses Green Eggs and Ham with the LZW compression method described in 6.02 (codewords from 0 to 255 are initialized to the corre- sponding ASCII characters, which includes all the letters of the alphabet and the space character). The book begins with these lines: Iam Sam I am Sam Sam Iam We have replaced each space with an underscore (-) for clarity, and eliminated punctuation marks. i. What are the strings corresponding to codewords 256 and 257 in the string table? ii. When compressed, the sequence of codewords starts with the codeword 73, in this sequence will all be 255, and then one codeword > 255 will appear. What string which is the ASCII value of I. The initial few codewords does that codeword correspond to? iii. Cat finds that codeword 700 corresponds to the string LO-not. This string comes from the sentence Idonot ike them with a mouse in the book. What are the first two letters of the codeword numbered 701 in the string table? Thanks to a stuck keyboard (or because Cat is an ABBA fan), the phrase Idoldoldoldoldo shows up at the input to the LZW compressor. The decom- pressor gets a codeword, already in its string table, and finds that it cor- responds to the string Ido. This codeword is followed immediately by a CHAPTER 3. COMPRESSION ALGORITHMS: HUFFMAN AND LEMPEL-ZIV-WELCH (LZW) new codeword not in its string table. What string should the decompressor return for this new codeword
