Why Compress Data?

Compression reduces the size of a file or data stream by encoding information more efficiently. It is used to:

• Reduce storage requirements (smaller files take up less disk space).
• Reduce transmission time (smaller files transfer faster over networks).
• Reduce bandwidth usage (less data sent = lower network costs).
• Enable streaming (e.g. video/audio streamed in real time must be small enough to transmit as it plays).

There are two fundamentally different approaches: lossless and lossy compression.

Lossless Compression

In lossless compression, the original data is perfectly reconstructed after decompression — no data is lost. The compressed file, when decompressed, is identical (bit-for-bit) to the original.

• Used when every bit of data matters: text files, executable programs, source code, spreadsheets, database files.
• Cannot achieve as high a compression ratio as lossy compression for media files.
• Examples of lossless formats: ZIP, PNG, GIF, FLAC (audio), PDF (usually).

Run-Length Encoding (RLE)

Run-Length Encoding is a simple lossless algorithm that replaces consecutive repeated values with a count and the repeated value.

Example: The string AAABBBBCCDDDDDD becomes 3A4B2C6D — where each number is the run length (count) of the following symbol.

• RLE is efficient when data contains many consecutive repeated values (long runs).
• Most effective on: simple bitmap images (e.g. black-and-white fax images, simple icons), PCX image format.
• Inefficient on: photographs, random data, already-compressed files — adding the count can make the file larger for short runs.
• Binary RLE for images: each pixel row is encoded as runs of the same colour — e.g. 50 white 30 black 20 white instead of storing 100 individual pixel values.

Dictionary Coding (e.g. LZ77, LZW)

Dictionary coding replaces repeated sequences of symbols with a reference to a dictionary entry (an index number pointing to a previously seen pattern). The most common variants are LZ77 and LZW, which underpin ZIP and GIF compression.

• LZW (Lempel–Ziv–Welch): builds a dictionary as it reads the data. Repeated sequences are replaced with their dictionary index.
• Example: in a file with many repetitions of "the", "and", "computer", each occurrence after the first is replaced by a short numeric code.
• The dictionary is rebuilt from the compressed data during decompression — so it doesn't need to be stored separately.

Huffman Coding

Huffman coding assigns shorter bit codes to more frequent symbols and longer codes to less frequent symbols, reducing the total number of bits needed.

• A Huffman tree is built: the most frequent characters are near the root (short path = short code); least frequent are at the leaves (long path = longer code).
• Used in JPEG, MP3, ZIP, and many other formats.
• In standard ASCII, every character takes 8 bits. In Huffman coding, a frequent letter like 'E' might take only 3 bits while a rare letter like 'Z' takes 10 bits — overall fewer bits if the frequency distribution is skewed.
• This is a variable-length encoding scheme.

Lossy Compression

In lossy compression, some data is permanently discarded — typically data that humans are unlikely to notice is missing. The original file cannot be perfectly reconstructed from the compressed version.

• Achieves much higher compression ratios than lossless compression.
• Used for media (images, audio, video) where perfect accuracy is less important than file size.
• Repeated lossy compression degrades quality further each time.
• Examples of lossy formats: JPEG (images), MP3/AAC (audio), MP4/H.264 (video), OGG.

Lossy Image Compression: JPEG

• Divides the image into 8×8 pixel blocks.
• Converts each block from RGB colour to a frequency representation using Discrete Cosine Transform (DCT).
• High-frequency detail (fine edges and textures) is discarded more aggressively than low-frequency information (broad areas of similar colour) — the human eye is less sensitive to high-frequency variation.
• A quality slider controls how much detail is discarded — lower quality = smaller file = more visible artefacts.

Lossy Audio Compression: MP3

• Uses perceptual audio coding — discards sounds the human ear is unlikely to perceive.
• Louder sounds mask quieter sounds at similar frequencies (auditory masking) — the quieter sounds are discarded.
• Very high and very low frequencies beyond normal hearing range are also discarded.
• The result is a file roughly 10× smaller than uncompressed WAV/AIFF audio with minimal perceived quality loss.

Comparing Lossless vs Lossy

Compression Ratio

The compression ratio measures how much a file has been reduced:

Compression ratio = Original size ÷ Compressed size

Example: a 10 MB file compressed to 2 MB has a compression ratio of 10 ÷ 2 = 5:1.