Transcription
Hi, I'm Andrew, and this talk is about the nuts and bolts of data compression. First, I'll cover some basic compression concepts, and then we'll see how these concepts are used in popular compression algorithms and how to select the right type of compression for your data. Hopefully, by the end of this talk, data compression will be much less of a magic black box. If you understand it better, you'll be able to use it more effectively, and maybe you'll even be inspired to develop a brilliant new compression algorithm.
I think compression is fascinating because it can be hard for humans to grasp. It's not really something that our brains are naturally wired to be good at, like sorting, searching, or extrapolating. It can be a little mysterious and intimidating since there's not a straightforward physical analogy for it, the way that the brain stores long-term memories compared to a short-term memory might be one example. It certainly seems like there's some compression that happens during that process, but we don't even fully understand how memory works. You might remember reading this if you can read it.
It's my user submission post for this talk. It turned out to be 569 bytes as a text file. I experimented with a few different compression algorithms and eventually found one that compressed it by almost half, down to 309 bytes. Just to illustrate that compression ratio, the red text is 309 bytes.
Now, suppose that you had the task of compressing this talk description by the same amount, but without using a computer. Well, one idea might be to just remove all the vowels. After doing that, someone might even be able to reconstruct the original text without too much pain, and that compresses it by 29%, but it's still 42 bytes, and we still have 93 bytes left to trim out. So, the next step could be to remove all spaces and punctuation, except for that one lone asterisk. And that actually does reduce it to exactly 309 bytes, the same as the maximum compression ratio that I could get. But it's probably not decodable back to the original text now, unless you're an expert code breaker.
So, the first half of this talk will be about the science of compression, and then I'll talk about some practical applications. But before we start, here are some relatively strong statements that I stumbled upon: Compression is machine learning. Compression is equivalent to intelligence. Consciousness is compression. Just some food for thought.
Compression starts with identifying patterns. Patterns are everywhere. The chairs in this room are identical, and they're arranged in a particular fashion. The people in this room graduated from lots of different universities, but some are more common than others, like KU and Iowa State. Others are less common, like MIT. Almost all data is highly redundant. It contains patterns. It contains repetition. If there were no patterns at all, the data would be random and essentially meaningless. But true randomness is rare. Data usually has a limited alphabet of symbols and it tends to repeat itself, or it might describe reality in a way that, given the past history of some data set, we can predict what the next value is going to be, or at least anticipate a likely range of possibilities. So, as Occam's Razor says, the simplest theory that explains the past is the best predictor for future events.
It's obviously useful to simplify your data from its original form to a more concise representation. We want to eliminate as much of the redundancy as possible. By compressing data, we can consume less disk space, and that allows us to store more data. And we can also transmit fewer bytes across networks, which is faster and saves bandwidth capacity.
There's something in information theory called Kolmogorov complexity, and this is a measure of the computation resources that are needed to describe an object. So, consider this string of text. It contains 21 characters, but it's just ABC repeated seven times. You can see that. Here's another string. It's 21 characters again, and there is a clear pattern. It's certainly more complex than that first string. One more example. With this one, there's no obvious way to describe it in any simpler way than the string itself, so it would rank the highest on that Kolmogorov complexity scale.
There are two basic types of compression that I'll talk about: lossy and lossless. With lossless compression, an identical copy of the data can be reconstructed byte for byte from the compressed form. And the main thing that lossless compression has to determine is what's redundant in the data, or if the element of time is involved, what has not changed about the data since the last time that we encountered it. It's a deterministic and reversible transformation.
On the other hand, lossy compression. Lossy compression's transformation of data is a one-way street. The original form of the data is lost. It's gone forever, and the decompressed version is just an approximate imitation of the original. The main thing that lossy compression has to determine is what's non-essential about the data. In other words, it has to figure out what's most important. That can be very subjective, of course, and there's no clear correct answer to these questions.
So, before considering compression at all, you should keep in mind that all digitized representations of our physical world have already lost almost all of their original fidelity. In comparison to microscopic particles and nanometers, we're never going to be able to capture video, image, and audio data at perfect infinite resolution. Our three-dimensional world has been flattened out into images and videos, and time gets arbitrarily sliced up into video frames. Also, sound gets arranged into stereo or surround channels.
Lossy compression combines the science of data with the science of perception. So, it can be more challenging to implement than lossless compression, since the perceptual quality of the decompressed representation actually matters, not just the compression ratio or how long it takes to compress the data.
Lossy audio compression algorithms are based on how we hear sound, of course. Here's an image of the raw audio data for a song, and if we compress that audio using the popular Free Lossless Audio Codec, or FLAC, then we can reduce its size by 45%. However, compressing it to an MP3 results in a much smaller size while essentially maintaining full perceived quality for that song. And even at a really high quality level of 256 kilobits per second, that raw wave data can be compressed lossy by 82%.
Images like this cat picture are also very commonly compressed by lossy algorithms. So, here's an example of JPEG image compression, starting with a quality level of 100 and an original file size of 1.6 megabytes. So, if we reduce the quality down to 90, it's already less than half of that original size, and we can keep reducing the quality further and further without any noticeable difference. So, let's stop here at a quality level of 30. It's now less than 10% of the original size, but the differences are still almost imperceptible. You can't really tell. If we keep reducing the quality further, compression artifacts eventually start to show up. At zero quality, it's less than 3% of the original size now, and zero quality is not really practical unless you want to create glitch art.
Like audio and image compression, video compression is everywhere. It's essential for fast transmission and storage of video content. If you've watched movies on Netflix, YouTube videos, or if you use a DVR, you've probably seen really convincing evidence through compression artifacts from time to time when the video stream gets corrupted.
Downsampling or bit rate reduction is an irreversible transformation that's commonly used in lossy compression. Two common downsampling techniques are aggregation and quantization. So, suppose that we have these four values, but for some reason, we can't afford to store them all, at least not at two decimal places of precision. Aggregation means combining the data values into a smaller number of values. This can be an average or some other function. Quantization, on the other hand, is essentially rounding or truncating, using fewer bits to represent the values, and so there's a loss of precision or fidelity. Quantization can be non-uniform, based on perception. For example, the human eye is more sensitive to certain colors than others, so the granularity could be flexible to account for that. Maybe we want nearest tenth precision for values less than seven, but maybe we want nearest odd integer precision for values that are greater than seven. And of course, these techniques are not mutually exclusive. We could first aggregate the values and then quantize them.
Source code minification is sort of a hybrid between lossy and lossless compression. It's not reversible, but it is functionally equivalent to the original code. So, the only thing that's lost is human readability. As you can see from this snippet of code, minification removes the whitespace and it makes variable names as short as possible. If you didn't get a chance to check out Michelle Brush's talk yesterday, you should check that out. It has some interesting stuff along these same lines.
Okay, so now we'll jump back over to the lossless compression side of the fence. And first, it's important to recognize that lossless compression is never guaranteed. We need to set some expectations. If we could always reduce the size of a file by compressing it, then we could just keep repeating that compression over and over until nothing is left, and then obviously, it would be impossible to reconstruct the original file. But we can actually make a stronger statement than that. Less than 1% of all possible files can be reduced in size by lossless compression techniques. Here's the math behind that. When you compress a file, that can be viewed as a one-to-one mapping of the file to a different and hopefully smaller file. So, compression of at least one bit means mapping a file of N bytes to a file of N minus one or fewer bytes. And it's clear that there's less than a 1% opportunity for such mappings to exist.
Encoding schemes are sort of the building blocks for lossless compression. Run-length encoding is one useful scheme. It replaces repeated occurrences or runs of the same data value with a value and count pair. So, here's a string that would be ideal to run-length encode. It begins with three consecutive A's, next there's a single B, followed by five C's, 8 B's, 14 A's, and five more C's. Run-length encoding is useful for data that contains many such runs, but it's not useful for data in which values aren't frequently repeated. Run-length encoding is common in some older image formats, like those used by photocopy and fax machines.
Another basic encoding scheme is called delta encoding, and it computes the relative differences between sequential data values. So, this sequence of numbers can be efficiently represented by delta encoding. The first value is just preserved as is, and then for each subsequent value, we calculate the difference. So, 1002 is 1000 plus 2. 13 is 10 plus 3. 10 is 10 plus 0. 6 is 10 minus 4. 10 is 6 plus 4. Delta encoding is great for sequences of closely clustered or naturally similar values, for example, hourly temperature measurements. The deltas could be further run-length encoded if values are repeated many times in a row, or if there are arithmetic sequences in the data, like 1, 2, 3, 4, 5, 6, 7, so that the differences or deltas are constantly the same.
Given the delta encoded values, it's easy to see how you would reconstruct the original sequence. Differential compression is a lot like delta encoding, but it's across multiple generations of a complex collection of data. One great example of differential compression is the Chrome auto-update system, codenamed Corette, which only sends the difference in executable code when a new version of Chrome gets installed. And as you can see from these stats that Google published, intelligent differential compression reduced the size of a Chrome update to less than 1% of its full size, and that's really awesome. Git commits and packs are also examples of differential compression. The git repack command combines unpacked objects in a repository into a pack, and it can also be used to reorganize an existing pack into a single and more efficient pack using differential compression. And these techniques are also commonly used when compressing video data. Consecutive frames of a video will usually be very similar, making differential compression quite effective. So, as you can see, the green ground line is the same in all frames of this short video loop, so we only need to store it once for the first frame. And the same thing applies to the position and shape of the bouncing red ball.
A third type of encoding is dictionary encoding, and the simplest example of this would be a dictionary that just contains all of the individual data symbols that are encountered. So, we add each symbol into the dictionary the first time that we see it. Our example word is Abracadabra, and the first symbol is A. So, add it to the dictionary and just assign it a value of one. The next symbol is B. We add it, assign it a value of two. R is three, and A is already in the dictionary. Its value is one, so just add that to the output. C is four, and so on, until we're done. The dictionary is usually much more complex than this example. They can be used to keep track of common repeating strings. For example, Abra occurs twice, so it's easy to see how we can use a dictionary to compress the output.
Entropy encoding assigns a unique code to each unique symbol in the input, like that first simple dictionary example. But with entropy encoding, the length of each code is approximately proportional to the negative logarithm of the corresponding symbol's frequency, so that the most common symbols have the shortest codes. Morse code is conceptually similar to entropy encoding. It was developed by Samuel Morse in the 1840s. Here are the Morse codes for each of the 26 letters in our alphabet. As you can see, shorter codes are assigned to letters that are more frequently used, and longer codes are assigned to less frequently used letters. Of course, the most famous Morse code is SOS, and it's actually a special code that's assigned to the entire word.
One popular type of actual entropy coding is Huffman coding. It was discovered in 1952 by David Huffman, a PhD student at MIT. So, let's just work through an example. First step in Huffman coding is to count the frequency of each symbol. So, there are five A's, two B's, two R's, one C, and one D. Then we set these as the frequencies of the leaf nodes of a binary tree. And the next step is to find the two nodes that have the lowest value that do not have a parent. So, that would be C and D. Then we create a parent node for them and assign it the sum of the children's values. One plus one is two. Then we find the next two parentless nodes with the lowest values. We can pick B and R, add a parent, assign it the sum, which is four. The next two lowest are two and four. Combine them, assign the sum, which is six. And then the last two nodes without a parent are five and six. We combine them, and the sum is 11. So, our tree now has a root node, and so we're done. And we can clear out the numeric values now because we don't need them anymore. Then we label the links in this binary tree in the standard way. The left child is zero, and the right child is one. Then we just trace down from the root to each leaf node to get the code for each symbol. So, the code for C is 0000. D is 001. B is 010. R is 011, and A is just one. So, note that no code is a prefix of any other code, and that's an important property that allows us to have a compact encoding. Then we use these codes to encode the input. Code for A is one, B is 010, R is 011, and so on, until we've encoded the entire string. So, here's the Huffman coding for Abracadabra. And note that we also need to include that binary code tree along with the output.
And so, how would we transform it back? We have our codes and we have our encoded data stream, and we just scan over the data stream bit by bit until we find a code that matches. So, one matches A. Zero is ambiguous. Keep scanning. 01 is still ambiguous, but 010 matches B. So, we know that that's the next symbol. 011 matches R. One is A again. 00 is C, and so on, until we've decoded the entire data, and we're done.
Another category of encoding uses interesting transformations to transform data into a more compressible form, rather than intending to reduce its size necessarily. Transformers can have an important role in some compression algorithms. One awesome transformer is the Burrows-Wheeler Transform, and here's how it works. So, given the input of Abracadabra, we're going to build a matrix of all possible rotations of this string. So, building a matrix. Okay, we've built our matrix, and then we're going to sort the matrix. So, we find the smallest value, move it to the top, and now it's magically sorted. We can see that the first column naturally has the most repetition due to the sorting, and the last column is especially interesting. So, it turns out that the repetition in this column is proportional to the amount of compressible redundancy in the data. We keep this last column as the output of the transform and just discard all of the others. But we also do need to remember the row number of the original input, that would be row three for this example. So, the Burrows-Wheeler Transform for Abracadabra gives us R D R C A A A B B, and row three.
So, how do we transform it back? It's not really obvious. The first step is to assign an index to each symbol. Next, we sort by the symbol value. So, lowest symbol is A. Move it to the top and sort the rest, and that would look like this. But we keep the original indexes associated with the symbols. And then we assign fresh indexes to those sorted symbols. And starting with the original row index from the transform, which was row three, we see that it's mapped to the symbol A. So, we know that that's the first letter. And then we just jump to the symbol's original index from before they were sorted to get to the next symbol. So, that sends us to index seven, which is mapped to B, and we just keep following the links. 11 is mapped to R, four is mapped to A, eight is C, and so on, until we're back to the value that we started from, three, and that's how we know that we're done. So, as you can see, it's certainly possible to reverse that transform, but it requires a little cleverness.
Another simple but effective transformer is the Move-to-Front Transform. Here's how this transform works. So, we have our now very familiar input data, Abracadabra, and also an array containing the alphabet of all symbols that are possible in the input. We record the position of each symbol in the alphabet and then we move it to the front of the alphabet. So, A is at position one, and it's already at the front, so we don't need to move it. B is at position two, and then move it to the front. R is all the way over at position 18, move it to the front. A is now at position three, so we record that, move A back to the front. C's at position four, move it to the front, and so on, until we've transformed the entire word. So, the Move-to-Front Transform gives us this particular sequence of values. As you can see, this could be helpful for further compression if there are certain patterns or frequently used letters in your data.
So, how would we transform it back? Reversing this transformation is actually a symmetric process. So, we just start with the same alphabet and repeat the process, basically reading the symbol at each position instead of getting the position for a symbol. So, at position one in the alphabet is the symbol A, and it's already at the front. At position two is B, move B to the front. R is at position 18, move R to the front. The symbol at position three is A, now move A to the front, and so on, until we've reversed the transformation. So, it's fairly straightforward and simple, but it has some really useful applications.
All right, so that was a quick tour of the science of compression. And now I'll cover a few practical applications of those concepts.
In 1977, Abraham Lempel and Jacob Ziv designed a dictionary-based lossless data compression algorithm, and that became known as LZ77. As you can see, there are many compression algorithms in the LZ family. One of the most noteworthy ones is called Deflate. It was developed in 1993, and it's over 20 years old, but it's still very heavily used today. Deflate combines LZ77 with Huffman coding. The commonly used Zlib library implements Deflate, and so does the gzip Unix application. It's normally used to compress single files, but a common usage of gzip is compressing a tar archive, where all files are concatenated together and compressed as a single block. This is called solid compression. If you have a lot of similar files, compressing them all together as a batch can be much more effective and efficient than compressing each file individually.
The Snappy algorithm was developed at Google and open-sourced in 2011. Snappy was designed to be as fast as possible. It's an order of magnitude faster than Deflate for most data, and to keep it as fast as possible, it does not do any entropy encoding. The raw symbols in the data are written to the output stream. Its goal is just moderate compression, but at very high speed. It might only compress half as much as Deflate in some cases, but that's considered good enough. My team uses Snappy for data in the Hadoop file system and also in Kafka messages.
There are many, many more compression algorithms that I could talk about, and here are just a few of the interesting ones. First is bzip2. It uses several of the techniques covered in this talk: run-length encoding, the Burrows-Wheeler Transform, move-to-front transform, and Huffman coding. It's a very good general-purpose lossless compression algorithm, but not as widely used as others. It can produce a better compression ratio, especially for structured text like JSON or source code, but at the expense of higher memory and more CPU consumption.
Prediction by Partial Matching guesses what the next symbol in the data is going to be based on statistical probabilities. It's excellent for natural language text, but it requires a lot of memory and it can be relatively slow as well. A popular variant called PPMd is actually what I used to compress the description of this talk to 309 bytes.
The PAQ family uses an extremely complex combination of probability estimates to achieve very excellent compression. It's innovative, but not really practical, just because it's slow.
HTTP compression is also something you should be aware of. It's important to the overall health of the internet. It uses bandwidth more efficiently, results in faster data transmission, of course. The Content-Encoding header specifies the compression method that's used for data being sent, and the Accept-Encoding header is used to specify the compression capabilities of your client. The latest Chrome browser for iOS and Android has an option for using a compression proxy server in Google's data centers for all non-HTTPS traffic. These proxy servers minify the HTML, JavaScript, and CSS content before compressing it and then sending it to your mobile device. And they also transcode all images to the new WebP format that Google introduced.
99% of the time, compression is beneficial, and you do want to use it. However, there are a handful of situations where it's not a good idea. The first reason is if the data is substantially random, which means that all data symbols are more or less equally likely to occur, so that the next value is consistently unpredictable. However, if your symbol set is limited, compression will generally help. And here are a few examples to illustrate this. If you have a file containing a random mix of the letters A and B, it will actually compress extremely well, around 85%. If you add a third letter to that random mixture, the compression ratio decreases, but it's still pretty good, 76%. A random file of the digits zero through nine compressed down to just under half of the original size. A random file of all 26 lowercase characters compressed by 36%. And with all uppercase and lowercase letters plus the digits zero through nine, the compression ratio was decreased, and it's only about 25% now. Finally, if your data is truly random bytes, ones and zeros, it will be completely incompressible unless you are extremely lucky. So, true random data, as I mentioned, is rarely encountered in the real world.
However, data that has already been compressed by some sort of compression typically looks substantially random. So, here are just a few examples of this. If you have an MP3 file and try to zip it, it won't compress much at all. And the same thing applies to a losslessly compressed FLAC audio file. JPEG images don't compress much, and neither do PNG screenshot files, because it already uses compression internally. The same thing applies for movie or video files, and data that has already been compressed generally can't be compressed much further, if at all, because all the juice has already been squeezed out, and so there's no more juice left to squeeze.
Proper encryption should remove any traces of recognizable patterns from the data so that it ends up looking very random. And I verified that by trying to compress an encrypted file and saw that there was no deflation. However, compressing data before you encrypt it can be beneficial and is usually recommended, so your encryption runs faster.
Another type of data that looks very random is raw audio, image, or video data. It's generally not compressible if you don't have a media-specific lossy codec. Given the high precision of modern recording equipment, there's a lot of noise or random natural variations in the data signal. So, here's an example of that. Attempting to zip a WAV file only compressed by 5%. And the same thing applies to raw image and video data. DNG, if you're not familiar with it, is a raw digital negative file format.
There's a practical minimum size for all compression algorithms. If you only have a tiny amount of data, trying to compress it may be counterproductive. Examples of this might be a single integer or a person's name. In this case, you would want to either compress many small items together as a batch or just avoid using compression.
And another reason to possibly avoid compression is if you don't have any tolerance whatsoever for increasing the size of your data. I've seen at least one defect that occurred when the compressed size was unexpectedly larger than the original size. Most algorithms actually do specify a worst-case inflation amount for incompressible data.
Another reason is severe system resource constraints. Usually not a valid reason, because any sort of compression will make subsequent IO faster and offset the compression overhead.
A final possible reason is unintentional disclosure of confidential information. And that's because compressing data can reveal patterns.
That brings us to the final application of compression for this talk, which is BREACH attacks. BREACH is a category of vulnerabilities that came to light last year at the Black Hat security conference. This attack works against all versions of SSL. There's nothing that stops attackers from seeing the size of an encrypted payload. If your website meets certain conditions, you might be vulnerable. So, you need to be using compression. The response page needs to reflect user input. And finally, the response needs to contain a secret. That can be any sort of sensitive data, such as Social Security numbers, email addresses, password reset links. So, it starts with a blind guess. If that guess is correct, then the encrypted message size would be smaller than it would be for an incorrect guess. That's because the response contains both the guess and the secret. So, an example initial guess might be the suffix of an email address, for example, @gmail.com. So, once that's found, then that guess is just expanded letter by letter until the full secret is finally revealed. And there's no clean and complete solution to the problem. There are some mitigations. Disabling compression works, but not very practical. Changing your pages to separate display of secrets from echoed user input is a good idea. Most websites already list only the last four digits of credit card numbers, and BREACH may force them to truncate other sensitive strings. You could add random padding to your responses so that attackers can't easily evaluate the success or failure of their guesses. And finally, rate limiting requests could help also, since BREACH requires several requests to expose those secrets.
So, here are some bonus links to some related topics that I didn't think I could cover in this talk without running out of time and confirm that, but they're really cool, so check them out. And in case you're curious, this presentation could unfortunately only be compressed by 4% because it contains a lot of images. So, please remember to submit your feedback. Thank you.
[Applause]