Email this article 
Open Access
Subscription or Fee Access
Analysis of Various Issues of Data Compression Algorithms
Abstract
Compression is used just about everywhere. Themotivation of the compression is reduction of data storage and transmission bandwidth requirements. Compression helps reduce the consumption of expensive resources, such as hard disk space or transmission bandwidth. So the growth of volume of data has led to a need for “Data Compression “, that is the ability to reduce the amount of storage or Internet bandwidth required to handle this data. Compression is the reduction in size of data in order to save space or transmission time. For data transmission, compression can be performed on just the data content or on the entire transmission unit depending on a number of factors. This paper summarizes the different issues related with the various compression algorithms such as Huffman Coding, LZW Coding, Arithmetic Coding, BWT related with various authors. By implementing these algorithms, I get some results and regarding to these results we suggest the efficient algorithm to be used with a certain type of file to be compressed. This paper compares the features of these algorithms also such as Compression speed, Decompression speed, Memory space occupied, Compression ratio etc.
Keywords
References
Amir said, “Arithmetic Coding”, in Lossless Compression Handbook, Academic Press, San Diego, CA, 2003.
Belinskaya D., De Agostion S., Storer J .A., “Near Optimal Compression with Respect to a Static Dictionary on a Practical Massively Parallel Architecture”, Proc. Data Compression Conference DCC-95, Snowbird, 1995.
Bentley j., Sleator D., Tarjan R., “A locally adaptive data compression scheme”, Communication of the ACM, vol. 29,pp. 320-330, April 1986.
Burrows M. and Wheeler D.J., “A Block- Sorting Lossless Data Compression Algorithm”, Research Report 124, Digital System Research Center, 1994.
Chung K.L., “Efficient Huffman decoding”, Inf.Process.lett.,vol 61,pp97-99,1997
De Agostino S., Storer J. A., “Optimal Algorithms for Optimal Compression using Dictionaries with the prefix Propertyon “, Proc. Data Compression Conference DCC-92, Snowbird.
Cleary J.G., “Arithmetic coding for data compression”, Commun. ACM. Vol. 30, pp.520-540, 1987.
Cleary J.G.,“Data Compression using daptive coding and partial string matching”, IEEE Transaction on communication, vol.32,pp.396-402, April 1984.
Chamzas C., “Probability estimation in arithmetic and adaptive –Huffman entropy coders”, IEEE Trans. Image Processing, vol 4, pp.237-249, March 1995.
Clearly J.G, W. Tcahan, “Unbounded Length Contexts for PPM”, in Prcoceedings of the IEEE data Compression Conference, Snowbird, Uath , PP, 52-62, 1995.
Davission LD.,, “Universal noiseless coding”, IEEE Trans. Inform. Theory, vol 19, pp.783-795, November 1973.
Even S., “On information lossless autometa of finite order”, IEEE Trans. Electronic Computers, vol EC 1, pp. 561-569 August 1965.
Effros M., “Universal lossless source coding with the Burrows-Wheeler transform”, In Data Compression Conference. IEEE Computer Society TCC,1999
Effros M., “PPM performance with BWT complexity: A new algorithm for lossless data compression”, In Data Compression Conference, Snowbird, UT, March 2000.
Fenwick P., “The Burrows-Wheeler transform for block sorting text compression : Principals and improvements”, The Computer Journal, vol.39,pp.731-740, 1996
Fenwick P., “ The block sorting text compression”, In proc. Australasian Computer Science Conf., Melbourne, Australia, February 1996.
Feygin G. and Chow P., “Minimizing excess code length and VLSI complexity in the multiplication free approximation of arithmetic coding”, in proc. Data Compression Conf., pp. 118-127, March 1993.
Fraenkel A.S., and Klein S.T., “Bi-directional Huffman Coding”, The computer, vol. 33,pp. 158-162,1995.
Girod B.,“Bidrectionally decodable streams of prefix codewords”, IEEE commun. Lett., vol. 3, pp.245-247, August 1999.
Gonzalez Smith M.E., Storer J. A., “Parallel Algorithms for Data Compression”, Journal of ACM, vol 32, pp.344-373, 1985.
Hunter R., and Robinson A.H., “International digital facsimile standards”, Proc. IEEE, vol.68,pp 854-867, July1980.
Huffman A., “ A method for the construction of minimum redundancy codes”, Proc. IRE., vol. 40.pp.1098-1101, September 1952.
Ho S., and Law p., “Efficient hardware-decoding method for modified Huffman code”, Electron, lett., vol. 27, pp.855-856, May 1991.
Hashemian R., “Design and hardware implementation of a memory-efficient Huffman coding”, IEEE Trans. Consumer Electron., vol. 40,pp. 345-351, August 1994.
Hashemian R., “Memory-efficient and high-speed search Huffman coding”, IEEE. Trans. Commun vol. 43, pp. 2576-2581, October 1995.
Howard P., and Vitter j., “Analysis of arithmetic coding for data compression”, Information proceeding and management, vol.28, 1992.
Howard P., and Vitter j., “Practical implementations of arithmetic coding”, In J.A. Storeer editor, Image and text Compression, Kluwer Academic, 1992.
Karp R.M., “Minimum –redundancy coding for the discrete noiseless channel”, IRE Trans. Inform. Theory, vol 17, pp.27-38, January 1961.
Langcon G., “An introduction to arithmetic coding”, IBM J.Res. Develop, vol 28, pp. 135-149, March 1984.
Langcon G. and Rissanen J., “A Simple general binary source code”, IEEE Trans. Inform. Theory, vol 28, pp.800-803, September 1982.
Lakovic K., and Villasenor J., “On design of error-correcting reversible variable length codes”, IEEE commun. Lett., vol 6,pp.337-339, August 2002.
Larsson N.J., “ The Context Trees of Block Sorting Compression”, In Proceedings of the IEEE Data Compression Conf, snowbird, Utah, March 30- April 1, pp. 189- 198, 1998.
Lee J.K.F., “Branch Prediction strageies and branch target buffer design”, IEEE Computer, vol21, pp.6-22, January 1984.
Lempel and Ziv J., “ On the complexity of finite sequences”, IEEE Trans. Inform. Theory, vol 22, pp. 75-81, January 1976.
Manber U., and Mycrs E.W., “Suffix Arrays: A New Method for On-Line String Scarches”, SIAM Journal on Computing, vol22, pp. 935-948, 1993.
Moffat A., “Implementating the PPM data compression scheme”, IEEE Trans. Commun., vol. 38, pp. 1917-1921, November 1990.
Nair R., “Optimal 2-bit branch predictors”, IEEE Transaction on Computers, vol. 44, pp. 698-702, May 1995.
Proakls J.G., “Digital Communication”, 3rd ed New Yark: McGraw Hill, 1998.
Rissanen J., and Langdon G., “Arithmetic Coding”, IBM J.Res Devel., vol. 23,pp. 149-159, March 1999.
Sadakane K., “Text compression using recency rank with context and relation to context sorting, block sorting, and PPM*”, in Proc conf. Compression and complexity of sequences, June 1997.
Sadakane K., “On the optimality of variants of the block sorting compression”, in Proc. Data Compression Conf. Snowbird, UT, pp. 570, March 1998.
Savari S.A., “Redundancy of the Lemple-Ziv incremental parsing rule”, IEEE Trans. Inform. Theory, vol. 43, pp. 9-21, January 1997.
Shield P.,” Universal redundancy rates donot exist”, IEEE Trans. Inform. Theory, vol.39, pp.520-524, March 1993.
Takishima Y., Wada M., and Murakami H., “Reversible variable length codes”, IEEE Trans. Commun., vol. 43, pp. 158-162, 1995.
Tsai C.W., and Wa J.L., “On Constructing the Huffman code-based reversible variable-length codes”, IEEE Trans. Commun., vol. 49, pp. 1506-1509, September 2001.
Williams R.N., “An extremely fast Z-v Lempel data compression algorithm”, Proc. Data Compression Conf, Snowbird, pp. 362-371, 1991.
Walach E., “High efficiency, multiplication free approximation of arithmetic coding”, in Proc .IEEE Data Compression Conf., pp. 43-52, 1991.
Wen J., and Villasenor J.D., “Reversible variable length codes for efficient and robust image and video coding”, in Data Compression Conf.,pp. 471-480, 1998.
Welch T.A., Szymsnski T.G., “Data compression via textual substitution, journal of the ACM., vol 29., pp. 928-951, 1982.
Yeh TY., ‘Alternative implementation of Two-Level Adaptive Branch Prediction”, IEEE Trans. Inform. Theory, vol-32, pp, 124-134, May 1992.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.