C

1.3 Compression

Understanding compression techniques, lossy vs lossless compression, and practical applications

Learning Objectives

By the end of this lesson, you will be able to:

  • Show understanding of the need for and examples of the use of compression
  • Show understanding of lossy and lossless compression and justify the use of a method in a given situation
  • Show understanding of how a text file, bitmap image, vector graphic and sound file can be compressed
  • Understand and apply run-length encoding (RLE) to compress data
  • Explain how Huffman coding works as a lossless compression technique
  • Describe how MP3 and MP4 formats use compression for audio and video files
  • Identify appropriate compression methods for different file types and situations

Key Terms

Compression

Techniques used to reduce file size for storage and transmission

Lossless Compression

File size is reduced but no information is lost; original file can be re-created

Lossy Compression

File size is reduced with some loss of information; original file cannot be recovered

Run-length Encoding (RLE)

Lossless compression that reduces size of adjacent identical data

Huffman Coding

Lossless data compression algorithm that gives shorter codes to frequent characters

JPEG

Common file format for images that uses lossy compression

MP3 (MPEG-3)

Audio compression format that reduces file size by about 90%

MP4 (MPEG-4)

Format for storing multimedia files including video, audio, and images

Perceptual Music Shaping

MP3 technique that removes sounds unlikely to be noticed by human ear

Bitmap Image

Image represented as grid of pixels, each with color value

Vector Graphic

Image defined by mathematical equations, scalable without quality loss

Bandwidth

Amount of data that can be transmitted in a given time period

Compression Techniques

Larger files require larger storage capacity and lower transmission or download rates. Compression techniques are used to reduce file size.

The Need for Compression

  • Reduce storage space required on devices
  • Faster file transmission over networks
  • Lower bandwidth usage for downloads/uploads
  • Allow more files to be stored on limited storage
  • Enable streaming of media over internet connections
Real Example:

Without compression, a 3-minute song would be about 30MB. With MP3 compression, it becomes about 3MB - making it 10x faster to download!

Two Categories of Compression

Lossless Compression

File size is reduced but no information is lost. When necessary, the process can be reversed to re-create the original file.

Important for:

Text files, executable programs, documents where loss of any data would be disastrous.

Lossy Compression

File size is reduced with some loss of information. The original file can never be recovered.

Used for:

Sound files, image files where human ear/eye will hardly notice differences.

Lossless Compression Algorithms

Huffman Coding

A lossless data compression algorithm. Instead of having each character coded in one byte, an analysis is carried out to find most often used characters. These are then given shorter codes.

Huffman Coding Example

If a text contained only eight different letters:

Code Character
10 e
01 t
111 o
110 h
0001 l
0000 p
0011 w
0010 z

The original stream of bytes becomes a bit stream. Most frequent character gets smallest code and least frequent character gets largest code.

Huffman Coding Tree Visualization

How it works: Huffman coding builds a binary tree where frequently used characters have shorter paths (codes). Characters like 'e' and 't' (most common in English) get the shortest codes (01, 10), while rare characters like 'z' get longer codes (0010).

Run-length Encoding (RLE)

RLE can be used to compress a number of different file formats. It is a form of lossless file compression that reduces size of a string of adjacent, identical data such as repeated colours in an image.

How RLE Works

A repeating string is encoded into two values. First value represents number of identical data items in run. Second value represents code of data item.

aaaaabbbbccddddd
Original string: 16 characters = 16 bytes
5a4b2c5d
RLE encoded: 8 values = 8 bytes (50% compression)
RLE Text Compression Simulation
Original: aaaaabbbbccddddd
RLE Encoded: 5a4b2c5d
Original: 16 bytes Compressed: 8 bytes

Note: RLE is only effective where there is a long run of repeated units/bits. For varied data with few repeats, RLE may actually increase file size.

RLE with Images

RLE Image Compression Visualization

Black and white image showing letter F in a grid where each square requires 1 byte of storage. White square has value 1 and black square a value 0.

Original storage needed: 8 × 8 grid = 64 bytes
Compressed RLE format: 30 values = 30 bytes (53% compression)

How it works: The image is scanned row by row. Consecutive pixels of the same color are counted and stored as (count, color) pairs. For example, first row might be encoded as "8W" for 8 white pixels.

Real-Life RLE Example: Screen Display

Consider a screen containing plain black text on a solid white background. There will be many long runs of white pixels in the blank space, and many short runs of black pixels within the text.

Original (B=black, W=white):
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
RLE Encoded:
12W1B12W3B24W1B14W

The run-length code represents original 67 characters in only 18 - a 73% reduction in size!

Activity 1: RLE Compression Practice

