Lossless Algorithms

Lossless compression: basic principles

The defining property of lossless compression is preservation of information. After compression and decompression, the result has exactly the same bits as the source file. Data is not lost, changed, or reordered. This guarantee is required for text documents, computer programs, financial records, and scientific data when a changed bit could alter meaning or correctness.

Compression remains possible because data contains redundancy. Real-world data often includes patterns, repetitions, and predictable structures. Lossless algorithms detect these properties and store them in a compact representation. They preserve the information by changing its representation. Three common families are statistical methods such as Huffman coding, dictionary-based methods such as LZW, and repetition-based schemes such as Run-Length Encoding.

Statistical compression

Statistical redundancy comes from unequal symbol frequencies. In a sufficiently large sample, some symbols or values occur more often than others. In English text, for instance, E, T, and A occur more often than Z, Q, and X. ASCII defines characters with 7-bit values, although a character commonly occupies an 8-bit byte in storage. A fixed-width representation does not reflect symbol frequency. Statistical compression uses this difference to create compact codes.

The guiding principle is to assign shorter binary codes to frequent symbols and longer codes to rare symbols. The resulting message can have a lower average number of bits per symbol.

Huffman coding: a classic implementation

Developed by David A. Huffman in 1952, Huffman coding is a statistical compression algorithm. For a given alphabet and symbol frequencies, it constructs an optimal prefix code, meaning the lowest average length among prefix codes for that alphabet. Ties can produce different but equivalent code tables. The decoder must receive the table or a way to reconstruct it. The process can be broken down into several steps.

The first step is to read the source data and count the occurrences of each unique symbol. This determines the probability or frequency of each symbol. Use the example string "go go gophers".

We analyze the string and count the characters (including the space):

Next, we construct a special binary tree based on these frequencies. The process is iterative:

• Create a leaf node for each unique symbol, labeling it with the symbol and its frequency.
• Repeatedly find the two nodes in the collection with the lowest frequencies.
• Merge these two nodes into a new internal parent node. The frequency of this new parent node is the sum of the frequencies of its two children.
• Continue this process until all nodes have been merged into a single root node.

This structure usually places low-frequency symbols deeper in the tree and frequent symbols closer to the root. The resulting code is prefix-free, so a decoder can identify a symbol without a separator.

Once the tree is built, we assign the binary codes by traversing it. A common convention is to label every left branch as '0' and every right branch as '1'. The binary code for any symbol is the sequence of 0s and 1s encountered on the path from the root of the tree to that symbol's leaf node.

The original string "go go gophers" is now encoded by replacing each character with its new binary code. Huffman codes have the prefix property: no code is the beginning (prefix) of another code. For example, '00' is the code for 'g', and no other code starts with '00'. This property lets the decoder parse the compressed bitstream unambiguously without special separators between codes.

The decoder reads the bitstream one bit at a time, traversing the Huffman tree (which must be sent along with the data or be pre-defined) until it reaches a leaf node. Once a leaf is reached, the symbol is output, and the process repeats from the root of the tree.

Dictionary-based compression: finding repeated phrases

Statistical methods focus on the frequency of individual symbols. Larger-scale redundancy can occur in entire words or phrases that repeat. Dictionary-based methods find these sequences and replace them with short references.

The LZW (Lempel-Ziv-Welch) algorithm

The LZW algorithm is a classic dictionary-based technique used, among other places, in the GIF image format. During compression it builds a dictionary of strings from the data being processed.

Compress the string "ABABABA".

1. Initialization: The dictionary starts with all single characters. Assume A=1 and B=2.
2. Pass 1:
   • The compressor reads 'A'. It is in the dictionary.
   • It reads the next character 'B'. The string "AB" is NOT in the dictionary.
   • It outputs the code for 'A' (which is 1).
   • It adds "AB" to the dictionary with a new code (e.g., 3).
   • The current string becomes 'B'.
3. Pass 2:
   • The current string is 'B'. The next character is 'A'. "BA" is NOT in the dictionary.
   • Output the code for 'B' (which is 2).
   • Add "BA" to the dictionary (code 4).
   • The current string becomes 'A'.
4. Pass 3:
   • Current string is 'A'. Next is 'B'. "AB" IS in the dictionary (it was previously added with code 3).
   • Continue. Current string is "AB". Next character is 'A'. "ABA" is NOT in the dictionary.
   • Output the code for "AB" (which is 3).
   • Add "ABA" to the dictionary (code 5).
   • Current string becomes 'A'.
5. End of String:
   • The final remaining string is 'A'. Output its code (1).
6. Result: The original 7-character string "ABABABA" is encoded as the sequence of codes [1, 2, 3, 1]. In this example, the sequence can use fewer bits than seven literal characters, depending on code widths and format overhead. The decompressor reconstructs the same dictionary while reading the codes when it knows the initial dictionary and coding rules. The complete dictionary does not need to be sent.

This technique is useful for data with many repeated sequences, such as text, computer code, and some images. GIF can use it to encode repeated patterns in image rows.

Run-length encoding (RLE)

Run-Length Encoding stores a repeated data value as a pair containing the value and the run length. It is designed for data with long, contiguous runs of one value.

The RLE principle

Instead of storing every single symbol in a repetitive sequence, RLE stores only two pieces of information: the symbol itself and the number of times it repeats.

Use the diagram to watch RLE collapse each run into compact pairs and compare the encoded size against the raw sequence.

A sample line of a black and white image is represented by this sequence (W=white, B=black):

The raw representation would require 23 data units. Using RLE, we can encode this as:

This representation contains 8 fields (4 counts and 4 values), so it is shorter for this example before the field encoding overhead is included.

When to use RLE

RLE is effective for data with large, uniform areas. It can be used for:

• Computer-generated graphics like icons, logos, and charts.
• Simple animations.
• The output of certain image analysis processes where regions are segmented by color.

With short runs, as in photographs or noisy data, RLE can increase the size of the representation. Variants of RLE are used in formats such as PCX, BMP, and TIFF.

Combining methods: DEFLATE

Many lossless formats combine several methods. The DEFLATE format is used in ZIP and GZIP archives and in the compression stream of PNG. DEFLATE combines the dictionary-based LZ77 algorithm with Huffman coding. LZ77 replaces repeated strings with references described by length and distance, while other bytes remain literals. The literals and references are then coded with Huffman trees. The two stages represent repeated data and unequal symbol frequencies in one stream. DEFLATE divides data into blocks and can use fixed or dynamic Huffman trees. Effectiveness depends on the data and encoder settings.

A DEFLATE stream also carries block headers and, for a dynamic block, a description of its Huffman trees. These metadata bits belong to the compressed representation, so a short input can keep a similar size or become larger after encoding.