Algorytmy bezstratnej kompresji danych

• Autorzy: Starosolski R.

Warianty tytułu

EN

Lossless data compression algorithms

• Języki publikacji: EN

Abstrakty

EN

In this paper, after presenting basic definitions and methods concerning lossless data compression, we describe basic universal lossless data compression algorithms that although regarded as classical, are still commonly used. We describe: Huffman Coding, Arithmetic Coding, Run Length Encoding and selected dictionary compression algorithms. We also describe important variants and present examples of the above-mentioned algorithms.

PL

W artykule, po omówieniu podstawowych pojęć i metod dotyczących bezstratnej kompresji danych, przedstawiono podstawowe uniwersalne algorytmy kompresji, które, chociaż uznawane już za klasyczne, są nadal powszechnie stosowane. Omówiono algorytmy: Huffmana, kodowania arytmetycznego, kodowania długości sekwencji oraz wybrane algorytmy słownikowe. Omówiono również istotne warianty ww. algorytmów oraz przedstawiono przykłady ilustrujące ich działanie.

Słowa kluczowe

EN

universal compression algorithms; lossless data compression; coding; information theory

PL

uniwersalne algorytmy kompresji; bezstratna kompresja danych; kodowanie; teoria informacji

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2003
• Tom: Vol. 24, nr 1
• Strony: 137--158
• Opis fizyczny: Bibliogr. 28 poz.

Twórcy

autor

Starosolski R.

• Politechnika Śląska, Instytut Informatyki, ul. Akademicka 16, 44-101 Gliwice, Polska

Bibliografia

• 1. Drozdek A.: Wprowadzenie do kompresji danych. WNT, Warszawa 1999.
• 2. Fiala E. R., Greene D. H.: Data Compression with Finite Windows. Communications of the ACM, Apr. 1989, Vol. 32(4), pp. 490-505.
• 3. Gallager R. G.: Variations on a theme of Huffman. IEEE Transactions on Information Theory, ГГ-24,1978, pp. 668-74.
• 4. Huffman D. A.: A method for the construction of minimum-redundancy codes. Proceedings of the Institute of Radio Engineers 40(9), 1952, pp. 1098-101.
• 5. Howard P. G., Vitter J. S.: Analysis of arithmetic coding for data compression. Information Processing & Management, Great Britain 1992, Vol. 28(6), pp. 749-63.
• 6. Howard P. G., Vitter J. S.: Practical Implementations of Arithmetic Coding, rozdział w: Storer J. A., Image and text compression. Kluwer Academic Publishers 1992, pp. 85-112.
• 7. Howard P. G., Vitter J. S.: Arithmetic Coding for Data Compression. Proceedings of the IEEE, June 1994 USA, Vol. 82(6), pp. 857-65.
• 8. Knuth D. E.: Dynamic Huffman coding. Journal of Algorithms, Vol 6, 1985, pp. 163-80.
• 9. Lei S.-М.: On the finite-precision implementation of arithmetic codes. Journal of Visual Communication and Image Representation, March 1995 USA, Vol. 6(1), pp. 80-8.
• 10. Migas A.: Kompresja danych. Charakterystyka metody LZW. Zeszyty Naukowe Politechniki Śląskiej, Nr 1306, seria Informatyka z. 29, Wydawnictwo Politechniki Śląskiej, Gliwice 1995, ss. 95-116.
• 11. Moffat A., Neal R. M., Witten I. H.: Arithmetic Coding Revisited. ACM Transactions on Information Systems 1998, Vol. 16(3), pp. 256-94.
• 12. Rissanen J.: Universal Coding, Information, Prediction, and Estimation. IEEE Transactions on Information Theory, July 1984, Vol. 30(4), pp. 629-36.
• 13. Rissanen J., Landgon G. G.: Universal Modeling and Coding. IEEE Transactions on Information Theory, January 1981, Vol. 27(1), pp. 12-23.
• 14. Rissanen J., Landgon G. G.: A General Approach to Data Compression: Binary Arithmetic Codes. IBM Research Report RJ 7443, March 1990, IBM Almaden Research Center, San Jose, CA, USA.
• 15. Sayood K.: Kompresja danych wprowadzenie. RM, Warszawa 2002.
• 16. Shannon C. E.: A Mathematical Theory of Communication. Bell System Technical Journal, 1948, Vol. 27, pp. 379-423, 623-56.
• 17. Skarbek W.: Metody reprezentacji obrazów cyfrowych. Akademicka Oficyna Wydawnicza PLJ, Warszawa 1993.
• 18. Praca zbiorowa pod redakcją W. Skarbka: Multimedia algorytmy i standardy kompresji. Akademicka Oficyna Wydawnicza PLJ, Warszawa 1998.
• 19. Stuiver L., Moffat A.: Piecewise Integer Mapping for Arithmetic Coding. Proceedings of the IEEE Data Compression Conference (DCC'98), USA 1998, pp. 3-12.
• 20. Storer J. A., Szymański T. G.: Data compression via textual substitution. Journal of the Association for Computing Machinery, vol.29, no. 4, October 1982, USA, pp. 928-51.
• 21. Starosolski R.: Algorytmy bezstratnej kompresji obrazów. Studia Informatica, Vol. 23, Nr 4(51), Gliwice 2002, ss. 277-300.
• 22. Starosolski R.: Nowoczesne algorytmy bezstratnej kompresji danych. Studia Informatica, Vol. 24, Nr 1(52), Gliwice 2003, ss. 159-69.
• 23. Thomas S., Orost J.: Compress (version 4.0) program and documentation. 1985.
• 24. Vitter J. S.: Design and Analysis of Dynamic Huffman Codes. Journal of the ACM, Vol. 34(4), October 1987, pp. 825-45.
• 25. Vitter J. S.: Algorithm 673: Dynamic Huffman Coding. ACM transactions on Mathematical Software, Vol. 15(2), 1989, pp. 158-67.
• 26. Witten I. H., Moffat A., Bell T. C.: Managing Gigabytes. Van Nostrand Reinhold, 1994.
• 27. Ziv J., Lempel A.: A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, Vol. 32(3), May 1977, pp. 337-43.
• 28. Ziv J., Lempel A.: Compression of individual sequences via variable rate coding. IEEE Transactions on Information Theory, Vol. 24(5), Sept. 1978, pp. 530-6.