Apply Run-length Encoding (RLE) to compress the following data:

  1. Text string: XXXYYZZZZZYYYYY
  2. Binary image data (0=white, 1=black): 0000011111000001111100000
  3. Calculate the compression ratio for each (Original size / Compressed size)

Remember: RLE stores (count, value) pairs. For text, values are characters. For binary, values are 0 or 1.

Solution:
  1. Text compression:
    Original: XXXYYZZZZZYYYYY (15 characters = 15 bytes)
    RLE: 3X2Y5Z5Y (8 values = 8 bytes)
    Compression ratio: 15/8 = 1.875 (47% size reduction)
  2. Binary image compression:
    Original: 0000011111000001111100000 (25 bits)
    RLE: 5 0, 5 1, 5 0, 5 1, 5 0 (10 values)
    Note: In practice, binary RLE might store counts only when value changes
  3. Key Insight: RLE works best with long runs of identical values. The binary example has perfect repeating patterns, so compression is very effective.

Check Your Understanding: Compression Techniques

Answer
  • [1 mark] Lossless compression reduces file size without losing any information; original file can be exactly reconstructed
  • [1 mark] Lossy compression reduces file size by removing some information; original file cannot be recovered
  • [Additional] Lossless is used for text, programs; lossy is used for images, audio where some quality loss is acceptable
Answer
  • [1 mark] Analyzes text to find frequency of each character
  • [1 mark] Assigns shorter binary codes to more frequent characters
  • [1 mark] Assigns longer binary codes to less frequent characters
  • [Additional] Creates a binary tree structure; common characters like 'e', 't' get codes like '01', '10' while rare characters get longer codes
Answer
  • [1 mark] When there are long runs of identical data values
  • [1 mark] Examples: Solid color backgrounds in images, repeated characters in text, black and white diagrams
  • [Additional] RLE is ineffective for data with frequent value changes as it may increase file size
Answer
  • [1 mark] Text files: Losing even a single character could change meaning or make file unusable
  • [1 mark] Images: Human eye may not notice small changes in color or detail
  • [1 mark] Lossy compression can achieve much higher compression ratios for images
  • [Additional] Example: Changing 'don't' to 'do t' changes meaning, but slightly changing pixel color in sky region of photo is unnoticeable
Answer
  • [1 mark] Original: AAAABBBCCDAAAE (14 characters)
  • [1 mark] RLE encoded: 4A3B2C1D3A1E
  • [Additional] Compression: 14 characters reduced to 10 values (count+character pairs)

Lossy Compression & Real Applications

Lossy compression reduces file size with some loss of information. The original file can never be recovered. Lossy compression can be used where a sound file or image file can have detailed coding removed when it's likely the human ear or eye will hardly notice any difference.

Photographic (Bitmap) Images

When a photographic file is compressed, both file size and quality of image are reduced. A common file format for images is JPEG, which uses lossy file compression.

  • Once image is subjected to JPEG compression algorithm, a new file is formed
  • The original file can no longer be constructed
  • JPEG reduces raw bitmap image by factor between 5 and 15
  • Reduction depends on quality of original image
Example:

A 10MB high-quality photo from a digital camera can be compressed to 1MB JPEG with minimal visible quality loss, making it suitable for web use.

Vector Graphics

Vector graphics can undergo file compression. Scalable vector graphics (.svg) are defined in text files which allows them to be compressed.

  • Vector graphics use mathematical equations to define shapes
  • They are resolution-independent (can be scaled without quality loss)
  • SVG files can be compressed using lossless methods like gzip
  • Commonly used for logos, icons, and technical drawings
Key difference:

Bitmap images store pixel data; vector graphics store mathematical instructions for drawing.

Image Compression Example from PDF

Consider following picture with brown pixels (b) on white background (w):

w
w
w
b
b
w
w
w
w
w
b
b
b
b
w
w
w
b
b
b
b
b
w
w
b
b
b
b
b
b
b
b
w
b
w
w
w
w
b
w
w
b
w
b
w
w
b
w
b
b
b
b
b
b
b
w

Lossy compression technique for this image: One example would be to reduce the colour depth for the coding of a bitmap. Instead of distinguishing between brown and white, we might use fewer colors.

File Compression in MPEG-3 (MP3) and MPEG-4 (MP4)

MPEG-3 (MP3)

MP3 uses technology known as audio compression to convert music and other sounds into an MP3 file format. This compression technology reduces size of a normal music file by about 90%.

Original CD Audio
80 MB

3-minute song on CD

MP3 Compressed
8 MB

90% size reduction

MP3 files use lossy format, since part of original file is lost following compression algorithm. Original file cannot be put back together again.

MPEG-4 (MP4)

