The week's pick
Reseach Article
Implementing a Novel Data Structure for Maintaining Cumulative Frequency of Symbols
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 41 - Number 15 |
| Year of Publication: 2012 |
| Authors: Jyotika Doshi, Savita Gandhi |
10.5120/5618-7910
|
Jyotika Doshi, Savita Gandhi . Implementing a Novel Data Structure for Maintaining Cumulative Frequency of Symbols. International Journal of Computer Applications. 41, 15 ( March 2012), 34-40. DOI=10.5120/5618-7910
Abstract
A new data structure, namely "cumulative frequency matrix (CFM)", is proposed here for maintaining cumulative frequencies. For an order-0 model having 256 symbols, CFM is a 2-D array of 16 rows and 16 columns. Two nibbles, say L for left and R for right, of a byte symbol represents row and column dimensions respectively. Matrix element (L, R) represents cumulative frequency of symbol with right nibble as R among symbols with left nibble as L. Within row, it stores cumulative frequency of symbols with right nibble varying from 0 to 15. Adaptive arithmetic coding is a lossless data compression method. It needs to update cumulative frequencies at runtime. Various algorithms for maintaining cumulative frequencies, computing cumulative frequency interval etc. are discussed here. Practical implementation shows that proposed data structure is simpler as well as efficient as compared to other data structures in use.
References
- I. H. Witten, R. Neal and J. G. Cleary, "Arithmetic compression for data compression", CACM, 30, (6), 520-540 (1987)
- A. Moffat, "Linear time adaptive coding", IEEE Trans Info. Theory, 36, (2), 401-406 (1990)
- D. W. Jones, Application of splay trees to data compression", Comm ACM, 31, (8), 996-1007 (1988)
- Peter M. Fenwick, "A New Data Structure for Cumulative Frequency Tables", Software – Practice and Experience, Vol 24(3), 327-336 (March 1994)
- W. Weaver and C. E. Shannon. The Mathematical Theory of Communication. University of Illinois Press, Urbana, Illinois, 1949. Republished in paperback 1963.
- Eric Bodden, Malte Clasen, Joachim Kneis, "Arithmetic Coding revealed-A guided tour from theory to praxis", Sable Technical Report No. 2007-5, May 2007, available at http://www. bodden. de/legacy/arithmetic-coding/
- Alexey V. Shanin, "Optimizing Tip on Adaptive Arithmetic Coding", January 2002 available at http://www. codeguru. com/cpp/cpp/algorithms/compression/article. php/c5089/Optimizing-Tip-on-Adaptive-Arithmetic-Coding. htm
- Paul G. Howard, Jeffrey S. Vitter, "Analysis of Arithmetic Coding for Data Compression", Information Processing and Management, Vol. 28, No. 6, pp. 749-764 (1992)
- David Solomon, "Data Compression – The Complete Reference", 3rd edition, Springer, 2004
- Ian H. Witten, Alistair Moffat, Timothy C. Bell, "Managing Gigabytes-Compressing and Indexing Documents and Images", 2nd edition, Morgan Kaufmann Publishers
- Bin Zhu, En-hui Yang, Ahmed H. Tewfik, "Arithmetic Coding with Dual Symbol Sets and Its Performance Analysis", IEEE transactions on Image Processing, Vol. 8, No. 12, 1999, pp 1667
- Ida Mengyi Pu, Fundamental Data Compression, Butterworth-Heinemann, 2006
- P. G. Howard and J. S. Vitter, "Practical implementation of arithmetic coding," in Image and Text Compression, J. A. Storer, Ed. Norwell, MA: Kluwer Academic, 1992, pp. 85–112.
- A. Moffat, R. M. Neal, and I. H. Witten, "Arithmetic coding revisited," ACM Trans. Inf. Syst. , vol. 16, no. 3, pp. 256–294, 1998.
- Ranjan Bose, Saumitr Pathak, "A Novel Compression and Encryption Scheme Using Variable Model Arithmetic Coding and Coupled Chaotic System", IEEE Transaction on Circuits and Systems – I: Regular Papers, Vol. 53, no. 4, 2006, pp 848-857
- Algorithm Tutorials available at http://community. topcoder. com
- Amir Said, "Introduction to Arithmetic Coding - Theory and Practice", Hewlett-Packard Laboratories Report, HPL-2004-76, Palo Alto, CA, April 2004 available at http://www. hpl. hp. com/techreports
Index Terms
Keywords