An Improved Data Structure for Cumulative Probability Tables

Alistair Moffat
Department of Computer Science, The University of Melbourne, Parkville 3052, Australia.

Status

Software-Practice & Experience, 29(7):647-659, 1999.

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 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.

Paper Preprint

Author version of paper (PDF).

Source Code

Public software is being prepared, and will appear at http://people.eng.unimelb.edu.au/ammoffat/arith_coder/ when ready.