Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Deflate
Résumé
In computing, Deflate (stylized as DEFLATE) is a lossless data compression that uses a combination of LZ77 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).
Katz also designed the original algorithm used to construct Deflate streams. This algorithm was patented as , and assigned to PKWARE, Inc. As stated in the RFC document, an algorithm producing Deflate files was widely thought to be implementable in a manner not covered by patents. This led to its widespread use – for example, in gzip compressed files and PNG image files, in addition to the file format for which Katz originally designed it. The patent has since expired.
A Deflate stream consists of a series of blocks. Each block is preceded by a 3-bit header:
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 dynamic Huffman 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.
Most compressible data will end up being encoded using method 10, the dynamic Huffman encoding, which produces an optimized Huffman tree customized 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:
The matching and replacement of duplicate strings with pointers.
Replacing symbols with new, weighted symbols based on the frequency of use.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.