Introduction to Compression

The need for data compression

Digital devices and services generate, transmit, and store large amounts of data. A smartphone can hold thousands of high-resolution photos and videos. Services such as Netflix, Disney+, and YouTube stream video, while websites combine text, images, and code.

Raw versions of this content require substantial storage. A single minute of uncompressed high-definition video can occupy gigabytes. Sending such a file over a typical connection could take hours, and a few movies could fill a drive. Without smaller representations, some services would be impractical or expensive.

Data compression encodes information with fewer bits than the initial representation. Lossless compression permits exact reconstruction, while lossy compression discards some information. The goal is to reduce storage requirements and transmission time. Smaller files use less space on drives, servers, and memory cards and move faster across networks, from local LANs to the internet.

Compression changes the representation of source information; lossy compression also changes part of the retained data. Its effectiveness depends on the input: repeated symbols and predictable samples can be coded more briefly, while random data may not become shorter. A file format can combine stages such as modeling, transformation, and entropy coding. The method must also account for encoding time, decoder requirements, and acceptable quality loss. A codec defines a coding procedure, while a container defines how coded streams and metadata are packaged.

The theoretical basis: Claude Shannon and information theory

The theoretical basis of compression was developed in the mid-20th century through the work of American mathematician and engineer Claude E. Shannon. His research supplied a mathematical framework for describing the limits and possibilities of source coding.

In his 1948 paper, "A Mathematical Theory of Communication," Shannon introduced concepts used to analyze information:

• The Bit as a Unit of Information: He formalized the bit as the basic unit of information, representing the answer to a single yes/no question.
• Information entropy: Shannon introduced the concept of entropy to quantify the average information in a message from a data source. Entropy describes source uncertainty. A random, hard-to-predict stream has high entropy, while a repetitive stream has low entropy.
• The source coding theorem: The theorem gives an asymptotic limit for lossless compression of long sequences from a specified source model. The average number of bits per symbol cannot fall below the source entropy, while rates above the entropy are achievable with suitable coding.

In a subsequent 1951 paper, "Prediction and entropy of printed English," he analyzed the statistical properties of English. Letters and letter combinations have different frequencies; for example, 'e' is common and 'q' is usually followed by 'u'. This redundancy makes written English compressible. Identifying and reducing redundancy is a principle used by many compression techniques.

Shannon's communication model

Shannon also proposed a general model for a communication system that can describe the transmission of compressed data:

1. Information Source: The origin of the message (e.g., a person speaking).
2. Transmitter (Encoder): Transforms the message into a signal suitable for transmission. In our context, this is the compression algorithm.
3. Channel: The medium through which the signal is sent (e.g., an internet cable, radio waves). The channel is where noise and interference can corrupt the signal.
4. Receiver (Decoder): Transforms the received signal back into a message for the destination. This is the decompression algorithm.
5. Information Destination: The final recipient of the message (e.g., the person listening on the other end).

The compressor and decompressor perform source coding. Their task is to change the representation while preserving the required information. Channel coding serves a different purpose: it adds controlled redundancy for detecting or correcting transmission errors.

What do we compress? Applications across data types

Compression is used for many kinds of digital data to reduce the size of their representations.

• Video: Uncompressed video requires substantial storage. Codecs and standards such as H.264/AVC, H.265/HEVC, and AV1 support streaming (YouTube, Netflix) and video conferencing. H.264/AVC and H.265/HEVC are also used on Blu-ray discs.
• Images: JPEG is used for photographic images, usually with some information loss. PNG and GIF are used for graphics, diagrams, and images with sharp lines.
• Audio and music: Formats such as MP3 and AAC use perceptual coding to omit components that may be weakly audible. This reduces files used by digital music players and streaming services such as Spotify and Apple Music.
• Speech: In mobile telephony (GSM, VoLTE) and VoIP applications (Skype, Zoom), specialized speech codecs compress the human voice to use minimal network bandwidth.
• Text and archives: Text files are small, but large collections can benefit from compression. Archive formats such as ZIP, RAR, and 7z compress text and other files, reducing software downloads and backups.

In practice, a format specifies more than an algorithm. It also defines headers, parameters, and auxiliary data. This overhead affects small files. For long streams, the source model and dependencies between symbols have a larger effect on the result.

For example, Deflate combines LZ77 repetition search with Huffman coding. ZIP is an archive container that can store Deflate-compressed data together with headers and file metadata.

Advantages and disadvantages of compression

Compression reduces storage and transmission requirements, but it requires computation and can alter data.

Advantages

• Reduced storage requirements: Less disk space is needed, so more files can be stored on devices and in the cloud.
• Faster data transmission: Smaller files can transfer more quickly over networks, shortening downloads and streaming transfers.
• Bandwidth use: Compression allows more users or services to share a network connection.
• Lower costs: Lower storage and bandwidth requirements can reduce costs for data centers, network providers, and data transfer.

Disadvantages

• Computational overhead: Compression and decompression require processing power. Complex algorithms can affect mobile battery life and require capable hardware for real-time video encoding.
• Quality loss in lossy compression: Selected data is permanently discarded. At a high compression level, visible image artifacts or audible distortion can appear.
• Error sensitivity: In a compressed stream, a bit error can damage a larger section when the decoder relies on dependencies between data. The scale depends on the format and its protection mechanisms. In an uncompressed file, the same error may affect only one pixel or sound sample.

The divide: lossless and lossy compression

A basic division of compression methods follows from whether the process is reversible. The two categories are lossless and lossy compression.

Choosing between lossless and lossy depends on the application. Archiving important documents requires lossless compression. When sharing vacation photos online, lossy compression can reduce the file to a practical transmission size. This distinction is a basic concept in data compression.