Data Compression


Criteria

Survey Formats

Basics

Compression Methods

Shannon-Fano

Huffman

Lempel-Ziv (LZ)

Arithmetic Coding

Run Length Encoding

Burrows-Wheeler (BWT)

Implementations

Deflate

Basic Algorithm

Data Structure

Huffman Code Trees

Data and Lengths

Distance

Static and Dynamic

Deflate64™

Data Formats


Glossary

Index


Download


www.BinaryEssence.com

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)