5 ms·

Nice writeup! FSE, one of the parts of Zstandard, is a very elegant entropy coder. If you're following this section of the article, you might be wondering how i

Nice writeup! FSE, one of the parts of Zstandard, is a very elegant entropy coder. If you're following this section of the article, you might be wondering how it's encoded, since the encoding process is somewhat less obvious than for Huffman coding. What causes trouble is simply, "Once you've emitted a symbol, how do you know that the next symbol is in the range [BL, BL+2^NB)?" The answer is that the encoding is performed backwards, starting from the end of the input, and the table is constructed so that for any symbol emitted, you can find a previous symbol so that the current symbol is in the previous symbol's [BL, BL+2^NB) range. There's another writeup about FSE here, which goes into more depth about FSE (rather than talking about Zstandard in general): http://fastcompression.blogspot.com/2013/12/finite-state-entropy-new-breed-of.html http://fastcompression.blogspot.com/2013/12/finite-state-ent... My intuition tells me that there's probably a homomorphism from Huffman coding to FSE that preserves the encoded size exactly, but I haven't done the math to check.

FullyFunctional 4y ago
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.)
vanderZwan 4y ago
Do you happen to know of any write-ups of ANS/FSE that explain the way it works in a more accessible way? Jarek Duda's work in figuring all of this out is amazing, but it's currently not very easy to grok for mere mortals - even your link says so. Note that this is not a complaint about his output; you probably need to bend your brain into really weird positions with advanced maths to come up with this entropy coding solution in the first place. Plus he deserves a lot of credit for fighting to keep all of his work in the public domain and free of software patents. Having said that, currently I only have a really superficial understanding of how it works, not even enough to experiment and implement something FSE-like on my own. And I'd like to change that. > My intuition tells me that there's probably a homomorphism from Huffman coding to FSE that preserves the encoded size exactly, but I haven't done the math to check. Well Huffman is "optimal" but limited to whole bits, so if it's possible to make a variant FSE encoder that doesn't use fractional bits but "rounds" to whole bits somehow then that probably ends up with the same compression size, no?
- dietrichepp 4y ago
  Have you gone into the details of Huffman coding and implemented a decoder and encoder? I remember reading a description of Huffman out of a book, or maybe Wikipedia or somewhere else, and thinking I understood it. It’s conceptually easy. Then I wrote a Deflate decoder, and better understood what it means to use Huffman in practice—how you transmit the codebook, and how limiting the symbol size lets you make a simple and efficient decoder. Later, I wrote a Huffman encoder, and I realized that the “simple” problem of rounding all of the -log P symbol lengths to integer values is actually a tricky integer programming problem, which we only solve approximately. Making one symbol shorter means you make other symbols longer. The decoder doesn’t have to do this, because it gets a copy of the codebook from the encoder. From that point, I found it easier to tackle FSE through the blog series I linked. Writing your own implementation helps—the blog makes some comment about how FSE works, and if you’re following along with your own implementation, you’re (usually) on a collision course with the reasoning behind that design decision. Meanwhile, you can also peek at the source code for an FSE implementation and try to understand things from that angle at the same time. Duda’s work is also not FSE, but ANS. My understanding is that Duda’s work on ANS was adapted and modified to create FSE. So if you read the paper on ANS, and trying to make an FSE implementation, it might be a bit confusing. I think it would be fun to try and write up a “demystifying FSE” article or series of articles, but my best estimate is that this would take at least a couple months, if not half a year, to do it. I most recently reverse engineered an audio compression format called VADPCM and the writeups for it are time-consuming.

FullyFunctional 4y ago

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

vanderZwan 4y ago

Do you happen to know of any write-ups of ANS/FSE that explain the way it works in a more accessible way? Jarek Duda's work in figuring all of this out is amazing, but it's currently not very easy to grok for mere mortals - even your link says so. Note that this is not a complaint about his output; you probably need to bend your brain into really weird positions with advanced maths to come up with this entropy coding solution in the first place. Plus he deserves a lot of credit for fighting to keep all of his work in the public domain and free of software patents. Having said that, currently I only have a really superficial understanding of how it works, not even enough to experiment and implement something FSE-like on my own. And I'd like to change that. > My intuition tells me that there's probably a homomorphism from Huffman coding to FSE that preserves the encoded size exactly, but I haven't done the math to check. Well Huffman is "optimal" but limited to whole bits, so if it's possible to make a variant FSE encoder that doesn't use fractional bits but "rounds" to whole bits somehow then that probably ends up with the same compression size, no?

dietrichepp 4y ago
Have you gone into the details of Huffman coding and implemented a decoder and encoder? I remember reading a description of Huffman out of a book, or maybe Wikipedia or somewhere else, and thinking I understood it. It’s conceptually easy. Then I wrote a Deflate decoder, and better understood what it means to use Huffman in practice—how you transmit the codebook, and how limiting the symbol size lets you make a simple and efficient decoder. Later, I wrote a Huffman encoder, and I realized that the “simple” problem of rounding all of the -log P symbol lengths to integer values is actually a tricky integer programming problem, which we only solve approximately. Making one symbol shorter means you make other symbols longer. The decoder doesn’t have to do this, because it gets a copy of the codebook from the encoder. From that point, I found it easier to tackle FSE through the blog series I linked. Writing your own implementation helps—the blog makes some comment about how FSE works, and if you’re following along with your own implementation, you’re (usually) on a collision course with the reasoning behind that design decision. Meanwhile, you can also peek at the source code for an FSE implementation and try to understand things from that angle at the same time. Duda’s work is also not FSE, but ANS. My understanding is that Duda’s work on ANS was adapted and modified to create FSE. So if you read the paper on ANS, and trying to make an FSE implementation, it might be a bit confusing. I think it would be fun to try and write up a “demystifying FSE” article or series of articles, but my best estimate is that this would take at least a couple months, if not half a year, to do it. I most recently reverse engineered an audio compression format called VADPCM and the writeups for it are time-consuming.