Compression

Open your phone's gallery and compare two images: a screenshot of a WhatsApp chat with a plain white background, and a photo you just took of your classroom. Even though both pictures might use the exact same number of pixels — say, 1080 by 2340 — the screenshot file is usually a fraction of the size of the photo in kilobytes. Nothing about the content explains this on its own; a pixel is a pixel. The difference is that the screenshot is mostly the same color repeated over and over — thousands of pixels in a row are pure white — while the photo's pixels are all slightly different from their neighbours, because real light doesn't arrive in flat blocks of colour. Compression is the general name for techniques that exploit exactly this kind of pattern: instead of storing "white, white, white, white..." nine hundred times, you store something closer to "white, nine hundred times." This chapter builds up, from first principles, how that idea turns into real, working algorithms — the same ideas that shrink the timetable PDF your teacher forwards on WhatsApp, the images ISRO downlinks from a satellite, and the video Hotstar streams to your phone during an IPL match.

Two Very Different Promises: Lossless vs Lossy

Before writing any algorithm, it is worth being precise about what "compression" is promising, because there are two fundamentally different kinds, and mixing them up is one of the most common misunderstandings about the topic.

Lossless compression guarantees that decompressing the compressed file gives you back the exact original, bit for bit, with nothing changed. If you compress a ZIP of your project files and later unzip it, every character of every file must be identical to what you started with — a single wrong bit in a piece of code could make it fail to run. Text files, program source code, spreadsheets of marks, and PDF documents all need lossless compression, because losing even a little information is unacceptable.

Lossy compression deliberately throws away information that human eyes or ears are unlikely to notice, in exchange for much smaller files. A JPEG photo or an MP3 song is not a perfect copy of the original — it is a close approximation, tuned to how human vision and hearing actually work. This is why a heavily compressed JPEG looks slightly blurry or blocky if you zoom in, while a compressed lossless text file, however small, always expands back to the exact original text, with no blur possible.

This chapter focuses on the mathematics of lossless compression, specifically two techniques you can trace by hand and implement yourself: run-length encoding and Huffman coding. These are also the conceptual building blocks that real-world lossy formats like JPEG and MP3 use internally, applied after their own lossy step has already thrown away whatever won't be reconstructed.

Run-Length Encoding: Compressing by Counting Repeats

Picture a single horizontal row of pixels scanned from a ruled answer sheet, where each pixel is either white (background) or black (a printed rule line). Suppose one particular row looks like this: forty white pixels, then ten black pixels forming part of a printed rule, then sixty white pixels, then ten more black pixels along the sheet's border. Written out pixel by pixel, that row is 120 characters long: forty W's, then ten B's, then sixty W's, then ten B's.

Writing "WWWWWWWW...W" forty times in a row is wasteful — you are storing the same fact ("white") forty separate times when one statement of the fact plus a count would do just as well. Run-length encoding (RLE) formalizes this idea: instead of storing every repeated character individually, you scan through the data and replace every run (a maximal stretch of one repeated character) with the character itself followed by how many times it repeats.

Applying that to our pixel row: the run of forty W's becomes W40, the run of ten B's becomes B10, the run of sixty W's becomes W60, and the final run of ten B's becomes B10 again. Concatenating these four pieces gives the encoded string W40B10W60B10 — just twelve characters, compared to the original 120 characters.

The diagram below shows this same row visually. The top strip is the actual sequence of 120 pixels, drawn proportionally so you can see the four runs; the bottom strip is the compact encoded form describing exactly the same information using four (colour, count) pairs instead of 120 individual pixels.

Once you have the encoded form, computing how much space you saved is simple arithmetic. Define the compression ratio as:

compression ratio = original size / compressed size

Here, that is 120 ÷ 12 = 10, often written as a "10:1" compression ratio — the original data was ten times larger than the compressed version. It is often more intuitive to talk about the percentage saved, computed as (1 − compressed/original) × 100. Substituting our numbers: (1 − 12/120) × 100 = (1 − 0.1) × 100 = 90%. Run-length encoding shrank this particular row by 90%, because it was extremely repetitive — long, uninterrupted runs of the same value are exactly the situation RLE is built for.

Writing Run-Length Encoding as Code

The pixel-row example used two-digit counts, but a general-purpose implementation should not assume anything about how many digits a count needs — a run could be 3 characters long or 3,000. Here is a general rle_encode function that scans through any string of letters, tracks the current run, and writes it out (character, then count) whenever the run breaks:

