16 ms·
The Elegance of Deflate
- xxs 10y agoThe article mentions LZW. In terms of algorithm elegance LZW should be head and shoulders above 'deflate'. LZW got patented which (aside gifs) screwed up its popularity. 'defalte' allows custom dictionaries that adds some extra complexity. I'd strongly disagree with In many people's eyes compression was still synonymous with run-length encoding as arj was extremely popular to the point it was used to cure full stealth viruses (v512 for example). hard to provide references now but wiling to search some old bbs Other than that - fairy nice/nostalgic article.
- gpvos 10y agoI very recently had to look at an LZW decoder, and it is indeed more elegant than Deflate as described here. However, LZW doesn't have a Huffman post-encoding step, so it does not compress as well as Deflate.
- beagle3 10y agoAsymptotically it doesn't matter - that's the genius of all LZ schemes (LZ77 =~ LZSS, LZ78 =~ LZW). All the other details just take care of the early pre asymptotic stage.
- TD-Linux 10y agoNo, it still does - LZW assumes flat probabilities for each entry in its dictionary. After a while, both the encoder and decoder will know more accurate probabilities, but LZW has no way to take advantage of that.
- beagle3 10y agoBut asymptotically it doesn't matter because the LZ78/LZW code words represent longer and longer sequences, with the more probable sequences getting shorter codes. The additional letter (per each code word, in the case of LZ78) doesn't matter asymptotically. Practically, of course, it does.
- gpvos 10y agoHow do the more probable sequences get shorter codes?
- beagle3 10y agoThat's basically the objective of every compression algorithm. Huffman coding does it directly by construction, Lempel Ziv do it indirectly - in LZ78/LZW, you get essentially and asymptotically (though randomly, per individual sequence) code length proportional to log_2 prob(sequence), because the sequences added to the dictionary are added by order of probability. In LZ77/LZSS, it is basically the same, except the dictionary is not constructed explicitly but rather implicitly from the history. In both cases, you need to refer to Lempel and Ziv's proof that indeed, the codeword length converges to log_2 P(sequence), which is optimal by the Shannon Source Code Theorem. I highly recommend Cover & Thomas book on information theory if you find that interesting and are not afraid of math. And Shannon's original 1949 paper ("A theory of communication") is surprisingly and exceptionally readable - though it doesn't cover LZ for obvious reasons.
- gpvos 10y agoOkay, so it's because the most probable sequences are more likely to be encountered first, which assumes the data is more or less uniform. (I.e., it doesn't work as well when the data starts with a large blob of random data, and the more regular data comes afterwards. But I guess that's true for most general compression algorithms. At least LZW has a reset code.) I'll see if I can find the C&T book. Shannon's paper was part of the course material at uni, IIRC; at least I think I read it long ago.
- beagle3 10y agoIt's not just a matter of encountered first, it's of encountered more often ("encountered first" is a special case of "more often"). But you really need to delve into the proof to figure out why that's enough for optimality. At the very least, _I personally_ don't know of a simple intuitive way to explain that. It is important to remember what each compression algorithm is optimal for. LZ77 and LZ78 are optimal for observable markov sources -- that is, sources in which given x recent consecutive outputs (where x is the markov order), the distribution of the next symbol is fixed. While this is rarely ever the case, it is reasonable to assume that e.g. English text is a 10-th order markov model (with respect to characters) or 3-rd order (with respect to words). The source you described is NOT markov overall, although it might be markov in the tail (past the random blob). Asymptotically, of course, it is markov :)
- eps 10y agoarj ... daaamn. That brings back some sweet memories to the soundtrack of a modem handshake whistle. Good thing we still have Norton Commander in a form of Far Manager to show some of the past glory to youngsters :)
- brian-armstrong 10y agoI really enjoyed this article. It's just enough detail to leave you thinking, "Hey, I should write my own DEFLATE library"
- bbcbasic 10y agoWould be fun to do that in Haskell Edit: https://github.com/GaloisInc/pure-zlib?files=1 https://github.com/GaloisInc/pure-zlib?files=1. Beautiful they've done just the decompression! Challenge awaits
- xxs 10y ago>>"Hey, I should write my own DEFLATE library" Did that in Java (2011) and the impl. was faster than the native one (party due to lack of proper customization of zlib from java code)
- banachtarski 10y agoUsing additional bits to encode lengths isn't really that different from having a marker indicating if the payload is a match vector or not. In fact, it could be argued to be less efficient for certain types of data depending on the huffman distribution since all "words" are larger than a byte. It also prevents you from encoding longer matches. I treat the decision as a compromise between the two extremes that "worked" for the majority of types of data "good enough" for some definition of both quoted words. The entire idea works well enough but I wouldn't go out of the way to declare it a marvel of engineering or anything.
- HisGraceTheDuck 10y ago"it could be argued to be less efficient for certain types of data" This is true of all lossless compression.
- banachtarski 10y agoYou're invoking a stronger "technically correct" interpretation of the statement I'm making. Let me qualify. In a blob with many short repeated sequences, the algorithm as presented is better. In a blob with many long repeated sequences, a marking bit is better. Honestly, neither example is that farfetched.
- brian-armstrong 10y agoThis comment shows a baffling level of arrogance. And it can hardly be considered a happy accident, compression methods are tested against real corpuses
- banachtarski 10y agoI never said happy accident. Like most algorithms (the reallocation size of a vector when it reaches capacity, the widths of slots in a timer wheel, the hierarchical sizes of a generational gc, etc.) the "correct" answer is determined experimentally. My point is that the choice of encoding small lengths is just a decision, like every other decision and is no more or less elegant than encoding a payload determining marking bit, and shouldn't be celebrated independently. Calling me "bafflingly arrogant" though is a bit perplexing. Can we disagree without resorting to petty jabs at character?
- flohofwoe 10y agoAnyone know what's the history behind that setjmp/longjmp as 'poor man's exception' error handling? Since C works perfectly fine without exceptions, why add such a hack? I've seen this in libpng and I think libjpeg has it too (one of many reasons I'm avoiding those libs).
- searealist 10y agoYou don't have to use setjmp/longjmp in libpng, it's just the default behavior. You can instead set an error callback to do whatever you want.
- johncolanduoni 10y agoC lacks "zero-cost" exceptions, where the code should be just as fast as it would be if no exceptions were involved as long as one isn't thrown. Although they are much more expensive when thrown than checking a return value and using indirection for any logical return values, they are a bit cheaper when you don't expect the exception to happen very often, or don't care about performance if it does (e.g. a corrupt png or jpeg file). My dream is something like the UX of Swift's exceptions (basically normal C error handling except for it does all the tedious pointer work for you) with the ability to tell the compiler to either implement the exceptions as return values or stack unwinds for a particular code path with the flick of a switch.
- vog 10y agoMy big hope in this regard is Rust, which has a very good track record if implementing good, usable, zero-cost abstractions. If they manage to implement zero-cost futures [1][2], maybe they will also implement sime kind of zero-cost error handling abstraction (either via exceptions, or via some other useful abstraction for that purpose). [1] https://aturon.github.io/blog/2016/08/11/futures/ https://aturon.github.io/blog/2016/08/11/futures/ [2] https://news.ycombinator.com/item?id=12268988 https://news.ycombinator.com/item?id=12268988
- barrkel 10y agoRust's abstractions are only zero cost if you're looking in the wrong place for your costs. The Result / try! stuff in particular I would be very surprised if it is faster than a good exception approach, for example, particularly the happy path. It's amortised throughout though, while different exception throwing mechanisms have dramatically different performance, so people's intuitions aren't reliable. I like Rust a lot. Zero costs is not a reason though; my reason is no GC and not as bad as C or C++.
- Jasper_ 10y agoI wouldn't say that entropy coding is "separate" from dictionary / window compression. DEFLATE surely isn't the first algorithm to combine LZ77 and some form of entropy coding, and surely won't be the last. I highly recommend that everybody go out and build an INFLATE implementation; it's a lot of fun. Mine can be found at https://github.com/magcius/libt2/blob/master/t2_inflate.h https://github.com/magcius/libt2/blob/master/t2_inflate.h
- dunham 10y agoI did this in javascript years ago (I had done snappy first, but wanted smaller data). It's fun and not too difficult. The deflate side seems a little more complex. I played with it while on vacation about a month ago, but stalled after doing the LZ77 and huffman table generation, because I really just wanted to learn on the LZ77 bits worked, and I don't actually have a project that needs it.
- Dylan16807 10y agoIt's a good system. Though the full DEFLATE spec has quirks like storing literal blocks prefixed by their length and then the ones complement of their length. The next step in improving a simple compression algorithm is to replace Huffman encoding with arithmetic/range encoding. Huffman encoding proceeds one bit at a time, treating everything as having a probability that's a power of 1/2. Arithmetic/range encoding uses more accurate probabilities and then packs them together, letting you save a fraction of a bit with every symbol. As an analogy, consider how to encode 3 decimal digits. You could spend 4 bits on each digit, and it would take 12 bits total. Or you could combine them into a single 10 bit number.
- sebular 10y agoReally enjoyed reading this, I think I'd like to look more closely at an implementation to understand it further. Reading the article, I was reminded of a nagging question I've had in the back of my mind for a bit. The ASCII table was invented in the '70s, when the cost of disk storage was much higher than it is today. But it's a shared dictionary, a standard that we can all agree upon, something that's already on every computer. The thing I've wondered about is whether there could be any advantage to creating new generations of shared dictionaries that are domain-specific, and much larger. For example, in the specific (and over-simplified) case of transmitting large quantities of English text from a server to a client, you could reduce the amount of data sent over the wire if both parties shared a lookup table that contained the entire English dictionary. In that case, you wouldn't transmit a book as a collection of characters, but rather as a collection of words. Furthermore, it would seem like you could apply the same traditional compression methods like what's described in the article to furthermore reduce the amount of data being sent. Rather than identifying repeating patterns of letters, you would identify repeating patterns of words. Of course, the obvious drawback is that an English lookup table is useless for transmitting anything other than English text. But again, disk storage being as cheap as it is, I wonder if it wouldn't be such a monumental problem to store many domain-specific dictionaries. Of course, you'd always want to keep the ASCII table as a fallback. Much in the same way that a conversation in sign language (ASL, specifically) is largely composed of hand gestures referring to words or concepts, but the language still includes the complete alphabet as a fallback. The thing I don't understand well enough is whether modern compression already incorporates concepts that are similar enough such that a shared-word dictionary would be useless. It seems like the "LZXX" style of compression essentially includes a similar but dynamically-generated sort of dictionary at the beginning of the transmission, and subsequently refers to that in order to express the message itself. Would the gains of having enormous shared dictionaries cancel out the advantage of that approach, only in a much more "wasteful" way?
- carey 10y agoIt sounds like what you're thinking of has been included in the Brotli compression algorithm, which uses a relatively large initial dictionary. There are similar ideas with a more limited scale in HTTP/2's HPACK algorithm for header compression.
- mozumder 10y agoDeflate is so ubiquitous (being a web standard) that I'd like to see a hardware Deflate encoder/decoder. It really needs to be in the core instruction set of x86 & ARM.
- userbinator 10y agohttp://www.xilinx.com/products/intellectual-property/1-7aisy9.html http://www.xilinx.com/products/intellectual-property/1-7aisy...
- beagle3 10y agoThere were a lot of encoders at the time using this general scheme (a few more values to indicate match length or distances). PKZIP won at the time because it was faster, and PK had the name recognition from his PKARC, which was a superfast implementation of SEA ARC (the dominant archiver on PCs at the time). PK had to stop working on PKARC because of a C&D request from SEA. He wrote the first algos of PKZIP, which were on par with SEA ARC on compression (and with PKARC on speed), but weren't much better. (And have been deprecated since the 1990 if I'm not mistaken). Then, the Japanese encoders started to rule the compression ratio (and had comparably reasonable compression times) - LHArc, LZAri, don't remember the rest of the names. LHArc or LHA (don't remember which), had basically the same scheme that PKZIP converged on, except it used adaptive arithmetic coding. PK replaced that with static huffman coding, trading a little compression for a lot of speed, and the format we now know and love as "zlib compression" was born (and quickly took the world by storm, being in a sweet spot of compression and speed). There's another non-trivial thing that PKZIP had going for it - it put the directory at the end, which meant you could see the list of files in the archive without reading the entire archive! This sounds simple, but back then everyone adopted the tar-style "file header then data" appendable style, which meant that just listing the files inside a 300KB zip file (almost a whole floppy disk!) meant reading that entire floppy (30 seconds at least). PKZIP could do it in about 2 seconds.
- carey 10y agoWeren't there also (alleged) patents on arithmetic coding back then? Huffman coding had that as an advantage, too, especially when GNU were looking for an alternative to Unix' compress program.
- TD-Linux 10y agoYes there were. JPEG was also affected, and most decoders still don't support the optional arithmetic mode.
- creshal 10y ago> There's another non-trivial thing that PKZIP had going for it - it put the directory at the end, which meant you could see the list of files in the archive without reading the entire archive! Beginning and the end, which continues to bite us in the ass until today, where we regularly stumble over bugs when one part of a toolchain uses one entry and the rest the other.
- shenberg 10y agoThe most clever part of deflate is actually how they store the huffman trees without storing the frequencies but rather the length in bits of each symbol. Combining the length of each symbol with its lexicographical ordering is enough to uniquely specify the actual tree. Ok, some research showed me that the idea can probably be traced back to Schwartz & Kallick 1964 (can't find the text), popularized by TAOCP vol. 1...
- userbinator 10y agoThe technique is known as "Canonical Huffman" and is quite elegant indeed. It is best understood by considering the codes as binary numbers, then the tree structure naturally appears. There's a very short algorithm to generate the appropriate encoding and decoding tables in the JPEG standard and it involves not much more than shifts and adds.
- jamesfisher 10y ago> This paragraph has five-hundred and sixty-one lower-case letters in It must have taken some trial-and-error to make this sentence correct, since the number itself adds some letters.
- to3m 10y agoPick a value that's close enough, and tweak everything else until it's true :) This post has one hundred and thirty-two chars in it.
- vintermann 10y agoThis, ten
- syntheticnature 10y agoInterestingly, it can work in-place if you change it to "This paragraph has five-hundred and sixty-three lower-case letters in"