Compression: lossless vs lossy

Why this matters

A photo from a phone can be several megabytes. Sent as an email attachment, stored in a backup, or streamed to a laptop, every byte costs something: storage space, waiting time, or money for data. Compression makes a file use fewer bytes. The storage and files lesson showed run-length encoding, which replaces a run of the same character with a count. That method is simple, but most real files do not contain long runs. This lesson covers two other ideas. The first is dictionary-style compression, which finds repeated pieces of text. The second is lossy compression, which saves much more space by giving up detail on purpose.

Compression methods come in two families. A lossless method rebuilds the original exactly, byte for byte. A lossy method rebuilds something close to the original, and the difference cannot be undone. Choosing between the two is the main decision in any compression task, so the rest of the lesson is built around it.

Lossless: every byte comes back

A lossless method has one test: compress a file, decompress it, and compare the result with the original. If the two are equal, nothing was lost. Python has a standard library called zlib that compresses data with a method named DEFLATE. ZIP files usually use DEFLATE too, so zlib is a small, direct model of what zip does. The code below compresses a sentence repeated 200 times and checks that the round trip gives the same bytes.

original bytes: 9000
packed bytes: 96
restored equals original: True

The 9,000 bytes became 96. The 9 in the call asks for the strongest compression level, which takes a little more time. The last line is the test that matters. A lossless method must print True.

Dictionary-style compression: write a repeat once

The idea behind dictionary compression is simple. Keep a list of the pieces you have already seen. When a piece comes back, write a short code that points to the list instead of the piece itself.

Take a short text with 11 words:

the cat and the dog and the cat and the bird

Read it from left to right and build a table as you go. The first time you see a word, give it the next free number. Every later appearance of that word becomes its number.

The text becomes the list of numbers 0, 1, 2, 0, 3, 2, 0, 1, 2, 0, 4. The program below does the same job, then rebuilds the text from the codes.

dictionary: {'the': 0, 'cat': 1, 'and': 2, 'dog': 3, 'bird': 4}
codes: [0, 1, 2, 0, 3, 2, 0, 1, 2, 0, 4]
decoded same as original: True
original bytes: 44
codes at one byte each: 11
dictionary bytes (word plus a separator): 21

Add the parts. The codes take 11 bytes and the dictionary takes 21 bytes, which is 32 bytes in total, against 44 for the original. The dictionary has to be stored with the codes, or nobody can read them. For short text the table costs more than it saves. A 40-character sentence with no repeats gets bigger, not smaller, after this treatment. This is the first rule of compression: the saving has to beat the cost of the table.

The example above uses whole words. Real compressors work on pieces of any length, including part of a word, a space and a punctuation mark together. The principle does not change.

Copying from earlier text

A second idea is more common in real compressors. Instead of a table, the compressor points back into the text it has already written. A token says "copy 9 characters, starting 3 characters back". The family of methods that does this is called LZ77, after the authors who described it in 1977. DEFLATE uses a version of it.

Here is the idea on a short string, abcabcabcabcX, which has 13 characters.

1. Position 0 is a. Nothing comes before it, so write it as a literal.
2. Position 1 is b. Nothing matches yet, so write it as a literal.
3. Position 2 is c. Again no match, so write it as a literal.
4. Position 3 starts abcabcabc. Look back. The text 3 characters back also starts with abc, and the match runs for 9 characters. Write one token: copy 9 characters from 3 back.
5. The last character is X. Write it as a literal.

Five tokens describe thirteen characters. The fourth token needs a closer look. Its source overlaps what it is writing, because the copy starts 3 back and runs 9 long. The decoder (the part that rebuilds the text) handles that by appending one character at a time, so each new character is available to the copy that follows it.

The program below is a small teaching version. It finds the longest match among the previous 255 characters. It writes a copy only when the match is at least 3 characters long, because a shorter copy would cost more than the characters it replaces.

('lit', 'a')
('lit', 'b')
('lit', 'c')
('copy', 3, 9)
('lit', 'X')
round trip ok: True
47 characters -> 20 tokens
copies: [('copy', 4, 3), ('copy', 15, 4), ('copy', 9, 5), ('copy', 24, 19)]
round trip ok: True

