Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 55 ยท Data Representation

Compression and File Formats

Understand lossless and lossy compression, run-length and Huffman coding, file headers and magic numbers, and why a file extension can lie about what is inside.

Raw data is wasteful. A text full of repeated words, a photo with a large blue sky and a song with silent passages all contain patterns, and a pattern can be described more briefly than it can be listed. Compression is the art of storing the same information in fewer bytes. It is why a movie fits on a phone, why web pages load quickly and why you can email a folder as one small attachment.

This lesson explains the two big families of compression, builds two classic ideas (run-length encoding and Huffman coding) from scratch, and then looks at how files announce what they are. It follows Images, Sound and Video as Data, where you saw how large uncompressed media can be.

Two families: lossless and lossy

Lossless compression shrinks data in a way that can be reversed exactly. After decompressing you get back every original bit. It is essential for text, programs, spreadsheets and anything where a single wrong byte matters. ZIP, gzip, PNG and FLAC are lossless.

Lossy compression throws away information that people are unlikely to miss, and it cannot be undone. A JPEG photo discards fine color detail, MP3 and AAC remove sounds that are masked by louder ones, and video codecs drop detail between frames. The result is much smaller, often 10 times or more, but each time a file is re-saved in a lossy format it degrades a little further.

Lossless Lossy
Original recoverable? Yes, bit for bit No, only an approximation
Typical saving 2x to 4x for ordinary data 10x to 100x for media
Best for text, code, documents, archives, screenshots photos, music, video
Examples ZIP, gzip, PNG, FLAC, WebP lossless JPEG, MP3, AAC, H.264, WebP lossy

Keep a lossless or original copy of anything you may edit again. Edit the master, then export a lossy version for sharing.

Run-length encoding: describe the repeats

The simplest idea is run-length encoding (RLE). Instead of writing "WWWWWWWWWW", write "10W". It works well on data with long runs of the same value, such as a black-and-white drawing with big blank areas, and it is used inside several image formats.

It also has a weakness. If nothing repeats, every item gets a count in front of it and the output becomes larger than the input. The TryIt below shows both cases. Always test a compression idea on data that does not suit it.

JS A run-length encoder

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Notice the middle line: "ABCDEFGH" grows from 8 to 16 characters. Real formats avoid this by marking only the worthwhile runs.

Huffman coding: short codes for common symbols

Standard text uses 8 bits for every character, whether it is the very common "e" or the rare "q". Huffman coding assigns short bit patterns to frequent symbols and long ones to rare symbols, so the average length drops. It is the idea behind the entropy coding stage of many formats, including DEFLATE, which powers ZIP, gzip and PNG.

The method counts how often each symbol appears, then repeatedly joins the two rarest items into a tree node until one tree remains. Walking left (0) or right (1) from the root to a symbol gives its code. Because every symbol sits at a leaf of the tree, no code is the beginning of another code, so the bit stream can be decoded without separators.

flowchart TB
  R["root: 11"] -->|0| A["a: 5"]
  R -->|1| N6["6"]
  N6 -->|0| RR["r: 2"]
  N6 -->|1| N4["4"]
  N4 -->|1| B["b: 2"]
  N4 -->|0| N2["2"]
  N2 -->|0| C["c: 1"]
  N2 -->|1| D["d: 1"]

The Huffman tree for "abracadabra" (numbers are letter counts): a = 0, r = 10, b = 111, c = 1100, d = 1101.

The diagram shows the tree for the word "abracadabra". The TryIt below builds it, prints each symbol's code and decodes the result again.

JS Build a Huffman code

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The 11-letter word shrinks from 88 bits to 23, because "a" (five of eleven letters) gets a one-bit code. A real compressed file must also store the code table (or enough information to rebuild it), so tiny inputs gain little.

Real tools combine ideas. DEFLATE first replaces repeated phrases with references to earlier occurrences ("copy 12 bytes from 300 bytes back") and then Huffman-codes the result. Two limits are worth remembering: random data and data that is already compressed cannot be compressed much further, and zipping a JPEG hardly helps.