MP4 files are slightly different to MP3 files. This format allows storage of multimedia files rather than just sound.

  • Music, videos, photos and animation can all be stored in MP4 format
  • Videos can be streamed over internet using MP4 format
  • Maintains good quality while reducing file size significantly
  • Uses both lossy and lossless compression techniques
Real Example:

YouTube videos use MP4 compression to stream high-quality video over the internet without excessive buffering.

MP3 Perceptual Music Shaping Simulation

TYK: When storing music tracks in a computer, MP3 format is used. This reduces file size by about 90%. Explain how music quality is apparently retained.

How MP3 compression works (Perceptual Music Shaping):

  • Removes frequencies outside human hearing range (below 20Hz, above 20kHz)
  • If two sounds are played at same time, only louder one can be heard by ear, so softer sound is eliminated
  • Removes sounds masked by other louder sounds
  • Certain parts of music can be removed without affecting quality too much

Compression Techniques for Different File Types

File Type Compression Techniques Type
Movie files Reduce the sampling rate used, reduce the frame rate Lossy
Image files Reduce the sampling resolution, decrease the colour/bit depth, reduce the image resolution Lossy
Text files Huffman coding, Run-length encoding Lossless
Sound files MP3 compression (perceptual music shaping) Lossy
Vector graphics Text-based compression (SVG), mathematical simplification Lossless/Lossy

Activity 2: Choosing Compression Methods

For each scenario below, recommend whether to use lossy or lossless compression and justify your choice:

  1. A software company distributing its new application for download
  2. A photographer uploading images to a portfolio website
  3. A hospital storing patient medical records digitally
  4. A music streaming service like Spotify
  5. An online map service storing road network data

Consider: What would happen if data was lost? How important is perfect reconstruction vs file size reduction?

Solution:
  1. Software application: Lossless - Any corruption could make program unusable. Must preserve exact binary code.
  2. Photographer portfolio: Lossy (JPEG) - Some quality loss acceptable for web display. Significant size reduction needed for fast loading.
  3. Medical records: Lossless - Critical data where any loss could be disastrous. File size less important than accuracy.
  4. Music streaming: Lossy (MP3/AAC) - 90% size reduction essential for streaming. Human ear won't notice removed sounds.
  5. Map data: Lossless or Vector compression - Accuracy critical for navigation. Vector graphics allow lossless compression of mathematical data.

Check Your Understanding: Lossy Compression & Applications

Answer
  • [1 mark] JPEG compression permanently removes some image data/information
  • [1 mark] The original file cannot be reconstructed from the compressed version
  • [Additional] JPEG reduces file size by 5-15 times by simplifying color information and removing details human eye won't notice
Answer
  • [1 mark] Uses perceptual music shaping - removes sounds human ear is unlikely to notice
  • [1 mark] Eliminates frequencies outside human hearing range (below 20Hz, above 20kHz)
  • [1 mark] When two sounds play simultaneously, removes the softer sound (masking effect)
  • [Additional] Example: 80MB CD track becomes 8MB MP3 with minimal audible difference
Answer
  • [1 mark] MP3 is for audio compression only (music, sounds)
  • [1 mark] MP4 can store multimedia: music, videos, photos, animation
  • [1 mark] MP4 allows streaming of videos over internet without significant quality loss
  • [Additional] MP3 reduces size by ~90%; MP4 provides good compression for video while maintaining quality for streaming
Answer
  • [1 mark] RLE stores (count, color) pairs for consecutive identical pixels
  • [1 mark] If image has few/no sequences of same color, RLE stores each color with count 1
  • [1 mark] Example: Red-Green-Blue pattern would become Red1 Green1 Blue1, increasing file size
  • [Additional] RLE only effective for images with large areas of solid color (like cartoons, text on plain background)
Answer
  • [1 mark] Customers can download photographs in less time
  • [1 mark] Compressed photos use less bandwidth
  • [1 mark] Photos take up less storage space on customer's device
  • [Additional] Customers can store more images and have more space for other files

Key Takeaways

  • Compression reduces file sizes for efficient storage and faster transmission over networks
  • Lossless compression preserves all data - essential for text files, programs, documents (Huffman coding, RLE)
  • Lossy compression removes some data - acceptable for images, audio, video where quality loss is barely noticeable (JPEG, MP3)
  • Run-length Encoding (RLE) compresses consecutive identical values into (count, value) pairs - effective for data with long repeats
  • Huffman coding gives shorter codes to frequent characters, longer codes to rare characters
  • JPEG uses lossy compression for images, reducing file size by 5-15 times with minimal visible quality loss
  • MP3 reduces audio files by ~90% using perceptual music shaping - removing inaudible sounds
  • MP4 supports multimedia compression for video, audio, images - enabling streaming with good quality
  • RLE may increase file size if data has few repeated values (e.g., complex photographs)
  • Choose compression method based on content: lossless for critical data, lossy for media files
  • Vector graphics (SVG) use mathematical descriptions and can be compressed differently than bitmap images
  • Compression benefits users through faster downloads, lower bandwidth use, and more storage capacity

