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: Huffman Code Trees


Two different code trees are used for coding. The first tree contains codes for original data (called literals by the specification) and the sequence lengths. The second is intended for the distances.


The combination of data and length is due to the fact, that each code starts with either an original symbol or a sequence length. If the decoder determines an original symbol, it can be written to the data stream. If a length code appear, a distance code will inevitably follow.


Scheme: compressed data in Deflate


Scheme: compressed data in Deflate


 <   ^   > 

Deflate Deflate: Data Structure Deflate: Code Tree for Original Data and Sequence Lengths