COMP9319 Exercises

Solution : To be posted in 2 weeks

Question 1

Given the text string below:

jejunojejunostomy

  1. What is its entropy?

  2. Draw a Huffman tree based on the letters and their corresponding distributions for the above text string (Do not need to draw trees for the intermediate steps).

  3. Provide the resulting Huffman code for each letter.

  4. What is the average number of bits needed for each letter, using your Huffman code? How does it compare to the entropy ? (i.e., equal/larger/small and why)

Question 2

Adaptive Huffman Coding is used to encode a string with a vocabulary of three letters a, b, c.

The initial coding before any transmission is: a=01100001, b=01100010, c=01100011.

Derive the encoded bitstream received from the decoder for the string abcbaaa. Draw the adaptive Huffman trees after each of the additional letters is received.

Question 3

The length of a given string is 8, containing letters a, f, i, r with their probability ranges as below:

a [0.0, 0.125), f [0.125, 0.625), i [0.625, 0.75), r [0.75, 1.0)

  1. Decode the arithmetic code 0.91805 to its corresponding string.

  2. Given the string:

    jejunojeju

    Derive an arithmetic code. (Your answer should be in decimal number with minimum precision).

Question 4

Consider the dictionary-based LZW compression algorithm. Suppose the alphabet is the set of ASCII characters, and the first 256 (i.e., <0> to <255>) table entries are initialized to these characters.

Show the dictionary (symbol sets plus associated codes) and output for LZW compression of the input string:

jejunojejuno