Zstandard Worked Example
Nice writeup! FSE, one of the parts of Zstandard, is a very elegant entropy coder. If you&#x27;re following this section of the article, you might be wondering how it&#x27;s encoded, since the encoding process is somewhat less obvious than for Huffman coding.<p>What causes trouble is simply, &quot;Once you&#x27;ve emitted a symbol, how do you know that the next symbol is in the range [BL, BL+2^NB)?&quot; 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 <i>previous</i> symbol so that the <i>current</i> symbol is in the previous symbol&#x27;s [BL, BL+2^NB) range.<p>There&#x27;s another writeup about FSE here, which goes into more depth about FSE (rather than talking about Zstandard in general):<p><a href="http:&#x2F;&#x2F;fastcompression.blogspot.com&#x2F;2013&#x2F;12&#x2F;finite-state-entropy-new-breed-of.html" rel="nofollow">http:&#x2F;&#x2F;fastcompression.blogspot.com&#x2F;2013&#x2F;12&#x2F;finite-state-ent...</a><p>My intuition tells me that there&#x27;s probably a homomorphism from Huffman coding to FSE that preserves the encoded size exactly, but I haven&#x27;t done the math to check.