DEFLATE / INFLATE from Zlib package

In computing, Deflate (raw) is a lossless data compression file format that uses a combination of LZSS and Huffman coding. It was designed by Phil Katz, for version 2 of his PKZIP archiving tool. Deflate was later specified in RFC 1951 (1996).[1]

Inflate (raw) is the reverse of Deflate (raw); decompressing the data into its initial form.

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

First 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.
Second and third bits: Encoding method used for this block type:
    00: A stored (a.k.a. raw or literal) section, between 0 and 65,535 bytes in length
    01: A static Huffman compressed block, using a pre-agreed Huffman tree defined in the RFC
    10: A compressed block complete with the Huffman table supplied
    11: Reserved—don't use.

The stored block option adds minimal overhead, and is used for data that is incompressible.[1]

Most compressible data 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. The static Huffman option is used for short messages, where the fixed saving gained by omitting the tree outweighs the percentage compression loss due to using a non-optimal (thus, not technically Huffman) code.[1]

Compression is achieved through two steps:[1]

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


Choose from 107 ops
Latest ops 0
Favorite ops 0