An improved data structure for cumulative probability tables

Abstract

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 sth 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 sth most frequent, the cost of processing each symbol is then linear in the number of bits produced by the arithmetic coder.