A New Data Structure for Cumulative Frequency Tables
📜 Abstract
A new method (the ‘binary indexed tree’) is presented for maintaining the cumulative frequencies which are needed to support dynamic arithmetic data compression. It is based on a decomposition of the cumulative frequencies into portions which parallel the binary representation of the index of the table element (or symbol). The operations to traverse the data structure are based on the binary coding of the index. In comparison with previous methods, the binary indexed tree is faster, using more compact data and simpler code. The access time for all operations is either constant or proportional to the logarithm of the table size. In conjunction with the compact data structure, this makes the new method particularly suitable for large symbol alphabets.
✨ Summary
The paper introduces the binary indexed tree, now commonly called the Fenwick tree, as a compact array-based structure for maintaining cumulative frequencies in adaptive arithmetic coding. Its representation decomposes prefix totals according to the binary representation of indices, enabling cumulative-frequency queries, point updates, single-frequency recovery, frequency-to-symbol searches, and scaling operations with constant or logarithmic access costs. Experiments on the Calgary Corpus reported fewer array references than the compared move-to-front, splay-tree, and heap-based methods for most tested files, while using substantially less storage. The paper also identified applications to large-alphabet and order-one arithmetic compression.\n\nThe structure became a standard technique for dynamic prefix sums and frequency-based ranking. Subsequent research has developed succinct Fenwick-tree representations and compact variants for dynamic ranking and predecessor search, explicitly building on the original data structure. (static.aminer.org) It has also been used as a cited implementation primitive in applied work, including computational biology and quantum-computing research. (pmc.ncbi.nlm.nih.gov)