3 ms·

That smells an awful lot like arithmetic coding. Is it just a reformulation (genuinely curious)?

dietrichepp 4y ago
I wouldn't describe it as a reformulation, but as a different solution to the same problem. The goal of entropy coders in general is to encode each symbol using -log P bits, where P is the probability of that symbol. Huffman, arithmetic encoding, range coding, and ANS / FSE are different systems that solve this problem. https://en.wikipedia.org/wiki/Entropy_coding https://en.wikipedia.org/wiki/Entropy_coding Huffman coding works by using an integer number of bits for each symbol and then creating a prefix-free code. This is computationally cheap but wastes some space. Arithmetic coding works using interval arithmetic. Each symbol corresponds to an interval, and you multiply each successive interval together, renormalizing after each step. This is close to optimal but computationally expensive. ANS / FSE work by using a state machine. A particular symbol can be coded using a variable number of bits, but that number is an integer. The average number of bits is close to -log P. Like Huffman coding, coding and decoding is fast--each symbol uses an integer number of bits, and you don't need to do any multiplication. Like Arithmetic coding, it is close to optimal in terms of space used. These techniques share one thing in common--you only need to record symbol frequency in order to recreate the codebook. In Huffman coding, you typically encode the symbol frequency log 2 (i.e. the symbol length). In FSE and arithmetic coding, you typically encode the symbol frequency as a dyadic rational. You use a deterministic process to recreate the exact same codebook given these frequencies. (Then the question is, "How do you encode the symbol frequency efficiency?" For Deflate, the answer is, funny enough, the symbol lengths for the Huffman codes are themselves encoded using Huffman codes! The codebook for that Huffman code is then coded using a fixed codebook.)

I wouldn't describe it as a reformulation, but as a different solution to the same problem. The goal of entropy coders in general is to encode each symbol using -log P bits, where P is the probability of that symbol. Huffman, arithmetic encoding, range coding, and ANS / FSE are different systems that solve this problem. https://en.wikipedia.org/wiki/Entropy_coding https://en.wikipedia.org/wiki/Entropy_coding Huffman coding works by using an integer number of bits for each symbol and then creating a prefix-free code. This is computationally cheap but wastes some space. Arithmetic coding works using interval arithmetic. Each symbol corresponds to an interval, and you multiply each successive interval together, renormalizing after each step. This is close to optimal but computationally expensive. ANS / FSE work by using a state machine. A particular symbol can be coded using a variable number of bits, but that number is an integer. The average number of bits is close to -log P. Like Huffman coding, coding and decoding is fast--each symbol uses an integer number of bits, and you don't need to do any multiplication. Like Arithmetic coding, it is close to optimal in terms of space used. These techniques share one thing in common--you only need to record symbol frequency in order to recreate the codebook. In Huffman coding, you typically encode the symbol frequency log 2 (i.e. the symbol length). In FSE and arithmetic coding, you typically encode the symbol frequency as a dyadic rational. You use a deterministic process to recreate the exact same codebook given these frequencies. (Then the question is, "How do you encode the symbol frequency efficiency?" For Deflate, the answer is, funny enough, the symbol lengths for the Huffman codes are themselves encoded using Huffman codes! The codebook for that Huffman code is then coded using a fixed codebook.)