Nowoczesne algorytmy bezstratnej kompresji danych

Starosolski, R.

Artykuł - szczegóły

Tytuł artykułu

Nowoczesne algorytmy bezstratnej kompresji danych

Autorzy

Starosolski R.

Identyfikatory

Warianty tytułu

Modern lossless data compression algorithms

Języki publikacji

Abstrakty

W niniejszym artykule omówiono zwięźle kilka nowoczesnych algorytmów z zakresu bezstratnej kompresji danych: algorytm predykcji przez częściowe dopasowanie, algorytm ważenia drzewa kontekstów, algorytm Burrowsa-Wheelera oraz algorytm Wolfa i Willemsa. Pod względem uzyskiwanych współczynników kompresji algorytmy te uznawane są obecnie za najlepsze wśród uniwersalnych algorytmów bezstratnej kompresji danych.

In this paper we present a brief overview of four modern lossless data compression algorithms: Prediction by Partial Matching, Context Tree Weighting, Burrows-Wheeler Block Sorting Compression Algorithm and the Switching Method of Volf and Willems. In terms of average compression ratio presented algorithms are regarded as best among universal lossless data compression algorithms.

Słowa kluczowe

bezstratna kompresja danych modelowanie predykcja przez częściowe dopasowanie ważenie drzewa kontekstów algorytm Burrowsa-Wheelera algorytm Wolfa i Willemsa

lossless data compression data modeling PPM CTW Bunows-Wheeler Block Sorting switching Method of Volf and Willems

Wydawca

Wydawnictwo Politechniki Śląskiej

Czasopismo

Studia Informatica

Rocznik

2003

Tom

Vol. 24, nr 1

Strony

159--169

Opis fizyczny

Bibliogr. 35 poz.

Twórcy

autor

Starosolski R.

rstaros@star.iinf.polsl.gliwice.pl

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

Bibliografia