Question Bank

Marking Scheme & Answer
  • [1 mark] Reduces storage space required on devices and servers
  • [1 mark] Enables faster file transmission/download over networks
  • [1 mark] Reduces bandwidth usage, allowing more efficient network use
  • [1 mark] Allows more files to be stored on limited storage media
  • [Additional] Essential for streaming media, web pages with images, and mobile devices with limited storage
Marking Scheme & Answer
  • [1 mark] RLE compresses consecutive identical data items
  • [1 mark] Stores data as (count, value) pairs
  • [1 mark] Example text: "aaaaabbbbccddddd"
  • [1 mark] Original: 16 characters = 16 bytes
  • [1 mark] RLE encoded: "5a4b2c5d" = 8 values
  • [1 mark] Compression: 16 bytes → 8 bytes (50% reduction)
  • [Additional] Only effective for data with long runs; may increase size for varied data
Marking Scheme & Answer
Lossless Compression:
  • No information lost
  • Original file can be reconstructed
  • Used for text, programs, documents
  • Examples: ZIP, Huffman coding, RLE
  • Essential when data integrity is critical
Lossy Compression:
  • Some information permanently lost
  • Original cannot be recovered
  • Used for images, audio, video
  • Examples: JPEG, MP3, MP4
  • Higher compression ratios possible
Commonality: Both reduce file size for more efficient storage and transmission.
Marking Scheme & Answer
  • [1 mark] Analyzes frequency of each character in the text
  • [1 mark] Creates a binary tree with frequent characters near the root
  • [1 mark] Assigns shorter binary codes to frequent characters
  • [1 mark] Assigns longer binary codes to infrequent characters
  • [1 mark] Replaces fixed-length codes (e.g., 8-bit ASCII) with variable-length codes
  • [Additional] Example: 'e' (common) gets code '10', 'z' (rare) gets code '0010'
Marking Scheme & Answer
  • [1 mark] Uses perceptual music shaping/audio compression
  • [1 mark] Removes frequencies outside human hearing range (below 20Hz, above 20kHz)
  • [1 mark] Eliminates softer sounds when louder sounds occur simultaneously (masking)
  • [1 mark] Reduces file size by about 90% (80MB CD → 8MB MP3)
  • [1 mark] Lossy because original audio data cannot be recovered; some sounds permanently removed
Marking Scheme & Answer
  • [1 mark] RLE works best with long runs of identical colors/pixels
  • [1 mark] Complex photographs have frequent color changes between adjacent pixels
  • [1 mark] Would need to store each color with count 1, increasing file size
  • [1 mark] Example: Red-Green-Blue pattern becomes R1 G1 B1 instead of RGB
  • [Additional] RLE effective for simple images (cartoons, text on solid background) but not for photos
Marking Scheme & Answer
  • [1 mark] Bitmap images store pixel color data; compressed using techniques like JPEG (lossy) or RLE (lossless)
  • [1 mark] Vector graphics store mathematical equations/instructions for drawing shapes
  • [1 mark] Vector files (like SVG) are text-based and can use text compression methods
  • [1 mark] Vector graphics scale without quality loss; bitmaps lose quality when enlarged
  • [Additional] Vector compression often lossless; bitmap compression often lossy for significant size reduction
Marking Scheme & Answer
  • [1 mark] When significant file size reduction is needed and some quality loss is acceptable
  • [1 mark] Example 1: Storing photos on a website (JPEG compression)
  • [1 mark] Example 2: Streaming music (MP3/AAC compression)
  • [1 mark] When file will be used in contexts where minor quality differences won't be noticed
  • [Additional] Lossy provides much higher compression ratios (e.g., 90% for MP3 vs 50% for typical lossless)
Marking Scheme & Answer
  • [1 mark] Technique that removes sounds unlikely to be noticed by human ear
  • [1 mark] Eliminates frequencies outside human hearing range (20Hz-20kHz)
  • [1 mark] Removes softer sounds when louder sounds occur at same time (auditory masking)
  • [Additional] Allows 90% file size reduction while maintaining acceptable audio quality
Marking Scheme & Answer
  • [1 mark] Lossy compression (e.g., JPEG) should be used
  • [1 mark] Provides significant file size reduction (5-15 times smaller)
  • [1 mark] Faster download times for website visitors
  • [1 mark] Human eye won't notice minor quality reduction for web display
  • [Additional] Lossless would produce larger files, slowing page load times without visible quality benefit for typical web viewing