English
Menu

Information Theory and Coding Basics

The 40-character string AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD (12 As, 4 Bs, 20 Cs and 4 Ds) is compressed with run-length encoding, which represents each run of the same character as a pair of "character (1 byte) and count (1 byte)". The original string uses 1 byte per character. Defining the compression ratio as "size after compression ÷ size before compression", which of the following is the compression ratio?

  1. A10%
  2. B20%
  3. C80%
Show answer and explanation

Answer: B. 20%

There are four runs of the same character, A, B, C and D, so the compressed data are 4 × 2 = 8 bytes. The original is 40 bytes, so the compression ratio is 8 ÷ 40 = 0.2, that is, 20%. Run-length encoding shrinks data better the longer the same value continues.

  • A. 10% is 4 ÷ 40, which leaves out the bytes that hold the count of each run.
  • B. Correct. 8 ÷ 40 = 20%.
  • C. 80% is the fraction removed by compression (1 − 0.2), not the compression ratio as defined in this question.
Practice this topic Back to topic

Books on Information Theory and Coding Basics Ad

As an Amazon Associate I earn from qualifying purchases.

More Information Theory and Coding Basics questions

  1. Which of the following data is most likely to be made smallest by run-length encoding?
  2. Which of the following correctly describes the idea of the LZ77 method used in ZIP, gzip and similar tools?
  3. Data compressed with the LZ77 method are to be restored. The data consist of "character A", "character B" and "(distance 2, length 5)", in that order. (distance d, length L) means repeating L times, one character at a time, "copy the character d characters back from the end of the restored string to its end". Which of the following is the restored string?
  4. When compressing data, which of the following must use lossless compression rather than lossy compression?
  5. A single even parity bit is added to a bit string of data so that the number of 1s is even, and the receiver checks the number of 1s. Which of the following correctly describes this check?