4 ms·
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 alw
by 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 agoBesides 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.