A Matrix Data Structure to Organize Cumulative Frequencies for Efficiency of Adaptive Arithmetic Compression

Abstract

A novel data structure, namely Cumulative Frequency
Matrix (CFM), is proposed here for maintaining cumulative
frequencies used in adaptive arithmetic data compression method. Arithmetic coding is based on cumulative probability interval of symbols. It computes subintervals using cumulative frequency of a symbol while encoding and decoding. While decoding, it also needs to find subinterval in which a given value falls. Adaptive methods need to compute cumulative frequencies on fly. CFM is suggested here for efficiency of algorithms to operate on cumulative frequency at runtime. CFM is a 2-D array of 16 rows and 16 columns for order-0
model. In order-0 model, a symbol is of single byte and it has two nibbles; say L for left and R for right. In CFM, row corresponds to left nibble and column corresponds to right nibble. As each nibble is of four bits, row index and column index varies from 0 to 15. Within row L, it stores partial cumulative frequency of only those symbols whose
left nibble is L. Thus matrix element (L, R) contains the partial cumulative frequency of a symbol with right nibble as R among all the symbols with left nibble as L. This paper analyses algorithm forvarious operations needed in adaptive arithmetic coding. Operations are discussed here for initializing data structure, maintainin cumulative frequencies, computing subinterval, finding subinterval. CFM data structure is compared with Heap as described by Solomon
and Fenwick’s Binary Indexed Tree data structure. As compared with these related data structures in use, proposed data structure CFM is much simpler and efficient as well.