Efficient approximate adaptive coding

Abstract

A pseudo-adaptive mechanism for achieving efficient one-pass coding is described. Symbol frequencies are approximated to the powers of a geometric sequence, and then the set of codewords fully recalculated each time the quantised set of frequencies changes. Novel code calculation procedure that is extremely efficient on geometric distributions of probabilities is then used that allows both encoding and decoding to take time linear in the number of inputs processed and outputs generated. Analysis is also given to bound the compression inefficiency caused by the use of approximate symbol probabilities. Experiments with the proposed method show it to be an attractive compromise between semi-sta..