Open Access Open Access  Restricted Access Subscription or Fee Access

A Brief Study of Data Compression Algorithms

Yogesh Rathore, Manish K. Ahirwar, Rajeev Pandey

Abstract


Data Compression is the science of representing data in a compact form. For last decades, Data compression has been one of the critical enabling technologies for the ongoing digital data revolution. There are lot of data compression algorithms which are available to compress files of different formats. This paper present survey of several lossless data compression techniques and its corresponding algorithms. A set of selected algorithms are studied and examined. This paper concluded by stating which algorithm performs well for text data.

Keywords


Compression, Encoding, HUFFMAN, HLZ, LZ, LZW, RLE and RLL

Full Text:

PDF

References


Lynch, Thomas J., Data Compression: Techniques and Applications, Lifetime Learning Publications, Belmont, CA, 1985

Philip M Long., Text compression via alphabet representation

Cappellini, V., Ed. 1985. Data Compression and Error Control Techniques with Applications. Academic Press, London.

Cortesi, D. 1982. An Effective Text-Compression Algorithm. BYTE 7,1 (Jan.), 397-403.

Glassey, C. R., and Karp, R. M. 1976. On the Optimality of Huffman Trees. SIAM J. Appl. Math 31, 2 (Sept.), 368-378.

Knuth, D. E. 1985. Dynamic Huffman Coding. J. Algorithms 6, 2 (June), 163-180.

Llewellyn, J. A. 1987. Data Compression for a Source with Markov Characteristics. Computer J. 30, 2, 149-156.

Pasco, R. 1976. Source Coding Algorithms for Fast Data Compression.Ph. D. Dissertation, Dept. of Electrical Engineering, Stanford Univ., Stanford, Calif.

Rissanen, J. J. 1983. A Universal Data Compression System. IEEE Trans. Inform. Theory 29, 5 (Sept.), 656-664.

Tanaka, H. 1987. Data Structure of Huffman Codes and Its Application to Efficient Encoding and Decoding. IEEE Trans. Inform. Theory 33,1 (Jan.), 154-156.

Ziv, J., and Lempel, A. 1977. A Universal Algorithm for Sequential Data Compression. IEEE Trans. Inform. Theory 23, 3 (May), 337-343.

Giancarlo, R., D. Scaturro, and F. Utro. 2009. Textual data compression in computational biology: a synopsis. Bioinformatics 25 (13): 1575-1586.

Burrows M., and Wheeler, D. J. 1994. A Block-Sorting Lossless Data Compression Algorithm. SRC Research Report 124, Digital Systems Research Center.

S. R. Kodifuwakku and U. S. Amarasinge, “Comparison of loosless data compression algorithms for text data”.IJCSE Vol 1 No 4416-225.

Shannon, C.E. (July 1948). "A Mathematical Theory of Communication". Bell System Technical Journal 27: 379–423.

HUFFMAN, D. A. 1952. A method for the construction of minimum-redundancy codes. In Proceedings of the Institute of Electrical and Radio Engineers 40, 9 (Sept.), pp. 1098-1101.

RISSANEN, J., AND LANGDON, G. G. 1979. Arithmetic coding. IBM J. Res. Dev. 23, 2 (Mar.), 149-162.

RODEH, M., PRATT, V. R., AND EVEN, S. 1981. Linear algorithm for data compression via string matching. J. ACM 28, 1 (Jan.), 16-24.

Bell, T., Witten, I., Cleary, J., "Modeling for Text Compression", ACM Computing Surveys, Vol. 21, No. 4 (1989).

DEFLATE64 benchmarks

STORER, J. A., AND SZYMANSKI, T. G. 1982. Data compression via textual substitution. J. ACM 29, 4 (Oct.), 928-951.

Bloom, C., "LZP: a new data compression algorithm", Data Compression Conference, 1996. DCC '96. Proceedings, p. 425 10.1109/DCC.1996.488353.

http://www.ross.net/compression/

"Data Compression Method - Adaptive Coding witih Sliding Window for Information Interchange", American National Standard for Information Systems, August 30, 1994.

LZX Sold to Microsoft

LZO Info

LZMA Accessed on 12/10/2011.

LZMA2 Release Date

Kwong, S., Ho, Y.F., "A Statistical Lempel-Ziv Compression Algorithm for Personal Digital Assistant (PDA)", IEEE Transactions on Consumer Electronics, Vol. 47, No. 1, February 2001, pp 154-162.

David Salomon, Data Compression – The complete reference, 4th ed., page 212

Chernik, K., Lansky, J., Galambos, L., "Syllable-based Compression for XML Documents", Dateso 2006, pp 21-31, ISBN 80-248-1025-5.

Jakobsson, M., "Compression of Character Strings by an Adaptive Dictionary", BIT Computer Science and Numerical Mathematics, Vol. 25 No. 4 (1985). doi>10.1007/BF01936138

Cleary, J., Witten, I., "Data Compression Using Adaptive Coding and Partial String Matching", IEEE Transactions on Communications, Vol. COM-32, No. 4, April 1984, pp 396-402.

Seward, J., "bzip2 and libbzip2", bzip2 Manual, March 2000.

Mahoney, M., "Adaptive Weighting of Context Models for Lossless Data Compression", Unknown, 2002.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.