English
Menu

Information Theory and Coding Basics

Which of the following correctly describes the idea of the LZ77 method used in ZIP, gzip and similar tools?

  1. AIt assigns short codewords to symbols with a high probability of occurring and long codewords to those with a low probability
  2. BIt discards components that are hard for human eyes or ears to notice to make the data smaller
  3. CIt replaces a string identical to one that appeared earlier with a pair of the distance back to that position and the length
Show answer and explanation

Answer: C. It replaces a string identical to one that appeared earlier with a pair of the distance back to that position and the length

The LZ77 method uses the data already processed like a dictionary, and when the same string appears again it replaces it with a pair of distance and length, "so many characters back, for so many characters". It can shrink highly repetitive data without knowing the symbol probabilities in advance, and it is lossless compression that restores the original data exactly. The Deflate method of ZIP and gzip further encodes the output of LZ77 with Huffman codes.

  • A. This is the idea of coding that uses symbol probabilities, such as Huffman coding.
  • B. This is the idea of lossy compression such as JPEG and MP3; LZ77 is lossless compression.
  • C. Correct. Repeated strings are represented by references to their earlier occurrences.
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. 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?
  2. When compressing data, which of the following must use lossless compression rather than lossy compression?
  3. 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?
  4. Four rows of 4-bit data were sent with an even parity bit for each row at its right end and a final row of even parity bits for each column (vertical and horizontal parity). The received bits were row 1: 1011 1, row 2: 0100 0, row 3: 1100 0, row 4: 0101 0 and parity row: 0100 (the rightmost bit of each row is its row parity). If exactly one bit is wrong, which of the following is its position?
  5. Data are added up one byte at a time, and the low 8 bits of the sum are sent along as a check value (checksum). Which of the following errors cannot be detected by this check?