Data Compression


Survey Formats


Compression Methods



Lempel-Ziv (LZ)

Arithmetic Coding

Run Length Encoding

Burrows-Wheeler (BWT)



Basic Algorithm

Data Structure

Huffman Code Trees

Data and Lengths


Static and Dynamic


Data Formats




Deflate: Static and Dynamic Code Trees

Both code trees might be generated either statically by using a parameter set located within the coders or dynamically by using the corresponding header data.

The Deflate procedure uses a special format to represent the Huffman tree. Instead of probabilities or entire tree structures, they store only the code length belonging to a particular code. But, this requires additional specifications to ensure that each application is able the create identical code trees.

A firm order is assigned to all symbols, which is evaluated, if symbols are represented by the same code length. The left branch is always assigned to lower symbols (binary 0).

Symbols with a shorter code length are always assigned to the left branch too (binary 0).

Additionally the maximum code length is restricted to 15 bit. It has to be adapted, if the probability distribution provides larger values. The minimum value is 0, i.e. this symbol does not appear within the current block.

Information about the code length is also coded by a special type of Huffman code provided statically by the coders. This code tree additionally contains control characters indicating repetitions. In this way a simple Run Length Encoding (RLE) is established.

 <   ^   > 

Deflate Deflate: Distance Tree Deflate64™ (Enhanced Deflate)