NationMaster - Encyclopedia: DEFLATE

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. Lossless data compression is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ... LZ77 and LZ78 are the names for the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. ... In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. ... Phil Katz, shown in 1994, holds a computer disk containing compression software made by his company, PKWare Inc. ... PKZIP is an archiving tool originally written by the late Phil Katz, and marketed by his company PKWARE, Inc. ...

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. A patent is a set of exclusive rights granted by a state to a patentee for a fixed period of time in exchange for a disclosure of an invention. ... LZW (Lempel-Ziv-Welch) is an implementation of a lossless data compression algorithm created by Abraham Lempel and Jacob Ziv. ... An example of a GIF image. ... The correct title of this article is . ... PNG (Portable Network Graphics) is a bitmapped image format that employs lossless data compression. ... The ZIP file format is the most widely-used compressed file format in the IBM PC world. ...

Using DEFLATE in new software

Implementations of deflate are freely available in many languages. C programs typically use the zlib library (under a BSD-like licence without advertising clause). 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. zlib is an open-source, cross-platform data compression library. ... The zlib license is a permissive free software license which defines the terms under which the zlib and libpng software libraries can be distributed. ... Borland Software Corporation is a software company headquartered in Austin, Texas. ... C++ (pronounced see plus plus, IPA: ) is a general-purpose, programming language with high-level and low-level capabilities. ... 7-Zip is an open source file archiver designed originally for the Microsoft Windows operating system, and later made available to other systems. ... AdvanceCOMP is a set of command line data (re-)compression tools. ... The . ...

Stream format

A DEFLATE stream consists of a series of blocks. Each block is preceded by a 3-bit header: This article is about the unit of information. ...

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.

Duplicate string elimination

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 a length (3-258 bytes) and a distance (1-32768 bytes). Relative back-references can be made across any number of blocks, as long as the distance appears within the last 32kB of uncompressed data decoded (termed the sliding window). LZ77 and LZ78 are the names for the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. ... This article discusses a general notion of reference in computing. ...

Bit reduction

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 bit-sequences, where the length of each sequence is inversely proportional to the likelihood of that symbol needing to be encoded. The more likely a symbol has to be encoded, the shorter its bit-sequence will be. In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. ... In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. ...

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

n / 2 - 1

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. A sliding scale is a scale (usually a payment scale) the values of which depend on another related factor. ...

Other DEFLATE encoders have been produced, all of which will also produce a compatible bit-stream 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 small encoded stream.

Encoder Implementations

AdvanceCOMP uses the higher compression ratio version of DEFLATE as implemented by 7-Zip 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. An even more effective (but also more user-input-demanding and CPU intensive) DEFLATE encoder is employed inside Ken Silverman's KZIP and PNGOUT utilities. PKZIP is an archiving tool originally written by the late Phil Katz, and marketed by his company PKWARE, Inc. ... Phil Katz, shown in 1994, holds a computer disk containing compression software made by his company, PKWare Inc. ... PKZIP is an archiving tool originally written by the late Phil Katz, and marketed by his company PKWARE, Inc. ... zlib is an open-source, cross-platform data compression library. ... The correct title of this article is . ... Java is a programming language originally developed by Sun Microsystems and released in 1995. ... The BSD license is a permissive license and is one of the most widely used free software licenses. ... Wikibooks has a book on the topic of Pascal Pascal is an imperative computer programming language, developed in 1970 by Niklaus Wirth as a language particularly suitable for structured programming. ... PNGOUT is a free optimizer for PNG images and is written by Ken Silverman. ... He invented the Build Engine Ken Silverman (born November 1, 1975) is a jewish game programmer best known for writing the Build engine used in Duke Nukem 3D, Redneck Rampage, and more than a dozen other games in the mid- to late-1990s. ... The Commodore 64 is the best-selling single personal computer model of all time. ... The Commodore 128 (C128, CBM 128, C=128) home/personal computer was Commodore Business Machiness (CBM) last commercially released 8-bit machine. ... DeflOpt is a tool created by Ben Jos Walbeehm, designed to optimize the storage of Deflate streams contained in several types of files. ... C++ (pronounced see plus plus, IPA: ) is a general-purpose, programming language with high-level and low-level capabilities. ... In computer security, the word vulnerability refers to a weakness in a system allowing an attacker to violate the confidentiality, integrity, availability [i. ... 7-Zip is an open source file archiver designed originally for the Microsoft Windows operating system, and later made available to other systems. ... AdvanceCOMP is a set of command line data (re-)compression tools. ... C++ (pronounced see plus plus, IPA: ) is a general-purpose, programming language with high-level and low-level capabilities. ... PuTTY is a free software SSH, Telnet, rlogin, and raw TCP client. ... AdvanceCOMP is a set of command line data (re-)compression tools. ... 7-Zip is an open source file archiver designed originally for the Microsoft Windows operating system, and later made available to other systems. ... The correct title of this article is . ... PNG (Portable Network Graphics) is a bitmapped image format that employs lossless data compression. ... Multiple-image Network Graphics (MNG) (IPA pronunciation: ) is a public graphics file format for animated images. ... The ZIP file format is the most widely-used compressed file format in the IBM PC world. ... zlib is an open-source, cross-platform data compression library. ... He invented the Build Engine Ken Silverman (born November 1, 1975) is a jewish game programmer best known for writing the Build engine used in Duke Nukem 3D, Redneck Rampage, and more than a dozen other games in the mid- to late-1990s. ...