The first five lines match the trace. The second text is the cat sat on the mat. the cat sat on the mat., which has 47 characters. The 19-character copy at the end is cat sat on the mat., written as one token that points 24 characters back. Plain text is full of such repeats: common words, phrases, code keywords, the same header in every line of a log. A copy token costs a few bytes whatever its length, so long repeats give the biggest savings.

A real compressor adds one more step. It gives short bit codes to the tokens that appear most often, and longer codes to the rare ones. That step is called Huffman coding. It is one reason real files are smaller than this teaching version would make them. The method is still lossless, so the decoder gets every character back.

Why repetitive text shrinks and random data does not

Compression removes patterns. Text is full of them, because letters follow rules, words repeat and sentences have shapes. Random data has none. The next program shows the effect. It uses a seeded random generator, so the numbers are the same each time you run it.

repeated text: 9000 -> 96 bytes, restored ok: True
random bytes: 9000 -> 9011 bytes, restored ok: True
short word: 5 -> 13 bytes, restored ok: True

Three cases, three results. The repeated text shrinks by about 99 percent. The random bytes grow by 11 bytes, because the compressor still writes a small header and a checksum (a number that detects damaged data), but it finds nothing to remove. The five-letter word grows from 5 bytes to 13, because the header costs more than the word saves. This is the second rule of compression: the file has to contain patterns, and it has to be long enough for the patterns to pay for the header.

Photos, music and video files are already compressed when you get them. Their data looks random to a general-purpose compressor, so zipping them gives almost no gain. The mistake is common enough to have its own section below.

Lossy: some detail is gone for good

A lossy method does not try to rebuild the original exactly. It keeps the parts a person will probably notice and drops the rest. The saving is much larger, but the lost detail is gone, and no program can bring it back.

Start with a very small example. A row of eight pixels (the dots that make up a picture) has brightness values from 0 (black) to 255 (white). Suppose the picture does not need that precision. Round each value to the nearest 10.

original: [52, 55, 61, 66, 70, 61, 64, 73]
rounded to 10: [50, 60, 60, 70, 70, 60, 60, 70]
change per pixel: [-2, 5, -1, 4, 0, -1, -4, -3]
stored as small codes: [5, 6, 6, 7, 7, 6, 6, 7]

Each pixel changed by at most 5. A change of 5 on a 256-level scale is hard to see in a picture. The stored codes are single digits, and there are only three different values, so the row now compresses well. The codes are the way the saving is made. Rounding is the loss.

The next example applies the same rounding to a whole image. The image is a synthetic 200 by 200 grey gradient with a little noise, so it has 40,000 pixels and 40,000 bytes. The program uses one byte per pixel. It rounds each value to the nearest multiple of a step size, compresses the result, and compares it with the original.

pixels: 40000 bytes uncompressed
lossless zlib size: 26532
step 1: zlib size 26532, biggest change 0, average change 0.00, same as original: True
step 4: zlib size 11214, biggest change 2, average change 1.00, same as original: False
step 16: zlib size 3297, biggest change 8, average change 4.01, same as original: False

The step size is the dial. A step of 1 changes nothing, and the file stays at 26,532 bytes. A step of 4 cuts the size by more than half, and no pixel changes by more than 2. A step of 16 leaves 3,297 bytes, which is 8 percent of the original size, and the largest change is 8. The biggest change is at most half the step size, because the rounding goes to the nearest multiple.

Real lossy formats are cleverer than this, but the trade is the same. JPEG cuts the picture into blocks of 8 by 8 pixels. For each block it works out how much of the change comes from fine detail, such as the edge of a leaf, and how much comes from broad shapes, such as a sky going from light to dark. People notice changes in brightness more than changes in fine colour, and they notice fine detail less than broad shapes. JPEG therefore rounds the fine detail more coarsely, often down to zero, and stores colour at a lower resolution than brightness. A quality setting in a JPEG encoder (the program that writes the file) controls how coarse that rounding is. Lower quality means smaller files and more visible damage.

MP3 audio does something similar with sound. It removes parts of the sound that people hardly hear, such as a quiet tone that is covered by a loud one next to it. The file is much smaller, and the removed parts are gone.

