Compressed Binary-indexed Tree Representing Cumulative Frequency Table for Adaptive Arithmetic Coding
Jian Liu · Microelectronics & Computer · 2003
To maintain the cumulative frequency table consumes much time and memory in the Implementation of adaptive arithmetic coding. This paper presents a compressed binary indexed tree data structure to represent the cumulative frequency table for the purpose of reducing the computation complexity. The data structure can save memory efficiently and decrease the access to the cumulative frequency table a lot. The computation complexity of each operation on the table is O(log(N)).