Other possible focuses for a DEFLATE implementation could be super-fast compression speed, or being designed to have a very small executable code such for use in embedded systems. Further requirements could be to have a separate license on the software, or for the code to be written in a language such Java or Python. In theory it might be possible for an implementation to produce an encoding that attempted to avoid certain symbols appearing in the output stream, avoiding blacklisted sequences or NUL bytes in a particular context. Java is a programming language originally developed by Sun Microsystems and released in 1995. ... Python is a high-level programming language first released by Guido van Rossum in 1991. ... A blacklist is a list or register of entities who, for one reason or another, are being denied a particular privilege, service, or mobility. ...

Hardware Encoders

For other meanings of PCI, see PCI (disambiguation). ... To meet Wikipedias quality standards, this article or section can be improved by converting lengthy lists to text. ... Windows XP loading drivers during a Safe Mode bootup A device driver, or a software driver is a specific type of computer software, typically developed to allow interaction with hardware devices. ... The Apache HTTP Server, commonly referred to simply as Apache, is a web server notable for playing a key role in the initial growth of the World Wide Web. ... Xilinx, Inc. ... Virtex is a series of FPGAs produced by Xilinx. ... A field-programmable gate array or FPGA is a gate array that can be reprogrammed after it is manufactured, rather than having its programming fixed during the manufacturing — a programmable logic device. ... This article does not cite any references or sources. ... For other meanings of PCI, see PCI (disambiguation). ... For other meanings of PCI, see PCI (disambiguation). ... It has been suggested that this article or section be merged with SAN. (Discuss) Look up san, -san in Wiktionary, the free dictionary. ...

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.

Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, standardised by ANSI X3. ... GNU logo The GNU Lesser General Public License (formerly the GNU Library General Public License) is an FSF approved Free Software license designed as a compromise between the GNU General Public License and simple permissive licenses such as the BSD license and the MIT License. ... C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ... GNU logo The GNU Lesser General Public License (formerly the GNU Library General Public License) is an FSF approved Free Software license designed as a compromise between the GNU General Public License and simple permissive licenses such as the BSD license and the MIT License. ... The GNU Image Manipulation Program, or GIMP, is a raster graphics editor application with some support for vector graphics. ... The BSD license is a permissive license and is one of the most widely used free software licenses. ... Python is a high-level programming language first released by Guido van Rossum in 1991. ... The correct title of this article is . ... The correct title of this article is . ... The BSD license is a permissive license and is one of the most widely used free software licenses. ... The GNU logo The GNU General Public License (GNU GPL or simply GPL) is a widely-used free software license, originally written by Richard Stallman for the GNU project. ... GNU logo The GNU Lesser General Public License (formerly the GNU Library General Public License) is a free software license published by the Free Software Foundation. ... The Debian Free Software Guidelines (DFSG) are a set of guidelines that the Debian Project uses to determine whether a software license is free software license, which in turn is used to determine whether a piece of software can be included in the main, free software distribution of Debian. ...

See also

This is a list of file formats used by archivers and compressors. ... It has been suggested that this article or section be merged into Comparison of file archivers. ... The following tables compare general and technical information for a number of file archivers. ...

External links

Data Compression Methods

v • d • e

Lossless compression methods

Theory

Entropy · Complexity · Redundancy

Entropy encoding

Huffman · Adaptive Huffman · Arithmetic (Shannon-Fano · Range) · Golomb · Exp-Golomb · Universal (Elias · Fibonacci)

Dictionary

LZ77/78 · LZW · LZO · DEFLATE · LZMA · LZX

Others

RLE · BWT · PPM · DMC

Audio compression methods

Theory

Convolution · Sampling · Nyquist–Shannon theorem

Audio codecs parts

LPC (LAR · LSP) · WLPC · CELP · ACELP · A-law · μ-law · MDCT · Fourier transform · Psychoacoustic model

Others

Dynamic range compression · Speech compression · Sub-band coding

Image compression methods

Terms

Color space · Pixel · Chroma subsampling · Compression artifact

Methods

RLE · Fractal · Wavelet · SPIHT · DCT · KLT

Others

