Compression

Runs of one symbol, pointers back into what was already sent, then cosines that pile a signal's energy into a few numbers and the codec that throws the rest away.

Algorithms & Data Structures · Digital Sound & Music · Computer Graphics

Start: Run-Length Encoding

Progress0/4

Before you start

Some lessons here build on lessons from other arcs: Huffman Coding: Shorter Codes for Common Symbols, The DFT: Finding the Harmonics, Transform Coding: Keep What the Ear Will Miss Least.

1
Run-Length Encodingin review
Algorithms · Compression · ~15 min
Where a symbol repeats, send it once with a count. The simplest compressor there is: two bytes per run, a scanline of a bitmap shrinks, a line of prose doubles, and a cap splits the long runs.
2
LZ77: Compress by Pointing Backwardsin progress
Algorithms · Compression · ~25 min
Text repeats itself. At each position, look back through a window for the longest copy of what comes next and send a pointer instead of the characters. The decoder just copies. The other half of zip.
3
The DCT: Cosines Without Phasein review
Sound · Spectra · ~25 min
Measure one frame of samples against a family of cosines, watch the energy pile into the first few coefficients, and rebuild the frame from those alone: the transform under JPEG, MP3, and AAC.
4
Block Coding: How JPEG Throws Detail Awayin progress
Graphics · Images · ~30 min
Cut a picture into 8 by 8 blocks, turn each into cosine coefficients, divide by a table and round, zigzag the levels into runs, and see what the decoder gets back: the lossy heart of JPEG.