Suppose that the Lempel, Ziv and Welch (LZW) compression algorithm is applied to text of the form:

aaa...ab

which contains 50 characters in total (so 49 a’s followed by a single b).

Assuming that:

• each character in the source file occupies 8 bits;
• the initial codeword length 7;
• the dictionary initially contain the strings a and b;

determine the resulting compression ratio and saved space (as a percentage of the original file size). Explain your reasoning and leave your answer as a fraction as no calculators are permitted.

Note. Marks will be lost if your computation involves building the compressed file to find its size or includes any unnecessary work.

Note. In the provided table there are more rows than you should need.

[10]