English
Menu

What is Lossless compression?

A compression method from whose output the original data can be restored without a single bit of difference. Methods include Huffman coding and arithmetic coding, which exploit skewed symbol probabilities, LZ methods such as LZ77, which exploit repetition, and run-length encoding, and they are used in ZIP, gzip, PNG, FLAC and elsewhere. It is used for data in which not even one bit may differ, such as programs, documents and spreadsheet data. How much data shrink depends on their redundancy, and no lossless compression can make every input smaller.

Japanese name: 可逆圧縮

Lossless compression appears in 5 practice questions across 2 topics, including Information Theory and Coding Basics, Web Technology Basics.

Field: Information Theory and Coding Basics

Try it: questions about Lossless compression

Which of the following correctly describes the relationship between lossless compression and the entropy of a source?

  1. AWith a good enough lossless compression algorithm, any file, whatever its contents, can always be made smaller than the original
  2. BEven for a source that emits symbols independently, a cleverly designed lossless code can make the average code length smaller than the entropy
  3. CThe average code length of a lossless code cannot be made smaller than the entropy, but coding symbols together brings it closer
Show answer and explanation

Answer: C. The average code length of a lossless code cannot be made smaller than the entropy, but coding symbols together brings it closer

For a source that emits symbols independently, the average code length per symbol of a lossless code is at least the entropy, and coding symbols together brings it arbitrarily close to the entropy (the source coding theorem). Moreover, there are 2ⁿ files of n bits, but only 2ⁿ − 1 bit strings shorter than that in total, so no lossless compression can shorten every file. Lossless compression shortens data with skew or repetition at the cost of making other data slightly longer.

When compressing data, which of the following must use lossless compression rather than lossy compression?

  1. ACompressing a program's executable file for distribution
  2. BShrinking video to match the speed of the connection in a video streaming service
  3. CMaking music files smaller to listen to on a portable player
Show answer and explanation

Answer: A. Compressing a program's executable file for distribution

Lossless compression restores the original data without a single bit of difference, while lossy compression discards parts that people hardly notice in return for much greater shrinkage. A program does not run correctly if even one bit differs, so lossless compression such as ZIP is used. Small differences in images and sound are hard to see or hear, so lossy compression such as JPEG, MP3 and video coding formats is widely used for them.

Lossless compression in the explanations

Questions that mention Lossless compression (5)

  1. Which of the following correctly describes the relationship between lossless compression and the entropy of a source?
  2. When compressing data, which of the following must use lossless compression rather than lossy compression?
  3. A source that emits 8 kinds of symbols has an entropy of 2.4 bits. Defining redundancy as 1 − (entropy ÷ maximum entropy), which of the following is the redundancy of this source?
  4. Which of the following correctly describes the idea of the LZ77 method used in ZIP, gzip and similar tools?
  5. Which of the following is an appropriate pairing of an image format for web pages with its typical use?

Books on Information Theory and Coding Basics Ad

As an Amazon Associate I earn from qualifying purchases.

Related terms

Information entropy Lossy compression Average code length Self-information Huffman coding Binary symmetric channel Forward error correction (FEC) Hamming code Hamming distance Kraft inequality

Back to the glossary