Building a data compression utility in Haskell using Huffman codes

Re:Building a data compression utility in Haskell using Huff... by kqr on Thursday July 04, 2024 @03:46AM (#40873124)

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

[ Parent | on HN ]

Re:Building a data compression utility in Haskell using Huff... by hcs on Thursday July 04, 2024 @04:05AM (#40873210)

Huffman 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)

[ Parent | on HN ]

Re:Building a data compression utility in Haskell using Huff... by lifthrasiir on Thursday July 04, 2024 @03:59AM (#40873179)

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

[ Parent | on HN ]

Re:Building a data compression utility in Haskell using Huff... by SassyBird on Thursday July 04, 2024 @06:42AM (#40873855)

Hopefully k is natural. ;)

[ Parent | on HN ]

Re:Building a data compression utility in Haskell using Huff... by lifthrasiir on Thursday July 04, 2024 @08:05AM (#40874211)

Implied because any symbol distribution which probabilities do not sum to 1 is invalid anyway ;-)

[ Parent | on HN ]