An Improved Data Structure for Cumulative Probability Tables
Department of Computer Science,
The University of Melbourne,
Parkville 3052, Australia.
Software-Practice & Experience, 29(7):647-659, 1999.
In 1994 Peter Fenwick at the University of Auckland devised an elegant
mechanism for tracking the cumulative symbol frequency counts that are
required for adaptive arithmetic coding.
His structure spends O(log n) time per update when processing the
s'th symbol in an alphabet of n symbols.
In this note we propose a small but significant alteration to this
mechanism, and reduce the running time to O(log(1+s)) time per update.
If a probability-sorted alphabet is maintained, so that symbol s in the
alphabet is the s'th most frequent, the cost of processing each symbol is
then linear in the number of bits produced by the arithmetic coder.
Public software is being prepared, and will appear at
http://people.eng.unimelb.edu.au/ammoffat/arith_coder/ when ready.