데이터 압축의 모든 것: 원리부터 최적화까지

Data Compression Explained Matt Mahoney Copyright (C) 2010-2012, Dell, Inc . You are permitted to copy and distribute material from this book provided (1) any material you distribute includes this license, (2) the material is not modified, and (3) you do not charge a fee or require any other considerations for copies or for any works that incorporate material from this book. These restrictions do not apply to normal "fair use", defined as cited quotations totaling less than one page. This book may be downloaded without charge from http://mattmahoney.net/dc/dce.html . Last update: Apr. 15, 2013. e-reader translations by Alejo Sanchez, Oct. 29, 2011: mobi (Kindle) and epub (other readers). About this Book This book is for the reader who wants to understand how data compression works, or who wants to write data compression software. Prior programming ability and some math skills will be needed. Specific topics include: 1. Information theory No universal compression Coding is bounded Modeling is not computable Compression is an artificial intelligence problem 2. Benchmarks Calgary corpus results 3. Coding Huffman arithmetic asymmetric binary numeric codes ( unary , Rice, Golomb , extra bit ) archive formats ( error detection , encryption ) 4. Modeling Fixed order : bytewise bitwise , indirect Variable order : DMC , PPM , CTW Context mixing : linear mixing , logistic mixing , SSE , indirect SSE , match , PAQ , ZPAQ , Crinkler 5. Transforms RLE LZ77 ( LZSS , deflate , LZMA , LZX , ROLZ, LZP , snappy , deduplication ) LZW and dictionary encoding Symbol ranking BWT ( context sorting , inverse , bzip2 , BBB , MSufSort v2 and v3 , Itoh-Tanaka , DivSufSort , Bijective ) Predictive filtering ( delta coding , color transform , linear filtering ) Specialized transforms ( E8E9 , precomp ) Huffman pre-coding 6. Lossy compression Images ( BMP , GIF , PNG , TIFF , JPEG ) JPEG recompression ( Stuffit , PAQ , WinZIP PackJPG ) Video ( NTSC , MPEG ) Audio (CD, MP3, AAC, Dolby, Vorbis) Conclusion Acknowledgements References This book is intended to be self contained. Sources are linked when appropriate, but you don't need to click on them to understand the material. 1. Information Theory Data compression is the art of reducing the number of bits needed to store or transmit data. Compression can be either lossless or lossy. Losslessly compressed data can be decompressed to exactly its original value. An example is 1848 Morse Code . Each letter of the alphabet is coded as a sequence of dots and dashes. The most common letters in English like E and T receive the shortest codes. The least common like J, Q, X, and Z are assigned the longest codes. All data compression algorithms consist of at least a model and a coder (with optional preprocessing transforms). A model estimates the probability distribution (E is more common than Z). The coder assigns shorter codes to the more likely symbols. There are efficient and optimal solutions to the coding problem. However, optimal modeling has been proven not computable. Modeling (or equivalently, prediction) is both an artificial intelligence (AI) problem and an art. Lossy compression discards "unimportant" data, for example, details of an image or audio clip that are not perceptible to the eye or ear. An example is the 1953 NTSC standard for broadcast color TV, used until 2009. The human eye is less sensitive to fine detail between colors of equal brightness (like red and green) than it is to brightness (black and white). Thus, the color signal is transmitted with less resolution over a narrower frequency band than the monochrome signal. Lossy compression consists of a transform to separate important from unimportant data, followed by lossless compression of the important part and discarding the rest. The transform is an AI problem because it requires understanding what the human brain can and cannot perceive. Information theory places hard limits on what can and cannot be compressed losslessly, and by how much: There is no such thing as a "universal" compression algorithm that is guaranteed to compress any input, or even any input above a certain size. In particular, it is not possible to compress random data or compress recursively. Given a model (probability distribution) of your input data, the best you can do is code symbols with probability p using log 2 1/p bits. Efficient and optimal codes are known. Data has a universal but uncomputable probability distribution. Specifically, any string x has probability (about) 2 -|M| where M is the shortest possible description of x, and |M| is the length of M in bits, almost independent of the language in which M is written. However there is no general procedure for finding M or even estimating |M| in any language. There is no algorithm that tests for randomness or tells you whether a string can be compressed any further. 1.1. No Universal Compression This is proved by the counting argument . Suppose there were a compression algorithm that could compress all strings of at least a certain size, say, n bits. There are exactly 2 n different binary strings of length n. A universal compressor would have to encode each input differently. Otherwise, if two inputs compressed to the same output, then the decompresser would not be able to decompress that output correctly. However there are only 2 n - 1 binary strings shorter than n bits. In fact, the vast majority of strings cannot be compressed by very much. The fraction of strings that can be compressed from n bits to m bits is at most 2 m - n . For example, less than 0.4% of strings can be compressed by one byte. Every compressor that can compress any input must also expand some of its input. However, the expansion never needs to be more than one symbol. Any compression algorithm can be modified by adding one bit to indicate that the rest of the data is stored uncompressed. The counting argument applies to systems that would recursively compress their own output. In general, compressed data appears random to the algorithm that compressed it so that it cannot be compressed again. 1.2. Coding is Bounded Suppose we wish to compress the digits of π, e.g. "314159265358979323846264...". Assume our model is that each digit occurs with probability 0.1, independent of any other digits. Consider 3 possible binary codes: Digit BCD Huffman Binary ---- ---- ---- ---- 0 0000 000 0 1 0001 001 1 2 0010 010 10 3 0011 011 11 4 0100 100 100 5 0101 101 101 6 0110 1100 110 7 0111 1101 111 8 1000 1110 1000 9 1001 1111 1001 --- ---- ---- ---- bpc 4.0 3.4 not valid Using a BCD (binary coded decimal) code, π would be encoded as 0011 0001 0100 0001 0101... (Spaces are shown for readability only). The compression ratio is 4 bits per character (4 bpc). If the input was ASCII text, the output would be compressed 50%. The decompresser would decode the data by dividing it into 4 bit strings. The Huffman code would code π as 011 001 100 001 101 1111... The decoder would read bits one at a time and decode a digit as soon as it found a match in the table (after either 3 or 4 bits). The code is uniquely decodable because no code is a prefix of any other code. The compression ratio is 3.4 bpc. The binary code is not uniquely decodable. For example, 111 could be decoded as 7 or 31 or 13 or 111. There are better codes than the Huffman code given above. For example, we could assign Huffman codes to pairs of digits. There are 100 pairs each with probability 0.01. We could assign 6 bit codes (000000 through 011011) to 00 through 27, and 7 bits (0111000 through 1111111) to 28 through 99. The average code length is 6.72 bits per pair of digits, or 3.36 bpc. Similarly, coding groups of 3 digits using 9 or 10 bits would yield 3.3253 bpc. Shannon and Weaver (1949) proved that the best you can do for a symbol with probability p is assign a code of length log 2 1/p. In this example, log 2 1/0.1 = 3.3219 bpc. Shannon defined the expected information content or equivocation (now called