def rle_encode(text):
    if not text:
        return ""
    result = []
    prev_char = text[0]
    count = 1
    for ch in text[1:]:
        if ch == prev_char:
            count += 1
        else:
            result.append(prev_char + str(count))
            prev_char = ch
            count = 1
    result.append(prev_char + str(count))
    return "".join(result)

Trace this by hand on text = "AAAABBBCCDDDDD" (four A's, three B's, two C's, and five D's — fourteen characters total) to see exactly how it builds its answer. The function starts with prev_char = "A" and count = 1, then walks through the remaining thirteen characters one at a time:

• Positions 1–3 are all "A": each matches prev_char, so count climbs to 4.
• Position 4 is "B": it does not match "A", so the function records "A" + "4" = "A4", then resets prev_char = "B", count = 1.
• Positions 5–6 are "B": count climbs to 3.
• Position 7 is "C": records "B3", resets to prev_char = "C", count = 1.
• Position 8 is "C": count becomes 2.
• Position 9 is "D": records "C2", resets to prev_char = "D", count = 1.
• Positions 10–13 are "D": count climbs to 5.
• The loop ends, and the function records the final run: "D5".

Joining every recorded piece gives "A4" + "B3" + "C2" + "D5" = "A4B3C2D5" — eight characters, down from fourteen. That is a compression ratio of 14/8 = 1.75, and a saving of (1 − 8/14) × 100 ≈ 42.9%.

Decoding has to reverse this precisely. rle_decode reads one letter, then greedily reads every digit that follows it as part of the count, then repeats that letter that many times:

def rle_decode(code):
    result = []
    i = 0
    while i < len(code):
        char = code[i]
        j = i + 1
        num_str = ""
        while j < len(code) and code[j].isdigit():
            num_str += code[j]
            j += 1
        result.append(char * int(num_str))
        i = j
    return "".join(result)

Tracing rle_decode("A4B3C2D5"): at i = 0, char = "A", and the inner loop reads the single digit "4" before hitting the non-digit "B", so it appends "A" * 4 = "AAAA" and jumps to i = 2. The same pattern repeats for "B3" (appends "BBB"), "C2" (appends "CC"), and "D5" (appends "DDDDD"). Joining every piece gives "AAAA" + "BBB" + "CC" + "DDDDD" = "AAAABBBCCDDDDD" — exactly the original string, confirming the round trip is lossless.

When Run-Length Encoding Makes Things Worse

Here is the misconception this section corrects directly: compression does not always make data smaller. A compression algorithm only helps when its assumptions about the data's structure actually hold. RLE assumes there will be long runs of repeated characters; when that assumption fails, RLE can make a file bigger than the original, not smaller.

Consider the ten-digit string "3184729506" — every digit is different from its neighbour, so every "run" has length exactly 1. Feeding this through the same rle_encode logic, each single-character run of length 1 still gets written as a (character, count) pair: the digit, followed by the digit "1". Tracing it digit by digit: "3"+"1", "1"+"1", "8"+"1", "4"+"1", "7"+"1", "2"+"1", "9"+"1", "5"+"1", "0"+"1", "6"+"1". Concatenating all ten pairs gives "31118141712191510161" — twenty characters, exactly double the original ten. Every character that had no repeated neighbour still had to carry an extra digit describing "how many times", and since that count was always just 1, RLE added pure overhead with zero benefit.

Notice something else about this particular example: because the alphabet here is digits, and the counts are also written as digits, a general-purpose rle_decode like the one above cannot safely tell where the "character" ends and the "count" begins — it would misread runs of digits as one giant count. Real lossless-compression formats solve this kind of ambiguity with reserved separator bytes or fixed-width fields. The lesson for you is that a compression scheme is only as good as the assumptions baked into its format, and those assumptions must be chosen to match both the data's structure and its alphabet — which is exactly why the earlier hand-traced example used letters, not digits, for the encode/decode round trip.

Beyond Repeats: Giving Common Symbols Shorter Codes

RLE exploits one specific kind of pattern: consecutive repetition. But plenty of data compresses well even without long runs, if some symbols simply appear far more often than others overall, without necessarily repeating back to back. English text is a good example — the letter "e" appears far more often than "z" in ordinary writing, even though neither one typically repeats consecutively.

