Question

Problem 9 Suppose the alphabet is E= {a,b,c}. Give a string of length 10 composed for which LZW compression is the worst possible. State the entries added to the dictionary.

Answer 1

Hi!

Below are mentioned the 6 worst case scenerios since we will be having cases as $\sum = \begin{Bmatrix} a, & b, & c \end{Bmatrix}$ :

 >>> print(compress('ABCAAAACBA')) {'AB': 256, 'BC': 257, 'CA': 258, 'AA': 259, 'AAA': 260, 'AC': 261, 'CB': 262, 'BA': 263} [65, 66, 67, 65, 259, 65, 67, 66, 65] >>> print(compress('BCABBBBACB')) {'BC': 256, 'CA': 257, 'AB': 258, 'BB': 259, 'BBB': 260, 'BA': 261, 'AC': 262, 'CB': 263} [66, 67, 65, 66, 259, 66, 65, 67, 66] >>> print(compress('CABCCCCBAC')) {'CA': 256, 'AB': 257, 'BC': 258, 'CC': 259, 'CCC': 260, 'CB': 261, 'BA': 262, 'AC': 263} [67, 65, 66, 67, 259, 67, 66, 65, 67] >>> print(compress('ACBAAAABCA')) {'AC': 256, 'CB': 257, 'BA': 258, 'AA': 259, 'AAA': 260, 'AB': 261, 'BC': 262, 'CA': 263} [65, 67, 66, 65, 259, 65, 66, 67, 65] >>> print(compress('BACBBBBCAB')) {'BA': 256, 'AC': 257, 'CB': 258, 'BB': 259, 'BBB': 260, 'BC': 261, 'CA': 262, 'AB': 263} [66, 65, 67, 66, 259, 66, 67, 65, 66] >>> print(compress('CBACCCCABC')) {'CB': 256, 'BA': 257, 'AC': 258, 'CC': 259, 'CCC': 260, 'CA': 261, 'AB': 262, 'BC': 263} [67, 66, 65, 67, 259, 67, 65, 66, 67] >>> 

The entries to the dictionary are gievn as key value pairs in the above snippet area. For the above cases we find that the output string contains the maximum entries and the dictionary contains the maximum entries as well.

Please feel to ask for the code whenever you like. I have not included the code as it was not asked for in the question. Plese do not forget to give a thumbs up for my work and presentation. Thanks and regards.