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: Data Structure


Deflate subdivides the data into blocks, which may use a certain form of coding. This has to remain unchanged within the block.


Type Coding
uncompressed The original data will be taken over unchanged. The block will be introduced by header information specifying the size of the block. The maximum size is restricted to 64 kbyte.
compressed
static Huffman code
The data will be encoded according to the scheme as previously described. A standardized static Huffman code will be applied, stored within the encoder as well as in the decoder. Only codes are contained in the data stream.
compressed
dynamic Huffman code
The data will be encoded by a Huffman code defined individually. The header of each block therefore contains two Huffman codes, one for coding of data and sequence lengths and another one for coding of distances.


Both data blocks dedicated for compressed data are not restricted to a certain size. The end of the block will be indicated by a special control character.


Arrangement, size and repetition of the blocks is freely selectable by the encoder and may be used according to the needs. The achievable compression rate may vary therefore if the same original data had been encoded by different types of encoder.


 <   ^   > 

Deflate Deflate: Basic Algorithm Deflate: Huffman Code Trees