This idea is far older than computers. Morse code, developed by Samuel Morse and Alfred Vail in 1837–38 for the electric telegraph, assigns short signals to the most frequent letters in English and long signals to the rare ones: "e", the most common letter, is a single dot, while "q", a rare letter, is dash-dash-dot-dash. Telegraph operators did not use these terms, but they were compressing English text by frequency — sending fewer total signal-lengths for a typical message than a scheme that gave every letter the same-length code would have needed. It took more than a century for this same idea to be formalised into a precise, provably optimal algorithm for computers: David Huffman published his algorithm, now called Huffman coding, in 1952, while he was a graduate student at MIT.

The key requirement that makes such variable-length codes work at all is that no code word may be a prefix of another code word — a property called being "prefix-free." If "e" were coded as 1 and "t" were coded as 10, a decoder reading the bit stream 10 could never be sure whether it had just seen "t", or "e" followed by the start of some other symbol whose code happens to begin with 0. Huffman's algorithm always produces a prefix-free code by construction, because — as you will see next — every symbol ends up at a distinct leaf of a binary tree, and no leaf's path from the root can ever be a prefix of another leaf's path.

Building a Huffman Code by Hand

Take the ten-character message "AAAAAABBBC": six A's, three B's, and one C. Counting frequencies: A appears 6 times, B appears 3 times, C appears 1 time.

Huffman's algorithm builds a binary tree from the bottom up, always merging the two least-frequent nodes into a new parent node whose frequency is their sum, and repeating until only one node — the root — remains:

1. Start: three separate nodes: C (frequency 1), B (frequency 3), A (frequency 6).
2. Merge step 1: the two smallest are C (1) and B (3). Merge them into a new internal node, call it X, with frequency 1 + 3 = 4. Remaining nodes: X (4), A (6).
3. Merge step 2: only two nodes remain, X (4) and A (6). Merge them into the root, with frequency 4 + 6 = 10 — which correctly equals the total length of the original ten-character message.

Every merge assigns a bit to each branch — by convention, 0 for the left branch and 1 for the right. Reading the path from the root down to each letter gives that letter's code. The diagram below shows the finished tree, with A hanging directly off the root along a single "1" edge, and B and C hanging one level deeper, underneath the internal node X:

Reading the paths off the tree: A sits one branch from the root along the "1" edge, so its code is simply 1. B sits two branches down — "0" to reach X, then "1" to reach B — so its code is 01. C sits two branches down along "0" then "0", so its code is 00. Notice that no code is a prefix of another: 1 is not a prefix of 01 or 00, and 01 is not a prefix of 00. A decoder reading bits one at a time can therefore always tell the instant a symbol's code is complete.

Now compare the total bits this code needs against a fixed-length code. There are three distinct symbols in the message. A fixed-length binary code needs enough bits to distinguish all of them: 1 bit only distinguishes 2 possibilities, so 3 symbols require 2 bits each (2 bits give you 4 possible codes, which is enough to cover 3 symbols, with one code left unused). Ten symbols at 2 bits each is 10 × 2 = 20 bits.

The Huffman code, by contrast, spends only 1 bit on every occurrence of A (the most frequent symbol) and 2 bits on every occurrence of B or C: 6 occurrences of A at 1 bit = 6 bits, 3 occurrences of B at 2 bits = 6 bits, 1 occurrence of C at 2 bits = 2 bits, for a total of 6 + 6 + 2 = 14 bits. That is a saving of 20 − 14 = 6 bits, or 6/20 = 30% fewer bits than the fixed-length code — achieved purely by giving the most common symbol the shortest code, exactly the same principle Morse code used for "e" more than a century earlier.

Why No Algorithm Can Compress Absolutely Everything

It is tempting to imagine an ultra-clever algorithm that shrinks any file, no matter what is in it — and then, since the output is itself a file, running that same algorithm on its own output again and again until the file vanishes to nothing. This is impossible, and the reason is a clean piece of counting logic called the pigeonhole principle: if you have more pigeons than pigeonholes, at least two pigeons must share a hole.