Saving again makes it worse

A lossy file is a copy that has already lost detail. Open a JPEG, change nothing, and save it again. The encoder rounds the picture again, and the new losses are added to the old ones. After many saves the picture looks blotchy and has halos around edges. This is called generation loss. The fix is to keep the original, which is usually a lossless file, and to export a lossy copy from it only once.

Choosing between lossless and lossy

Ask one question first: will anyone need the exact original? If the answer is yes, use a lossless method. If the answer is no, a lossy method may save far more space.

The last row matters most. A lossy copy is fine for sharing. It should not be the only copy.

Common mistakes

Zipping a file that is already compressed

Photos, music and video are already compressed. Putting them in a zip file usually gives almost no gain, and it wastes time. The program from the random data section shows the cause: a file with no patterns grows slightly when a compressor tries to shrink it. If you need a smaller file of a JPEG, make a lower-quality JPEG. Zipping it will not help.

Expecting a tiny file to shrink

A file of a few bytes is usually made bigger by compression, because the header costs more than it saves. The example above showed hello growing from 5 bytes to 13. Compression pays off on larger files with repeated content.

Decompressing a file that was never compressed

Calling a decompressor on plain text gives an error, not a result. The message is short and it names the cause, but the cause is easy to miss when the file looks like it should be compressed.

zlib.error: Error -3 while decompressing data: incorrect header check

The "incorrect header check" message means the first bytes of the file are not the header that a zlib stream starts with. Check the file's name and how it was made. If you are not sure, look at the first few bytes before you call a decompressor. A zlib stream starts with a two-byte header that passes a fixed check, so a mismatch is a sign that the data came from somewhere else.

Treating lossy output as the original

A lossy copy does not match the original, and comparing the two with == returns False. This is not a bug in the program. The loss is the point. If your code needs an exact match, store the file losslessly. The step-4 and step-16 rows in the image example show that the same image can give a different answer at each setting.

Practice

Exercise 1

Compress xyxyxyxy by hand, using the rules from the copying section. Write each token. Which character is the copy?

Show the answer

Three tokens: ('lit', 'x'), ('lit', 'y'), ('copy', 2, 6). The copy starts 2 characters back and writes 6 characters. The second x and y both come from the copy, so the copy overlaps what it is writing.

Exercise 2

Round the row 12, 18, 25, 31 to the nearest 5. What is the change for each pixel?

Show the answer

The rounded row is 10, 20, 25, 30. The changes are -2, 2, 0, -1. No change is larger than 2, which is half the step of 5.

Exercise 3

The text red red blue red red blue has 25 characters. The dictionary method gives red the number 0 and blue the number 1. How many codes are there, and how many bytes do the codes take if each code is one byte?

Show the answer

There are 6 codes, because the text has 6 words. The codes 0, 0, 1, 0, 0, 1 take 6 bytes. The dictionary is still needed, so the total is larger than 6 bytes.

Exercise 4

Compress the three-byte text abc with zlib.compress(b"abc", 9) and count the bytes. Is the result smaller than the input?

Show the answer

The result is 11 bytes, which is larger than the 3-byte input. The header and checksum cost more than the text saves, so compression does not help short data.

Exercise 5

Which method would you use for each of these: a school report saved as a text file, a family photo to send to relatives, and a backup of your own source code?

Show the answer

Lossless for the report and the source code, because one changed character matters. Lossy (JPEG) for the photo, because relatives need a viewable picture, not every original pixel. Keep the original photo as well, because the lossy copy cannot be turned back into it.

Summary

• A lossless method rebuilds the original exactly. The test is to compress, decompress and compare with ==.
• Dictionary-style compression replaces repeats with short codes, and it pays for its table only when the text has enough repeats.
• Copy tokens point back into text already written. A copy can overlap its own output, and the decoder handles it one character at a time.
• Random or already-compressed data does not shrink, and very short files can grow.
• A lossy method removes detail people are unlikely to notice, such as fine detail in a photo or quiet sound under a loud one. The removed detail cannot be recovered.
• Keep a lossless original, and make lossy copies only from it, because each lossy save adds more loss.