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.
I hear you on writing out explanations taking even longer than grokking the material yourself. But hopefully the path you describe will already help me find an angle to get into the material even if you never get around to it (would love to read such a series though).
I have only done Huffman encoding/decoding in "toy" contexts, although I do think I understand the theory. Also I was not fully aware that ANS and FSE aren't quite the same thing, I thought the latter was "just" the finite-state machine formulation of the concepts described by the former. Perhaps trying to make sense of FSE first will be an easier entrypoint.
Thanks for taking the time to write out all of that advice, it's really appreciated!
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.