Bit rate · Test images · PSNR quality measure · Quantization

Video compression

Terms

Video Characteristics · Frame · Frame types · Video quality

Video codec parts

Motion compensation · DCT · Quantization

Others

Video codecs · Rate distortion theory (CBR · ABR · VBR)

Timeline of information theory, data compression, and error-correcting codes

(See Compression Formats and Standards for formats and Compression Software Implementations for codecs) PKZIP is an archiving tool originally written by the late Phil Katz, and marketed by his company PKWARE, Inc. ... In computer science and information theory, data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes. ... Lossless data compression is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. ... A bundle of optical fiber. ... Claude Shannon In information theory, the Shannon entropy or information entropy is a measure of the uncertainty associated with a random variable. ... In computer science, the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity) of an object such as a piece of text is a measure of the computational resources needed to specify the object. ... Redundancy in information theory is the number of bits used to transmit a message minus the number of bits of actual information in the message. ... In information theory an entropy encoding is a data compression scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols. ... In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. ... Adaptive Huffman coding is an adaptive coding technique based on Huffman coding, building the code as the symbols are being transmitted, having no initial knowledge of source distribution, that allows one-pass encoding and adaptation to changing conditions in data. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ... In the field of data compression, Shannon-Fano coding is a technique for constructing a prefix code based on a set of symbols and their probabilities (estimated or measured). ... Range encoding is a form of arithmetic coding, a data compression method, that is believed to be free from arithmetic coding related patents. ... Golomb coding is a form of entropy encoding invented by Solomon W. Golomb that is optimal for alphabets following geometric distributions, that is, when small values are vastly more common than large values. ... An Exponential-Golomb code (or just Exp-Golomb code) of order is a type of universal code, parameterized by a whole number . ... In data compression, a universal code for integers is a prefix-free code that maps the positive integers onto self-delimiting binary codewords, with the additional property that whatever the true probability distribution on integers, the lengths of the codewords are within a constant factor of the lengths that the... Elias gamma code is a universal code encoding the positive integers. ... The Fibonacci code is a universal code which encodes positive integers into binary code words. ... A dictionary coder, also sometimes known as a substitution coder, is any of a number of data compression algorithms which operate by searching for matches between the text to be compressed and a set of strings contained in a data structure (called the dictionary) maintained by the encoder. ... LZ77 and LZ78 are the names for the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. ... LZW (Lempel-Ziv-Welch) is a lossless data compression algorithm. ... Lempel-Ziv-Oberhumer (LZO) is a data compression algorithm that is focused on decompression speed. ... Lempel-Ziv-Markov chain-Algorithm (LZMA) is a data compression algorithm in development since 1998 and used in the 7z format of the 7-Zip archiver. ... LZX is the name of an LZ77 family compression algorithm. ... Run-length encoding (RLE) is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. ... The Burrows-Wheeler transform (BWT, also called block-sorting compression), is an algorithm used in data compression techniques such as bzip2. ... PPM is an adaptive statistical data compression technique based on context modeling and prediction. ... Dynamic Markov Compression (DMC) is a lossless data compression algorithm developed by Gordon Cormack and Nigel Horspool [1]. It uses predictive arithmetic coding similar to prediction by partial matching (PPM), except that the input is predicted one bit at a time (rather than one byte at a time). ... Audio compression is a form of data compression designed to reduce the size of audio files. ... Acoustics is a branch of physics and is the study of sound (mechanical waves in gases, liquids, and solids). ... In mathematics and, in particular, functional analysis, convolution is a mathematical operator which takes two functions f and g and produces a third function that in a sense represents the amount of overlap between f and a reversed and translated version of g. ... In signal processing, sampling is the reduction of a continuous signal to a discrete signal. ... The Nyquistâ€“Shannon sampling theorem is a fundamental result in the field of information theory, in particular telecommunications and signal processing. ... An audio codec is a computer program that compresses/decompresses digital audio data according to a given audio file format or streaming audio format. ... It has been suggested that this article or section be merged with Code Excited Linear Prediction. ... Log Area Ratios (LAR) can be used to represent Reflection Coefficients (another from for Linear Prediction Coefficients) for transmission over a channel. ... Line Spectral Pairs (LSP) are used to represent Linear Prediction Coefficients (LPC) for transmission over a channel. ... Warped Linear Predictive Coding (Warped LPC or WLPC) is a variant of Linear predictive coding in which the spectral representation of the system is modified, for example by replacing the unit delays used in an LPC implementation with first-order allpass filters. ... CELP stands for Code Excited Linear Prediction and is a speech coding algorithm originally proposed by M.R. Schroeder and B.S. Atal in 1984. ... Algebraic Code Excited Linear Prediction or ACELP is a speech encoding algorithm where a limited set of pulses is distributed as excitation to linear prediction filter. ... Graph of Î¼-law & A-law algorithms An a-law algorithm is a standard companding algorithm, used in European digital communications systems to optimize, modify, the dynamic range of an analog signal for digitizing. ... In telecommunication, a mu-law algorithm (Î¼-law) is a standard analog signal compression or companding algorithm, used in digital communications systems of the North American and Japanese digital hierarchies, to optimize (in other words, modify) the dynamic range of an audio analog signal prior to digitizing. ... modified discrete cosine transform (MDCT) is a Fourier-related transform based on the type-IV discrete cosine transform (DCT-IV), with the additional property of being lapped: it is designed to be performed on consecutive blocks of a larger dataset, where subsequent blocks are overlapped so that the last half... In mathematics, the Fourier transform is a certain linear operator that maps functions to other functions. ... Psychoacoustics is the study of subjective human perception of sounds. ... Audio level compression, also called dynamic range compression, volume compression, compression, limiting, or DRC (often seen in DVD player settings) is a process that manipulates the dynamic range of an audio signal. ... Speech coding is the compression of speech (into a code) for transmission with speech codecs that use audio signal processing and speech processing techniques. ... Sub-band coding is any form of transform coding that breaks a signal into a number of different frequency bands and encodes each one independently. ... Image compression is the application of data compression on digital images. ... A comparison of different color spaces. ... This example shows an image with a portion greatly enlarged, in which the individual pixels are rendered as little squares and can easily be seen. ... In digital image processing, chroma subsampling is the use of lower resolution for the colour (chroma) information in an image than for the brightness (intensity or luma) information. ... A compression artifact (or artefact) is the result of an aggressive data compression scheme applied to an image, audio, or video that discards some data which is determined by an algorithm to be of lesser importance to the overall content but which is nonetheless discernible and objectionable to the user. ... Run-length encoding (RLE) is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. ... Fractal compression is a lossy compression method used to compress images using fractals. ... Wavelet compression is a form of data compression well suited for image compression (sometimes also video compression and audio compression). ... Set Partitioning in Hierarchical Trees (SPIHT) is an image compression algorithm that exploits the inherent similarities across subbands in a wavelet decomposition of an image. ... 2-D DCT compared to the DFT The discrete cosine transform (DCT) is a Fourier-related transform similar to the discrete Fourier transform (DFT), but using only real numbers. ... In statistics, principal components analysis (PCA) is a technique that can be used to simplify a dataset; more formally it is a linear transformation that chooses a new coordinate system for the data set such that the greatest variance by any projection of the data set comes to lie on... In telecommunications and computing, bit rate (sometimes written bitrate) is the frequency at which bits are passing a given (physical or metaphorical) point. It is quantified using the bit per second (bit/s) unit. ... In order to intuitively test the effects of an image-processing algorithm on a natural picture a number of test images are in common use in the image-processing field. ... The phrase peak signal-to-noise ratio, often abbreviated PSNR, is an engineering term for the ratio between the maximum possible power of a signal and the power of corrupting noise that affects the fidelity of its representation. ... Quantization, involved in image processing. ... Video compression refers to making a digital video signal use less data, without noticeably reducing the quality of the picture. ... This article does not cite any references or sources. ... It has been suggested that video frame be merged into this article or section. ... The three major picture types found in typical video compression designs are I(ntra) pictures, P(redicted) pictures, and B(i-predictive) pictures (or B(i-directional) pictures). ... Video quality is a characteristic of video passed through a video processing system. ... A video codec is a device or software module that enables video compression or decompression for digital video. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ... 2-D DCT compared to the DFT The discrete cosine transform (DCT) is a Fourier-related transform similar to the discrete Fourier transform (DFT), but using only real numbers. ... Quantized signal Digital signal In digital signal processing, quantization is the process of approximating a continuous range of values (or a very large set of possible discrete values) by a relatively-small set of discrete symbols or integer values. ... A video codec is a device or software module that enables video compression or decompression for digital video. ... Rate distortion theory is the branch of information theory addressing the problem of determining the minimal amount of entropy (or information) R that should be communicated over a channel such that the source (input signal) can be reconstructed at the receiver (output signal) with given distortion D. As such, rate... Constant bit rate (CBR) is a term used in telecommunications, relating to the quality of service. ... Average bit rate refers to the average amount of data transferred per second. ... Variable bit rate (VBR) is a term used in telecommunications and computing that relates to sound or video quality. ... A timeline of events related to information theory, data compression, error correcting codes and related subjects. ...

Contents

Using DEFLATE in new software GA_googleFillSlot("encyclopedia_square");

Stream format

Duplicate string elimination

Bit reduction

Encoder / Compressor

Encoder Implementations

Hardware Encoders

Decoder / Decompressor

INFLATE-only implementations

See also

External links

Using DEFLATE in new software