A new data structure for cumulative frequency tables
- 1 March 1994
- journal article
- research article
- Published by Wiley in Software: Practice and Experience
- Vol. 24 (3) , 327-336
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.Keywords
This publication has 4 references indexed in Scilit:
- Linear time adaptive arithmetic codingIEEE Transactions on Information Theory, 1990
- Word‐based text compressionSoftware: Practice and Experience, 1989
- Application of splay trees to data compressionCommunications of the ACM, 1988
- Arithmetic coding for data compressionCommunications of the ACM, 1987