Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Building a data compression utility in Haskell using Huffman codes

lazamar.github.io

Post reply on HN
Print view View original

51–60 of 94 posts

Re: Building a data compression utility in Haskell using Huffman codes

#51

Post by userbinator »

mrkeen wrote: post #8

There 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…

The 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.

Re: Building a data compression utility in Haskell using Huffman codes

#52

Post by userbinator »

londons_explore wrote: post #5

For 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 u…

LZ 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.

Re: Building a data compression utility in Haskell using Huffman codes

#53

Post by mrkeen »

random3 wrote: post #38
benreesman wrote: post #20

Haskell 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 exc…

How do you distinguish data shuffling from computation? What’s actual computation from this perspective?

Before I was good at Haskell, I would approach a data-processing job sequentially based on the next thing that needs to be done.

I want to open a file, and I can't read it all at once, so I'll use a FileReader and it should be buffered, so I'll wrap it with a BufferedReader. I'll use try-with-resources and click into the classes because I can't remember if the contract of the outermost reader is that it will close the inner readers too.

Right, now I'll grab the next n bytes from the stream, and start thinking about the algorithm. Swear a bit when I think about crossing the buffer boundaries, and on-and-on...

The IO concerns are very much interwoven with the algorithm.

In Haskell I just start by writing one function from bytes to bytes. That's the computation. Then when that's done I expose that function as bytes to bytes.

Others can hook it up to files, webservers, pipe it through gzip, whatever!

Re: Building a data compression utility in Haskell using Huffman codes

#54

Post by lazamar »

userbinator wrote: post #52
londons_explore wrote: post #5

For 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 u…

LZ 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.

Indeed, 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.

Re: Building a data compression utility in Haskell using Huffman codes

#55

Post by [deleted] »

tromp wrote: post #18

> 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 o…

[deleted]

Re: Building a data compression utility in Haskell using Huffman codes

#56

Post by n4r9 »

tromp wrote: post #18

> 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 o…

It'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 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.

Re: Building a data compression utility in Haskell using Huffman codes

#57

Post by ykonstant »

Iceland_jack wrote: post #24
ykonstant wrote: post #21

Hey, 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.

I 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 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

Thanks for the info!

Re: Building a data compression utility in Haskell using Huffman codes

#58

Post by ykonstant »

mrkeen wrote: post #32
ykonstant wrote: post #21

Hey, 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.

I like Haskell performance for every-day backend/web and CLI stuff. But I drop down into Rust when I'm writing something performance-focused. That said, Haskell's no slouch. Here's a small program to count the 1-bits in a file. main :: IO () main = do content >= \[a] -> unsafeMMapVector a Nothing print (vectorPopCount content) vectorPopCount :: V.Vector Word64 -> Int vectorPopCount = V.foldl' (+) 0 . V.map popCount W…

The lack of heap allocations is great! Thanks for the pointers.

Re: Building a data compression utility in Haskell using Huffman codes

#59

Post by d_burfoot »

userbinator wrote: post #52
londons_explore wrote: post #5

For 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 u…

LZ 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.

> 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

Re: Building a data compression utility in Haskell using Huffman codes

#60

Post by freilanzer »

epgui wrote: post #22
ykonstant wrote: post #21

Hey, 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.

I’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.

I'm pretty sure highly optimised code won't be elegant Haskell code though.
Post reply on HN