3 ms·

Both Huffman coding and arithmetic coding requires a separate coding for the input distribution and it might be easier to code the (canonical) Huffman tree than

Both Huffman coding and arithmetic coding requires a separate coding for the input distribution and it might be easier to code the (canonical) Huffman tree than the full probability distribution. This is also why many uses of arithmetic coding is adaptive.

user-the-name 5y ago
That sounds highly unlikely. To build the Huffman tree you would have to first find the full probability distribution, so arithmetic coding will pretty much always be less work. The reason most arithmetic coding is adaptive is because that is often more efficient, and it is slow and cumbersome to do with Huffman coding.
- lifthrasiir 5y ago
  > The reason most arithmetic coding is adaptive is because that is often more efficient, [...] Adaptive coding can be (technically) thought as a trade-off for stationary distributions, since it takes time for an the current distribution to catch up with the target distribution. Yes, it is more efficient for non-stationary distributions and even bearable for stationary distributions, but that doesn't make stationary adaptive coding is more useful than stationary Huffman coding. As a practical example for my original reply, Zstandard does implement stationary coding for both FSE (the tANS variant of arithmetic coding) and Huffman coding. The structure of the FSE decoding table is not simple, but the minimum number of bits required for each symbol is initially 5. By comparison the direct representation of Huffman tables initially require 4 bits per symbol, with an additional compression scheme available. (Both numbers subsequently decrease as the number of possibilities diminshes.)
  - lifthrasiir 5y ago
    Besides from several typos (I was half-asleep at that time), I should have said "that doesn't make stationary arithmetic coding is as useful than stationary Huffman coding as adaptive arithmetic coding is to adaptive Huffman coding" instead. I really meant that stationary arithmetic coding remains useful but its usefulness is limited.

user-the-name 5y ago

That sounds highly unlikely. To build the Huffman tree you would have to first find the full probability distribution, so arithmetic coding will pretty much always be less work. The reason most arithmetic coding is adaptive is because that is often more efficient, and it is slow and cumbersome to do with Huffman coding.

lifthrasiir 5y ago
> The reason most arithmetic coding is adaptive is because that is often more efficient, [...] Adaptive coding can be (technically) thought as a trade-off for stationary distributions, since it takes time for an the current distribution to catch up with the target distribution. Yes, it is more efficient for non-stationary distributions and even bearable for stationary distributions, but that doesn't make stationary adaptive coding is more useful than stationary Huffman coding. As a practical example for my original reply, Zstandard does implement stationary coding for both FSE (the tANS variant of arithmetic coding) and Huffman coding. The structure of the FSE decoding table is not simple, but the minimum number of bits required for each symbol is initially 5. By comparison the direct representation of Huffman tables initially require 4 bits per symbol, with an additional compression scheme available. (Both numbers subsequently decrease as the number of possibilities diminshes.)
- lifthrasiir 5y ago
  Besides from several typos (I was half-asleep at that time), I should have said "that doesn't make stationary arithmetic coding is as useful than stationary Huffman coding as adaptive arithmetic coding is to adaptive Huffman coding" instead. I really meant that stationary arithmetic coding remains useful but its usefulness is limited.