DEFLATE

related topics
{system, computer, user}
{math, number, function}
{rate, high, increase}
{language, word, form}

Deflate is a lossless data compression algorithm that uses a combination of the LZ77 algorithm and Huffman coding. It was originally defined by Phil Katz for version 2 of his PKZIP archiving tool, and was later specified in RFC 1951.

Deflate is widely thought to be free of any subsisting patents, and at a time before the patent on LZW (which is used in the GIF file format) expired, this has led to its use in gzip compressed files and PNG image files, in addition to the ZIP file format for which Katz originally designed it.

Contents

Stream format

A Deflate stream consists of a series of blocks. Each block is preceded by a 3-bit header:

  • 1-bit: Last block in stream marker:
    • 1: this is the last-block in the stream.
    • 0: there are more blocks to process after this one.
  • 2-bits: Encoding method used for this block type:
    • 00: a stored/raw/literal section follows, between 0 and 65,535 bytes in length.
    • 01: a static Huffman compressed block, using a pre-agreed Huffman tree.
    • 10: a compressed block complete with the Huffman table supplied.
    • 11: reserved, don't use.

Most blocks will end up being encoded using method 10, the dynamic Huffman encoding, which produces an optimised Huffman tree customised for each block of data individually. Instructions to generate the necessary Huffman tree immediately follow the block header.

Compression is achieved through two steps

  • The matching and replacement of duplicate strings with pointers.
  • Replacing symbols with new, weighted symbols based on frequency of use.

Duplicate string elimination

Full article ▸

related documents
Talker
Machine code
Rsync
Baudot code
GNU Privacy Guard
Blitz BASIC
Software bug
ReiserFS
Byte
Parrot virtual machine
MMX (instruction set)
Complex instruction set computer
Object Linking and Embedding
NewtonScript
Vim (text editor)
Lotus Symphony
UCSD Pascal
GNU Debugger
FIFO
JFS (file system)
Ext2
Wikipedia:Free On-line Dictionary of Computing/L - N
Journaling file system
Digital signal
Cyrix 6x86
GNU
Signal-to-noise ratio
Traceroute
2D computer graphics
List of ad-hoc routing protocols