|
In computing, deflate is a 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. The original algorithm as designed by Katz was patented as and assigned to PKWARE, Inc. As stated in the RFC document, Deflate is widely thought to be implementable in a manner not covered by patents.〔 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: * 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/raw/literal section, 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.The ''stored'' block option adds minimal overhead, and is used for data that is incompressible. Most compressible 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 * The matching and replacement of duplicate strings with pointers. * Replacing symbols with new, weighted symbols based on frequency of use. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「deflate」の詳細全文を読む スポンサード リンク
|