1. Arnavut Z., Magliveras S, S.: Block Sorting and Compression. Proceedings of the Data Compression Conference DCC'97, USA, March 1997, pp. 181-90.
2. Aberg J., Shtarkov Y. M.: Text Compression by Context Tree Weighting. Proceedings of the IEEE Data Compression Conference (DCC'97), USA 1997, pp. 377-86.
3. Balkenhol B., Kurtz S.: Universal Data Compression Based on the Burrows-Wheeler Transformation: Theory and Practice. IEEE Trans, on Computers, Oct. 2000, Vol.49(10).
4. Balkenhol B., Kurtz S., Shtarkov Y. M.: Modifications of the Burrows and Wheeler Data Compression Algorithm. Proceedings of the Data Compression Conference DCC'99, USA, March 1999, pp. 188-97.
5. Bentley J. L., Sleator D. D., Tatjan R. E., Wei V. K.: A Locally Adaptive Data Compression Scheme. Communications of the ACM, Apr. 1986, Vol. 29(4), pp. 320-30.
6. Bunton S.: Semantically Motivated Improvements for PPM Variants. The Computer Journal, Great Britain 1997, Vol. 40(2-3), pp. 76-93.
7. Burrows M., Wheeler D. J.: A block-sorting lossless data compression algorithm. SRC Research Report 124, Systems Research Center, Digital Equipment Corporation, Palo Alto, CA, USA, May 1994.
8. Bell T., Witten I. H., Cleary J. G.: Modelling for text compression. ACM Computing Surveys, Vol. 21(4), 1989, pp. 557-591.
9. Cleary J. G., Teahan W. J.: Experiments on the Zero Frequency Problem. Proceedings of the IEEE Data Compression Conference (DCC'95), USA, March 1995, pp. 480.
10. Cleary J. G., Teahan W. J.: Unbounded length contexts for PPM. Computer Journal, Great Britain 1997, Vol. 40(2-3), pp. 67-75.
11. Cleary J. G., Teahan W. J., Witten I. H.: Unbounded length contexts for PPM. Proc, of the Data Compression Conference (DCC'95), USA, March 1995, pp. 52-61.
12. Deorowicz S.: Improvements to Burrows-Wheeler compression algorithm. Software - Practice and Experience, Vol. 30(13). September 2000, pp. 1465-83.
13. Deorowicz S.: Second step algorithms in the Burrows-Wheeler compression algorithm. Software - Practice and Experience, Vol. 32(2), 2002, pp. 99-111.
14. Deorowicz S.: Universal lossless data compression algorithms. Rozprawa doktorska, Institute of Computer Science, Silesian University of Technology, Gliwice, 2003.
15. Drozdek A.: Wprowadzenie do kompresji danych. WNT, Warszawa 1999.
16. Effros M.: Universal Lossless Source Coding with the Burrows Wheeler Transform. Proceedings of the Data Compression Conference DCC'99, USA 1999, pp. 178-87.
17. Fenwick P.: Block Sorting Text Compression. Proceedings of the 19th Australian Computer Science Conference, Melbourne, Australia 1996, pp. 193-202.
18. Fenwick P.: The В arrows-Wheeler Transform for block sorting text compression: principles and improvements. The Computer Journal, 1996, Vol. 39(9), pp. 731-40.
19. Hoang D. T.: Fast and Efficient Algorithms for Text and Video Compression. Rozprawa doktorska, Department of Computer Science, Brown University, Providence, Rhode Island 02912, May 1997.
20. Howard P. G.: The design and analysis of efficient lossless data compression systems. Rozprawa doktorska, Department of Computer Science, Brown University, Providence, Rhode Island 02912, June 1993.
21. Moffat A.: Implementing the PPM data compression scheme. IEEE Transactions on Communications, 1990, Vol. 38(11), pp. 1917-21. .
22. Sayood K.: Kompresja danych wprowadzenie. RM, Warszawa 2002.
23. Skarbek W.: Metody reprezentacji obrazów cyfrowych. Akademicka Oficyna Wydawnicza PLJ, Warszawa 1993.
24. Praca zbiorowa pod redakcją W. Skarbka: Multimedia algorytmy i standardy kompresji. Akademicka Oficyna Wydawnicza PLJ, Warszawa 1998.
25. Sadakane K., Okazaki T., Imai H.: Implementing the Context Tree Weighting Method for Text Compression. Proceedings of the IEEE Data Compression Conference (DCC'2000), USA 2000, pp. 123-32.
26. Starosolski R.: Algorytmy bezstratnej kompresji obrazów. Studia Informatica, Vol. 23, Nr 4(51), Gliwice 2002, ss. 277-300.
27. Starosolski R.: Algorytmy bezstratnej kompresji danych. Studia Informatica, Vol. 24, Nr 1(52), Gliwice 2003, ss. 137-58.
28. Teahan W. J., Cleary J. G.: The Entropy of English Using PPM-based Models. Proceedings of the IEEE Data Compression Conference (DCC'96), USA 1996, pp. 53-62.
29. Teahan W. J., Inglis S., Cleary J. G., Holmes G.: Correcting English text using PPM models. Proceedings of the IEEE Data Compression Conference (DCC'98), March-April 1998, pp. 289-98.
30. Tjalkens T. J., Volf P. A. J., Willems F. M. J.: A Context-Tree Weighting Method for Text Generating Sources. Proceedings of the IEEE Data Compression Conference (DCC'97), USA 1997, pp. 472.
31. Volf P. A. J., Willems F. M. J.: Switching Between Two Universal Source Coding Algorithms. Proceedings of the EEEE Data Compression Conference DCC'98, USA, March 1998, pp. 491-500.
32. Volf P. A. J., Willems F. M. J.: The Switching Method: Elaborations. Proceedings of the 19th Symposium on Information Theory in the Benelux, Veldhoven, The Netherlands, May 1998, pp. 13-20.
33. Witten I. H., Moffat A., Bell T. C.: Managing Gigabytes. Van Nostrand Reinhold, 1994.
34. Willems F. M. J., Shtarkov Y. M., Tjalkens T. J.: The Context Tree Weighting Method: Basic Properties. IEEE Trans, on Information Theory, May 1995, Vol. 41, pp.653-64.
35. Willems F., Shtarkov Y., Tjalkens T.: Reflections on „The Context-Tree Weighting Method: Basic Properties”. IEEE Information Theory Society Newsletter, Vol. 47, March 1997, pp. 20-7.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-a1ad204a-ba49-4a31-bb67-d6ab7afce496