Fast adaptive arithmetic code for large alphabet sources with asymmetrical distributions

摘要

We address the problem of constructing an adaptive arithmetic code in the case where the source alphabet is large and there are lots of different symbols with equal counts of occurrence. For an alphabet of N symbols and r distinct symbol weights we describe a code for which the number of operations needed for encoding and decoding is equal to clogr+c/sub 1/ instead of clogN+c/sub 2/ as in previous arithmetic codes, c, c/sub 1/, c/sub 2/ are constants. When r is small relative to N-which is the case for most practical coding problems on large alphabets-the encoding and decoding speed of the suggested code will be substantially greater than with known methods.