Suppose a file contains the letters a, b, c, and d. Nominally, we require 2 bits per letter to store such a file.
(a) Assume the letter a occurs 50% of the time, b occurs 30% of the time, and c and d each occur 10% of the time. Give an encoding of each letter as a bit string that provides optimal compression. Hint: Use a single bit for a.
(b) What is the percentage of compression you achieve above? (This is the average of the compression percentages achieved for each letter, weighted by the letter's frequency.)
(c) Repeat this, assuming a and b each occur 40% of the time, c occurs 15% of the time, and d occurs 5% of the time.