Lossy compression: trading detail for size

Lossy methods usually quantize: they round values to a coarser grid so there are fewer distinct values, and fewer distinct values are easier to encode compactly. The TryIt below rounds a list of brightness values to steps of different sizes. A bigger step means fewer distinct values (cheaper to store) but a larger worst-case error.

JS Rounding to save space

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Real codecs are smarter about what to round. JPEG converts blocks of pixels into frequencies and rounds the fine detail the most, because the eye notices small changes in smooth areas more than in busy ones.

File formats: how a file says what it is

A file format is an agreed layout for the bytes in a file. Most formats start with a header that records basic facts, such as image width and height, sample rate or the compression method, followed by the data. Formats differ in purpose:

  • Plain text (.txt, .csv, .json, .html) is readable in any editor and stores characters, usually as UTF-8 (see Text and Character Encoding).
  • Binary formats (.png, .jpg, .mp3, .pdf, .exe) pack data as raw numbers and need the right program to interpret them.
  • Containers (.zip, .mp4, .mkv, .docx) hold several things inside one file. A .docx file is really a ZIP archive of XML files and images.

Magic numbers and why extensions can lie

The ending of a file name, the extension, is only a label that helps the operating system choose a program. Renaming photo.jpg to photo.txt changes the label, not a single byte of content. Many formats start with a fixed signature, called a magic number, that programs use to recognize them:

Format First bytes (hex) As text
PNG 89 50 4E 47 0D 0A 1A 0A .PNG....
JPEG FF D8 FF not printable
PDF 25 50 44 46 2D %PDF-
ZIP (also docx, xlsx) 50 4B 03 04 PK..
gzip 1F 8B not printable

This is why extensions can lie: a file named invoice.txt can really be a PDF, and malware often hides behind a harmless-looking name such as photo.jpg.exe (the real extension is the last one, and some systems hide it). The honest way to know is to inspect the content. The stand-in below does what the Unix file command does on a small scale: it compares the first bytes with a list of signatures and the file name.

JS Do the file extensions tell the truth?

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The file bytes here are made up by hand and only their first few bytes are shown. Real programs read the first bytes of an actual file the same way, which is also how browsers decide how to handle a download when a server sends the wrong type.

Choosing a format

  • Photographs for the web: JPEG, or modern lossy formats such as WebP and AVIF.
  • Screenshots, logos and diagrams with sharp edges: PNG (lossless) or SVG (vector).
  • Music for listening: AAC or MP3 (lossy). For archiving or editing: FLAC or WAV.
  • Documents to share exactly as designed: PDF. Documents to edit: the word processor's own format.
  • Many files into one: ZIP. Better ratios with a tool such as 7z or tar.xz, but ZIP opens everywhere.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which statement about lossless compression is true?

    Lossless compression is fully reversible: decompressing returns every original bit. Lossy formats are the ones that discard detail.
  2. 2. What is run-length encoding of "AAAABBB"?

    Each run is replaced by its length followed by the symbol, as in this lesson: four As, then three Bs.
  3. 3. In Huffman coding, which symbols get the shortest codes?

    Frequent symbols get short codes and rare symbols get long ones, which lowers the average number of bits per symbol.
  4. 4. A file called notes.txt starts with the bytes 25 50 44 46 2D. What is it most likely?

    Those bytes spell %PDF- in ASCII, the magic number of PDF files. The extension is just a label and can be wrong.

Summary

  • Compression stores the same information in fewer bytes; lossless can be reversed exactly, lossy cannot.
  • Run-length encoding replaces repeats with counts; it can make non-repetitive data bigger.
  • Huffman coding gives short bit patterns to frequent symbols; DEFLATE (ZIP, gzip, PNG) combines it with phrase references.
  • Lossy methods quantize or discard detail people are unlikely to notice, trading quality for size.
  • Files have headers, and many start with magic numbers; an extension is only a label, so it can lie.

Next, open the machine itself with The CPU.