Chapter 3, Problem 51E

Explanation of Solution

Data Compression using Run-length encoding:

Given string: “AAAABBBCCCCCCCCDDDD hi there EEEEEEEEEFF”

• Data compression starts with flag character “*”.
• It replaces a string containing sequence of repeated character.
• Followed by a flag character, remaining characters in a string are encoded as follows,
  • The string “AAAA” is compressed as “A4” where numeric digit “4” indicates that the character “A” is repeated four times in a string.
  • The string “CCCCCCCC” is compressed as “C8” where numeric digit “8” indicates that the character “C” is repeated eight times in a string...

Explanation of Solution

Compression ratio in Run-length encoding:

• Compression ratio is defined as the length of encoded sting is divided by the length of original string.
• Formula to compute the compression ratio,

$\text{Compression ratio}=\frac{\text{Length of the encoded string}}{\text{Length of the}\text{original string}}$

• The length of original string “AAAABBBCCCCCCCCDDDD hi there EEEEEEEEEFF” is 40.
• The length of compressed string “*A4BBB*C8*D4 hi there *E9FF” is 27