Apply this to compression. There are exactly 2⁸ = 256 different possible files that are exactly 8 bits long. Now count every possible file that is 7 bits or shorter: that is 2⁰ + 2¹ + 2² + ... + 2⁷ = 2⁸ − 1 = 255 distinct files. If a lossless compressor promised to shrink every 8-bit file down to 7 bits or fewer, it would need to assign each of the 256 different 8-bit files to one of only 255 possible shorter outputs. By the pigeonhole principle, at least two different 8-bit files would have to be compressed to the exact same output — but then decompression, looking only at that shared output, could not know which of the two original files to reconstruct. That breaks the core promise of lossless compression: perfect, unambiguous reversal. So no lossless algorithm can shrink every possible input; it can only shrink inputs that contain exploitable redundancy, and on some inputs it must leave the size unchanged or make it slightly bigger — exactly what happened to "3184729506" above.

This is also why re-zipping an already-zipped file rarely helps, and often makes it slightly larger. The first pass of compression already found and removed the file's redundant patterns; what comes out the other end looks close to random to a second pass of the same algorithm, and by the pigeonhole argument above, most already-compressed data simply has nowhere left to shrink to. Any file-size decrease you occasionally notice from double-compressing is coincidental, not a rule you can rely on — and the small header that every compressed format adds usually makes a second pass a net loss rather than a gain.

Compression at Work Around You

Once you know to look, lossless and lossy compression are working constantly in ordinary Indian digital life, each tuned to what that particular kind of data can afford to lose. When your class group forwards a scanned answer key or a datesheet image on WhatsApp, WhatsApp typically re-compresses images before sending — which is exactly why a forwarded photo often looks slightly softer than the original: some pixel information was sacrificed to cut the file down for faster delivery over patchy mobile networks. The QR code printed on an IRCTC ticket is a different kind of encoding rather than compression proper, but it relies on the same underlying idea of representing information compactly and unambiguously so a scanner at the station gate can recover the PNR instantly. When JioCinema or Hotstar streams an IPL match live, the video is lossy-compressed, and the app continuously adjusts the compression level in real time — lowering picture quality automatically when your network is slow, and raising it back on Wi-Fi — trading visual detail for a stream that does not keep buffering. And when ISRO downlinks imagery from an Earth-observation satellite, the raw sensor data captured in orbit is far too large to transmit over the available satellite bandwidth without compression; ground stations receive a compressed version and reconstruct the image, choosing lossless methods where the data will be used for precise scientific measurement, and lossy methods where visual inspection alone is enough.

Practice Questions

1. Run-length encode the string "MMMMMKKKKKKPP" by hand using the (character, count) format from this chapter. What is the compressed length, and what is the compression ratio compared to the original?
2. Explain, in your own words, why RLE performs poorly on the string "1212121212" even though it looks repetitive at a glance. (Hint: look closely at what actually repeats consecutively, character by character.)
3. Build a Huffman tree by hand for a message made of five occurrences of P, four occurrences of Q, and one occurrence of R. Show each merge step, assign 0/1 codes to each branch, and compute the total bits used. Compare this to a fixed-length code for the same nine-symbol message.
4. A friend claims: "I zipped my file, and then I zipped the zip file, and it got smaller again — so if I keep doing this, I can shrink any file down to almost nothing." Using the pigeonhole principle, explain what is wrong with generalizing this into "you can always keep shrinking."
5. Four symbols occur with frequencies W: 12, X: 6, Y: 1, Z: 1, in a 20-symbol message. Build the Huffman tree by hand, assign codes, and compute the total number of bits the encoded message needs. Compare it to a fixed-length code (remember: 4 symbols need at least 2 bits each).

Summary

• Compression re-represents data using fewer bits by exploiting patterns already present in it; it cannot create space out of nothing, so it only works where real redundancy exists.
• Lossless compression guarantees an exact, bit-for-bit original on decompression (needed for text, code, spreadsheets); lossy compression discards information judged unimportant to save far more space (used for photos, audio, video).
• Run-length encoding replaces a run of repeated characters with (character, count) pairs. It shrinks highly repetitive data dramatically but can expand data with no consecutive repeats, as it did on "3184729506" (10 → 20 characters).
• Compression ratio = original size ÷ compressed size; percentage saved = (1 − compressed/original) × 100.
• Huffman coding assigns shorter binary codes to more frequent symbols by repeatedly merging the two least-frequent nodes into a tree, guaranteeing a prefix-free code that a decoder can always read unambiguously.
• The pigeonhole principle proves no lossless algorithm can shrink every possible input — there are always more files of a given length than there are shorter files to map them to, so some inputs must stay the same size or grow.