DEFLATE

"Deflate" redirects here. For other uses, see Deflation (disambiguation).

In computing, deflate is a data compression algorithm and associated file format 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. The file format was later specified in RFC 1951.[1]

The original algorithm as designed by Katz was patented as U.S. Patent 5,051,745 and assigned to PKWARE, Inc.[2][3] As stated in the RFC document, an algorithm producing DEFLATE files is widely thought to be implementable in a manner not covered by patents.[1] This has led to its widespread use, for example in gzip compressed files, PNG image files and the .ZIP file format for which Katz originally designed it.

Stream format

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

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

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.

Compression is achieved through two steps:

Duplicate string elimination

Main article: LZ77 and LZ78

Within compressed blocks, if a duplicate series of bytes is spotted (a repeated string), then a back-reference is inserted, linking to the previous location of that identical string instead. An encoded match to an earlier string consists of an 8-bit length (3–258 bytes) and a 15-bit distance (1–32,768 bytes) to the beginning of the duplicate. Relative back-references can be made across any number of blocks, as long as the distance appears within the last 32 KB of uncompressed data decoded (termed the sliding window).

If the distance is less than the length, the duplicate overlaps itself, indicating repetition. For example, a run of 10 identical bytes can be encoded as one byte, followed by a duplicate of length 9 beginning 1 byte ago.

Bit reduction

Main article: Huffman coding

The second compression stage consists of replacing commonly used symbols with shorter representations and less commonly used symbols with longer representations. The method used is Huffman coding which creates an unprefixed tree of non-overlapping intervals, where the length of each sequence is inversely proportional to the probability of that symbol needing to be encoded. The more likely a symbol has to be encoded, the shorter its bit-sequence will be.

A tree is created, containing space for 288 symbols:

A match length code will always be followed by a distance code. Based on the distance code read, further "extra" bits may be read in order to produce the final distance. The distance tree contains space for 32 symbols:

Note that for the match distance symbols 2–29, the number of extra bits can be calculated as \frac{n}{2}-1.

The code is itself a canonical Huffman code sent by giving the bit length of the code for each symbol. The bit lengths are themselves run-length encoded to produce as compact a representation as possible. As an alternative to including the tree representation, the "static tree" option provides a standard fixed Huffman tree. The compressed size using the static tree can be computed using the same statistics (the number of times each symbol appears) as are used to generate the dynamic tree, so it is easy for a compressor to choose whichever is smaller.

Encoder/compressor

During the compression stage, it is the encoder that chooses the amount of time spent looking for matching strings. The zlib/gzip reference implementation allows the user to select from a sliding scale of likely resulting compression-level vs. speed of encoding. Options range from -0 (do not attempt compression, just store uncompressed) to -9 representing the maximum capability of the reference implementation in zlib/gzip.

Other Deflate encoders have been produced, all of which will also produce a compatible bitstream capable of being decompressed by any existing Deflate decoder. Differing implementations will likely produce variations on the final encoded bit-stream produced. The focus with non-zlib versions of an encoder has normally been to produce a more efficiently compressed and smaller encoded stream.

Deflate64/Enhanced Deflate

Deflate64, specified by PKWare, is a proprietary variant of the Deflate procedure. The fundamental mechanisms remain the same. What has changed is the increase in dictionary size from 32 KB to 64 KB, an addition of 14 bits to the distance codes so that they may address a range of 64 KB, and the length code, which is extended by 16 bits so that it may define lengths of three to 65538 bytes.[4] This leads to Deflate64 having a slightly higher compression ratio and a slightly lower compression time than Deflate.[5] Several free and/or open source projects support Deflate64, such as 7-Zip,[6] while others, such as zlib, do not, as a result of the proprietary nature of the procedure[7] and the very modest performance increase over Deflate.[8]

Using Deflate in new software

Implementations of Deflate are freely available in many languages. C programs typically use the zlib library (licensed under the zlib License, which allows use with both free and proprietary software). Programs written using the Borland dialects of Pascal can use paszlib; a C++ library is included as part of 7-Zip/AdvanceCOMP. Java includes support as part of the standard library (in java.util.zip). Microsoft .NET Framework 2.0 base class library supports it in the System.IO.Compression namespace.

Encoder implementations

AdvanceCOMP uses the higher compression ratio version of Deflate as implemented by 7-Zip (or optionally Zopfli in recent versions) to enable recompression of gzip, PNG, MNG and ZIP files with the possibility of achieving smaller file sizes than zlib is able to at maximum settings.

Hardware encoders

Decoder/decompressor

Inflate is the decoding process that takes a Deflate bit stream for decompression and correctly produces the original full-size data or file.

Inflate-only implementations

The normal intent with an alternative Inflate implementation is highly optimised decoding speed, or extremely predictable RAM usage for micro-controller embedded systems.

Hardware decoders

See also

References

  1. 1 2 L. Peter Deutsch (May 1996). DEFLATE Compressed Data Format Specification version 1.3. IETF. p. 1. sec. Abstract. RFC 1951. https://tools.ietf.org/html/rfc1951#section-Abstract. Retrieved 2014-04-23.
  2. ↑ US patent 5051745, Katz, Phillip W., "String searcher, and compressor using same", published 1991-09-24, issued 1991-09-24
  3. ↑ David, Salomon (2007). Data Compression: The Complete Reference (4 ed.). Springer. p. 241. ISBN 978-1-84628-602-5.
  4. ↑ Binary Essence – Deflate64
  5. ↑ Binary Essence – "Calgary Corpus" compression comparisons
  6. ↑ 7-Zip Manual and Documentation – compression Method
  7. ↑ History of Lossless Data Compression Algorithms – Deflate64
  8. ↑ zlib FAQ – Does zlib support the new "Deflate64" format introduced by PKWare?

External links

This article is issued from Wikipedia - version of the Tuesday, March 22, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.