Compression · ⁨压缩⁩

The three letters that made the web possible

• In 1987 a programmer named Phil Katz wrote a compression program and put the file format in the public domain. He called it ZIP. He was 24.
• Nothing about the web works without that idea. A single uncompressed second of HD video is about 187 MB; a two-hour film would be 1.3 terabytes. Streaming it over a home connection is arithmetically impossible.
• The films you watch are perhaps a thousandth of that, and they still look right, because the compression throws away things your eye was never going to notice.
• This lesson is compression 压缩: the two families, the three lossless methods, and how to justify one for a given file.

Lossless and lossy

• Compression reduces a file's size, saving storage space and transmission bandwidth 带宽, and making downloads and streams faster.
• Lossless 无损 compression is compression from which the original data can be recovered exactly. ZIP and PNG are lossless.
• Lossy 有损 compression permanently removes some data, so the original cannot be recovered. JPEG, MP3 and streamed video are lossy.

Recover exactly, or shrink much further

Worked example: justify the choice

Run-length encoding

• Run-length encoding 行程编码 (RLE) replaces a run of repeated values with one value and a count: instead of eight identical white pixels, store "8, white".
• It is excellent on data with long runs, such as icons, diagrams, black-and-white scans and areas of flat colour.
• It is useless, and can make a file larger, on noisy data such as a photograph, where almost no two neighbouring values are equal.

Each row becomes counts and colours

Worked example: encode a row with RLE

Dictionary coding and Huffman coding

• Dictionary coding 字典编码, used by ZIP and PNG, builds a dictionary of repeated byte sequences and replaces each occurrence with a short index. It suits text and program code, where words and patterns recur.
• Huffman coding 霍夫曼编码 gives short codes to common symbols and long codes to rare ones, so the average code length falls. In "BANANA" the A is commonest and gets the shortest code.
• Both are lossless: the decoder rebuilds the original byte for byte.

Lossy methods

• Images (JPEG): fine detail and colour differences the eye barely notices are dropped.
• Sound (MP3, AAC): pitches we hear poorly are removed, along with quiet sounds masked by louder ones at the same moment.
• Video: spatial 空间 compression works within each frame, like JPEG, and temporal 时间 compression stores most frames as only the differences from the previous frame, since consecutive frames are nearly identical.

Worked example: how each kind of file is compressed

Why streaming must be lossy

• Raw HD video is gigabytes per minute, and a home connection carries a few megabits per second.
• Lossless compression on video achieves perhaps a factor of two, nowhere near enough, so the picture would keep stopping to buffer.
• Lossy compression achieves a factor of a hundred or more by discarding detail the viewer does not notice at normal speed. The reason names the bandwidth and the data rate, not just "it is smaller".

Marks that slip away

You've got it