7 ms·
Building a data compression utility in Haskell using Huffman codes
- tankfeeder 2y agohttps://rosettacode.org/wiki/Huffman_coding https://rosettacode.org/wiki/Huffman_coding
- lynx23 2y agoVery nice read, thanks for sharing!
- revskill 2y agoWhat's nice ?
- alwinaugustin 2y agoThanks for sharing. Very nice and insightful.
- londons_explore 2y agoFor all readers, arithmetic codes are better in nearly all ways. They can be implemented in less RAM and code, they compress and decompress to a better ratio, and the probabilities of different symbols appearing can be dynamically updated during the stream far more easily. The only reason Huffman codes are used is they were invented first and arithmetic codes were patented. That patent has now expired, so we should use the better design.
- londons_explore 2y agoTwo slight benefits of Huffman codes over arithmetic: * They usually self synchronize when some data is corrupted (but not guaranteed, does not apply where the Huffman table is dynamic) * Neither Huffman nor arithmetic codes are easy to parallelize the decoding of, but Huffman is slightly easier.
- kqr 2y agoI was under the impression that arithmetic codes are guaranteed to be at least one bit less efficient than Huffman codes per input block. What makes you say they have better compression ratio? Are you thinking of pre-defined Huffman tables that aren't adapted to the input? Because the latter ought to be as good as it gets. (I agree with the other benefits. Since arithmetic coding tables are built in a streaming fashion rather than constructing the codebook up front, they are more memory-efficient while working.)
- lifthrasiir 2y agoHuffman codes are conceptually isomorphic to arithmetic codes where all probabilities are 2^-k with k integer, so they have an obvious disadvantage due to more inaccurate symbol distribution.
- SassyBird 2y agoHopefully k is natural. ;)
- lifthrasiir 2y agoImplied because any symbol distribution which probabilities do not sum to 1 is invalid anyway ;-)
- hcs 2y agoHuffman codes are less efficient per symbol since each symbol is a bit string, arithmetic coding effectively smears symbols across bits more finely. Whether you use a dynamic or static probability model is a different issue applying to either coding method. (Emotionally though I prefer Huffman codes, they're just so neat)
- lifthrasiir 2y agoIf you do have an option to switch from Huffman, rANS is now the way to go, not a clasical arithmetic coding.
- lazamar 2y agoThere is one way in which Huffman codes are better: they are easier to explain and simpler to implement. I went for simplicity of exposition in the post, but arithmetic coders can indeed get arbitrarily close to the entropy, which is not quite the case with Huffman.
- nottorp 2y ago> easier to explain I think Huffman is the one compression algorithm that compresses stuff significantly that can fit on the proverbial napkin, so it's a good start. The others require the whole napkin stack at the table.
- userbinator 2y agoLZ is even better. Neither arithmetic nor Huffman will compress when the probability of all symbols is the same, but LZ will find repetitions easily. LZ also decompresses extremely quickly --- faster than memcpy is often mentioned.
- lazamar 2y agoIndeed, but worth noting that LZ is a modelling scheme, whilst Huffman is a coding technique. That is, LZ determines, dynamically as it goes, what are all the elements we want to encode and their probabilities. Then you need a coder, like Huffman, to actually encode it. In the post I used a semi-static zero-order byte-based model. Which means I counted the byte occurrences first and just used that count for the probabilities throughout all of the encoding. Then I used Huffman codes to translate those probabilities into bits. But I'm considering writing a follow-up changing this static model for an LZ77 one as I think that would be fun.
- d_burfoot 2y ago> LZ is even better. Neither arithmetic nor Huffman will compress when the probability of all symbols is the same Comparing LZ to arithmetic encoding is a category error. LZ and Huffman are combined modeling+encoding methods, while arithmetic is just an encoding method, and it can be combined with any modeling technique. Arithmetic plus a suitable modeling technique will achieve compression as good as LZ, Huffman, or any other scheme. The PAQ8 compressors, and I believe its successors in the Hutter Prize ranking, use arithmetic plus a very advanced modeling scheme. http://prize.hutter1.net/hfaq.htm#paq8 http://prize.hutter1.net/hfaq.htm#paq8
- mrkeen 2y agoThere exists an array-based, in-place algorithm for this, reducing the need to allocate trees and chase pointers. I mention this only because, when I learned the tree-based approach at uni, I simply wasn't aware that there was another way to do it, and I'm wondering how many of you that's true for as well. While the tree approach is intuitive and illuminating, it probably makes more sense to work with in-place arrays, since the situations when you care most about compression are probably the situations when you have a lot of data and want to run fast. In-Place Calculation of Minimum-Redundancy Codes Moffat, Katajainen. 1995. http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdf
- userbinator 2y agoThe JPEG standard ITU T.81 (1992) has a description of the algorithm in flowcharts, so the knowledge of array-based Huffman was probably already somewhat common in the 80s.
- lifthrasiir 2y ago> In-Place Calculation of Minimum-Redundancy Codes Or in general, refer to "On the Implementation of Minimum Redundancy Prefix Codes" by Moffat and Turpin (1997), as strongly recommended and later explained by Charles Bloom [1]. [1] https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffman-paper.html https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...
- lazamar 2y agoThanks for the link. I was motivated to write the post after reading Moffat’s book ‘Managing Gigabytes’. A pearl from the 90’s. The authors mention this technique in the second edition.
- mjan22640 2y ago> and I'm wondering how many of you that's true for as well the phrasing sounds like a list comprehension
- agumonkey 2y ago
- banish-m4 2y agoLast time I used Huffman codes, it was to run a MICMAC processor macroprogram (assembly text) in the fewest number of microcycles and to use the fewest microinstructions in the microprogram (microcode). So starting with a histogram of the macroinstructions executed (IIRC, I first wrote an interpreter in C to count how many of each were executed), I crafted a progressive decoding microcode program to implement all of the required ISA macro-operations. IIRC, the macro instruction ISA I created was bit-granular instead of byte-oriented. In the real world, it would've been slow and inconvenient. What's nice about Huffman codes is that you can vary the prefix depth based on the distribution of values, so you don't have to have lopsided codes based on 1 bit prefixes. Also, the microprogram had to deal with branch prediction because it was a non-superscalar pipelined processor model. Guess the wrong branch, and enjoy wasting cycles on a pipeline stall while the correct branch filters forward.
- atlintots 2y agoThis is great! Are there any other similar tutorials going through writing a Haskell program, but with some more advanced features (monad transformers, lenses, etc)
- trealira 2y agoI would recommend the book Haskell in Depth, which covers both of those topics (monad transformers by chapter 6, lenses in chapter 3 and chapter 14). It also covers some other advanced features, like Template Haskell and concurrency, and has a chapter dedicated to working with SQL databases in Haskell.
- mirpa 2y agoYou might try: https://github.com/turion/rhine-koans https://github.com/turion/rhine-koans it is tutorial for FRP library Rhine, well commented with tests
- tromp 2y ago> To make it unambiguous we must make sure that no code word is a prefix of another code word. Technically, this is not quite correct. The class of so-called uniquely decodable codes is unambigous, and a superset of the prefix codes. One simple example of a uniquely decodable code is the reverse of a prefix code. For the example in the article that would be a 1 b 00 c 10 While the code for a is a prefix of the code of c, one can still unambiguously decode any code sequence by processing it in reverse order. It would be interesting to see a uniquely decodable code that is neither a prefix code nor one in reverse.
- lazamar 2y agoThat’s interesting. I guess this is not usually used because you may have a long string of bits that is ambiguous till you get to a disambiguating bit. Something like `100000000000000001` In this case, where to know whether the first code was an `a` or a `c` you have to read all the way to where the zeroes end.
- deleted 2y ago[deleted]
- deleted 2y ago[deleted]
- n4r9 2y agoIt's a weird example, but what about a 1 b 101 ? It is neither prefix-free nor suffix-free. Yet every occurrence of 0 corresponds to an occurrence of b. However, this is obviously inefficient. So I guess the question is whether there's an optimal code which is neither prefix-free nor suffix-free. -------------- EDIT I did some googling and found this webpage https://blog.plover.com/CS/udcodes.html https://blog.plover.com/CS/udcodes.html where the author gives the following example of a uniquely decodable code: a 0011 b 011 c 11 d 1110 I guess this is "almost" prefix-free since the only prefix is c of d. If a message starts wiht 1, you could find the first 0 and then look at whether there's an odd or even number of 1's. So I think I can see how it's uniquely decodable. However, my crypto knowledge is too rusty to remember how to show whether this is an optimal code for some probability distribution.
- benreesman 2y agoHaskell is a really nice language. In general I don’t identify as an X programmer for any value of X: I tend to write in a half dozen languages daily and they all suck in their own special way. But on two separate occasions I made important career decisions with opportunity cost to work with highly lethal GHC contributors: those people are just really good. If Haskell sucks like all languages it’s because Haskell excels at using computers to compute something: Haskell considers data shuffling a strictly secondary concern compared to doing actual computations.
- random3 2y agoHow do you distinguish data shuffling from computation? What’s actual computation from this perspective?
- tossandthrow 2y agoPhilosophically speaking there is no difference. What parent commenter probably refers to is that you think in terms of computations and not in terms of data units. And that is just tremendously elegant.
- 082349872349872 2y agoPhilosophically speaking there's a great difference. Data shuffling doesn't —in principle— lose information; computation does. ("evaluation is forgetting") In https://news.ycombinator.com/item?id=32498382 https://news.ycombinator.com/item?id=32498382 "glue code" and "parsley code" are data shuffling, while "crunch code" is computation.
- tossandthrow 2y agoSurely someone could find a taxonomy that makes a distinction... I guess we have to colive in a world where both views are true.
- 2y ago
- ykonstant 2y agoHey, since this is likely to attract Haskell programmers: how fast is Haskell these days for a programmer intent on writing optimized code? I am particularly interested in its performance for numerical crunching like matrix operations and other stuff that benefit from SIMD.
- epgui 2y agoI’m not the best person to answer this question, but AFAIK it’s very very fast (in the rough vicinity of C). But also memory-hungry.
- freilanzer 2y agoI'm pretty sure highly optimised code won't be elegant Haskell code though.
- rebeccaskinner 2y agoHighly optimized code tends to be inelegant in any language. That said, you can get really good performance from very elegant looking “normal” Haskell too. The big challenge with performance in Haskell is that the differences between optimized and unoptimized code can be pretty subtle if you’re not used to thinking about Haskell performance.
- epgui 2y agoLet me clarify: naive/beautiful/effortless Haskell code tends to be highly performant, although that is not always true. I believe it is much easier to write fast Haskell code than to write fast C/C++ code.
- Iceland_jack 2y agoI met Sam Derbyshire at ZuriHac who told me all the difficult architectural work had been done for SIMD support. + https://gitlab.haskell.org/ghc/ghc/-/issues/7741 https://gitlab.haskell.org/ghc/ghc/-/issues/7741 It might make it for GHC 9.12 (for 128 bit vectors only, and mostly floating-point operations unless other people come in and contribute). The patch is at: + https://gitlab.haskell.org/ghc/ghc/-/merge_requests/12860 https://gitlab.haskell.org/ghc/ghc/-/merge_requests/12860
- bdahz 2y agoHow is the performance when compared to similar implementations in C/C++ or Rust?
- lazamar 2y agoI’d say unbeatable! The goal was simplicity of implementation and code clarity. For this kind of thing I say Haskell performs the best.
- mrkeen 2y agoThat wasn't really the spirit of the question as I read it. 'Performance' has a narrower definition than that.
- zarathustreal 2y agoThe point they’re making is that there is no performance without tradeoffs and “fast” is meaningless unless you define what you’re measuring. Asking the question implies a misunderstanding of the intent of the implementation, OP was trying to subtly let them know.
- bdahz 2y agoFor the simplicity of implementation and code clarity, I need to know how much I need to pay for it. If the Haskell implementation is 3x slower than C/C++/Rust implementation, it would be acceptable. If it's 30x slower, I would rather choose C/C++/Rust even the implementation won't be simple. If it is even possible to be 3x faster than C/C++/Rust, then why not the mainstream programmers adopt Haskell everywhere?
- lazamar 2y agoThe goal of this implementation is not to be fast, but to be clear. I am doing some inefficient things (like two pass encoding) on purpose to keep things simple and clear. So using this particular piece of code to judge a language's performance potential is not really the way to go here.
- chvrchbvrner 2y agoI think there is a typo in the table of the "Creating prefix-free codes" section. D should be '0010' (not '0110'). Otherwise a great read, thanks!
- 2-3-7-43-1807 2y agoand yet another episode in the series of "look, what I did with Haskell"
- goldfishgold 2y agoCoursera’s functional programming course (in Scala) includes a pretty similar Huffman coding assignment with autograder if anybody wants to take a stab at it themselves. https://www.coursera.org/learn/scala-functional-programming?specialization=scala#modules https://www.coursera.org/learn/scala-functional-programming?...
- polterguy1000 2y ago[flagged]
- dist-epoch 2y agoArithmetic codes are not marginally better. Asymmetric numeral systems, which is related to arithmetic coding was a real breakthrough used in all modern compressors.
- VMG 2y agoDownvoted not because of AI but because of snark and negativity
- freilanzer 2y agoWas this supposed to be funny?
- lo_zamoyski 2y agoBtw, what is that on the girl's shirt in the image? Direct link: https://lazamar.github.io/images/data-compressor.svg https://lazamar.github.io/images/data-compressor.svg
- iso8859-1 2y agoShe has made Jesus illegal.