What does “ω(1)” mean in this instance?
f(n) is in ω(g(n)) if for all c > 0 there exists N > 0 such that c|g(n)| <= |f(n)| for all n >= N
Patents used to be the reason for choosing Huffman, but now even that reason is gone.
"Comparison of Huffman and Arithmetic Coding" and the conclusion is around the following lines:
"...This means that for most sources we can get rates closer to the entropy using arithmetic coding than by using Huffman coding. The exceptions are sources whose probabilities are powers of two. In these cases, the single-letter Huffman code achieves the entropy; and we cannot do any better
with arithmetic coding, no matter how long a sequence we pick..."
"...for Huffman codes, we are guaranteed to obtain rates within 0.086 + pmax of the entropy, where pmax is the probability of the most probable letter in the alphabet. If the alphabet size is relatively large and the probabilities are not too skewed, the maximum probability pmax is generally small. In these cases, the advantage of arithmetic coding
over Huffman coding is small; and it might not be worth the extra complexity to use arithmetic coding rather than Huffman coding. However, there are many sources, such as facsimile, in which the alphabet size is small; and the probabilities are highly unbalanced. In these cases, the use of arithmetic coding is generally worth the added complexity...."
Many modern compression algorithms use ANS for entropy coding.
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.
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.)