A Review of Classical Lossless Data Compression Algorithms and Their Contemporary Relevance

• Autorzy: Matusiak Dominik Maciej

Identyfikatory

DOI

10.5604/01.3001.0055.3096

Warianty tytułu

PL

Przegląd klasycznych algorytmów bezstratnej kompresji danych i ich współczesne znaczenie

• Języki publikacji: EN

Abstrakty

EN

Compression is data processing aimed at reducing the amount of information (e.g., for archiving and transfer). There is lossy and lossless compression. Compression algorithms can be either general-purpose or designed for specific types of data (e.g., for sound - including FLAC - Free Lossless Audio Codec, psychoacoustic model + Huffman coding in MP3; image - e.g., DCT, fractal, wavelet compression, RLE, Deflate, LZW; video - e.g., DivX, Cinepak, Indeo; textures in games and programs (e.g., S3TC, NVIDIA Neural Texture Compression), executable files (e.g., UCL). The most commonly used compression algorithm is Deflate (LZ77 + Huffman coding) - it is lossless and general-purpose. Depending on the compression method, there are dictionary algorithms (e.g., LZ77, LZW, LZSS, LZMA, LZ4, BPE, Zstd, Brotli), entropic algorithms (e.g., arithmetic and Huffman coding), predictive algorithms (e.g., PPM), and other types (including RLE, delta encoding). Some of the compression algorithms are patented. Deflate as a standard should be replaced by more efficient algorithms (e.g., Brotli, Zstd, LZMA). The importance of compression is growing due to the general trend towards growth of data.

PL

Kompresja to przetwarzanie danych mające na celu zmniejszenie ilości informacji (np. w celu archiwizacji i przesyłania). Istnieje kompresja stratna i bezstratna. Algorytmy kompresji mogą być ogólnego przeznaczenia lub służyć do określonych typów danych (np. dla dźwięku - w tym FLAC - Free Lossless Audio Codec, model psychoakustyczny + kodowanie Huffmana w formacie MP3; obrazu - np. DCT, kompresja fraktalna, falkowa, RLE, Deflate, LZW; wideo - np. DivX, Cinepak, Indeo; tekstur w grach i programach (np. S3TC, NVIDIA Neural Texture Compression), plików wykonywalnych (np. UCL). Najczęściej stosowanym algorytmem kompresji jest Deflate (LZ77 + kodowanie Huffmana) - jest on bezstratny i ogólnego przeznaczenia. W zależności od metody kompresji istnieją algorytmy słownikowe (np. LZ77, LZW, LZSS, LZMA, LZ4, BPE, Zstd, Brotli), algorytmy entropijne (np. kodowanie arytmetyczne i Huffmana), algorytmy predykcyjne (np. PPM) oraz innego typu (w tym RLE, kodowanie delta). Niektóre algorytmy kompresji są opatentowane. Standard Deflate powinien zostać zastąpiony bardziej wydajnymi algorytmami (np. Brotli, Zstd, LZMA). Znaczenie kompresji rośnie ze względu na ogólny trend wzrostu ilości danych.

Słowa kluczowe

EN

data compression; information entropy; BPE; RLE; Huffman Coding

PL

kompresja danych; entropia informacji; BPE; RLE; kodowanie Huffmana

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Biuletyn Wojskowej Akademii Technicznej
• Rocznik: 2025
• Tom: Vol. 74, No. 2
• Strony: 31--40
• Opis fizyczny: Bibliogr. 55 poz., rys., tab., wykr.

Twórcy

autor

Matusiak Dominik Maciej

• Forvite P.S.A. Laboratory, 5 Lechicka St., 91-230 Łódź, Poland

• https://orcid.org/0000-0003-0177-3411

Bibliografia

• [1] Agustsson E., Tschannen M., Mentzer F., Timofte R.,Gool L. V., Generative Adversarial Networks for Extreme Learned Image Compression, IEEE Xplore, 2019, 221-231.
• [2] Albahadily H. K., Altaay A. A. J., Tsviatkou V. U., Kanapelka V. K., New modified RLE algorithms to compress grayscale images with lossy and lossless compression, IJACSA, 7, 7, 2016, 250-255.
• [3] Al-laham M., Elmary I. M. M., Comparative study between various algorithms of data compression techniques, IJCSNS, 7, 4, 2007, 281-291.
• [4] AQA, Teaching guide: Run-length encoding (RLE), 2020, 1-6, https://filestore.aqa.org.uk/resources/computing/AQA-8525-TG-RLE.PDF.
• [5] Auli-Llinas F., Fast and efficient entropy coding architectures for massive data compression, Technologies, 11, 132, 2023, 1-15.
• [6] Begleiter R., El-Yaniv R., Yona G., On prediction using variable order Markov models, J. Artif. Intell., 22, 2004, 385-421.
• [7] Bhadade U. S., Trivedi A. I., Lossless text compression using dictionaries, IJCA, 13, 8, 2011, 27-34.
• [8] Bommena S., Cyclic Redundancy Check (CRC), Microchip Technology Inc., 2008, 1-12, https://ww1.microchip.com/downloads/en/Appnotes/01148a.pdf.
• [9] Chen J., Fang Y., Khisti A., Özgür A., Shlezinger N., Information Compression in the AI Era: Recent Advances and Future Challenges, JSAC, 43, 7, 2025, 2333-2348.
• [10] Deorowicz S., Second step algorithms in the Burrows-Wheeler compression algorithm, Softw. Pract. Exper., 32, 2, 2002, 99-111.
• [11] Drozdek A., Wprowadzenie do kompresji danych, Wydawnictwa Naukowo-Techniczne, Warszawa 2007.
• [12] Fitriya L. A., Purboyo T. W., Prasasti A. L., A review of data compression techniques, Int. J. Appl. Eng. Res., 12, 19, 2017, 8956-8963.
• [13] Fradet N., Gutowski N., Chhel F., Briot J.P., Byte Pair Encoding for symbolic music, Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023, 2001-2020.
• [14] Gagie T., Manzini G., Move-to-Front, distance coding, and inversion frequencies revisited, Theor. Comput. Sci., 411, 2010, 2925-2944.
• [15] Galle M., Investigating the effectiveness of BPE: The power of shorter sequences, EMNLP-IJCNLP, 2019, 1375-1381.
• [16] Gutierrez-Vasques X., Bentz C., Samardzic T., Languages through the looking glass of BPE compression, Comput. Linguist., 49, 4, 2023, 943-1001.
• [17] Habib A., Islam M. J., Rahman M. S., Huffman based code generation algorithms: data compression perspectives, JCS, 14, 12, 2018, 1599-1610.
• [18] Holtz K., The evolution of lossless data compression techniques, Proceedings of WESCON ‘93, 1993, 140-145.
• [19] Huang H. C., Wu J. L., Windowed Huffman coding algorithm with size adaptation, Proc. IEEE, 1, 140, 1993, 109-113.
• [20] Husseen A. H., Mahmud S. S., Mohammed R. J., Image compression using proposed enhanced Run Length Encoding algorithm, IBN Al-Haitham Journal for Pure and Applied Science, 24, 1, 2011, 1-14.
• [21] InfoQ, Google Snappy - A Fast Compressing Library, 2011, https://www.infoq.com/news/2011/04/Snappy/ [accessed: 10.07.2025].
• [22] ITU, CCITT, V.42bis: Data compression procedures for data circuit-terminating equipment (DCE) using error correction procedures, 1990, 1-29.
• [23] Jain S., Chouhan S.S., Cyclic Redundancy Codes: study and implementation, IJETAE, 4, 4, 2014, 213-217.
• [24] Jayasankar U., Thirumal V., Ponnurangam D., A survey on data compression techniques: From the perspective of data quality, coding schemes, data type and applications, J. King Saud Univ. Comput. Inf., 33, 2021, 119-140.
• [25] Joseph S., Srikanth N., Abhilash J. E. N., A novel approach of modified Run Length Encoding scheme for high speed data communication application, IJSR, 2, 12, 2013, 293-296.
• [26] Kadhim D. J., Mosleh M. F, Abed F. A., Exploring text data compression: a comparative study of adaptive Huffman and LZW approaches, BIO Web of Conferences, 97, 35, 2024, 1-8.
• [27] Kaur K., Saxena J., Singh S., Image compression using Run Length Encoding (RLE), IJRITCC, 5, 5, 2017, 1280-1285.
• [28] Kodituwakku S. R., Amarasinghe U.S., Comparison of lossless data compression algorithms for text data, IJCSE, 1, 4, 2010, 416-425.
• [29] Lehmann T. M., Abel J., Weiss C., The impact of lossless image compression to radiographs, Proc. Of SPIE, 6145, 2006, 290-297.
• [30] Li H., Durbin R., Fast and accurate short read alignment with Burrows-Wheeler transform, Bioinformatics, 25, 14, 2009, 1754-1760.
• [31] Liu W., Mei F., Wang C., O’Neill M., Swartzlander E. E., Data compression device based on modified LZ4 algorithm, IEEE Trans. Consum. Electron., 64, 1, 2018, 110-117.
• [32] Manzini G., The Burrows-Wheeler transform: theory and practice, [in:] M. Kutyłowski, L. Pacholski, T. Wierzbicki (ed.), Mathematical Foundations of Computer Science 1999, Lect. Notes Comput. Sci. 1672, Springer, Berlin, 1999, 34-47.
• [33] Manzini G., An analysis of the Burrows-Wheeler Transform,
• JACM, 48, 3, 2001, 407–430.
• [34] Mogul J.C., Douglis F., Feldmann A., Krishnamurthy B., Potential benefits of delta encoding and data compression for HTTP, ACM SIGCOMM Comp. Com., 27, 4, 1997, 181-194.
• [35] Mustafa S., Xiao H., Comparison of cinepak, intel, microsoft video and indeo codec for video compression, IJMA, 7, 6, 2015, 1-12.
• [36] Oswal S., Singh A., Kumari K., Deflate compression algorithm, IJERGS, 4, 1, 2016, 430-436.
• [37] Patil V., Deshpande S.S., Design of RLE compression algorithm using custom codesign technique for WSN applications, Gedrag Organ., 33, 2, 2020, 2648-2656.
• [38] Parmar C. K., Pancholi K., A review on image compression techniques, J. Inf. Knowl. Res. Electr. Eng., 2, 2, 2012, 281-284.
• [39] Peng J., Kim C. S., Kuo C. C. J., Technologies for 3D mesh compression: A survey, J. Vis. Commun. Image R., 16, 2005, 688-733.
• [40] Pentapati S. K., Philips G., Bovik A. C., Mesh Compression with Quantized Neural Displacement Fields, CGF, 44, 2, 2025, 1-13.
• [41] Rajput A. A., Rajput R. A., Raundale P., Comparative study of data compression techniques, IJCA, 178, 28, 2019, 15-19.
• [42] Salomon D., Data compression, 3rd edition, 2004, Springer, New York.
• [43] Salson M., Lecroq M., Mouchard L., Dynamic Burrows-Wheeler Transform, Proceedings of PSC 2008, Czech Technical University in Prague, 2008, 13-25.
• [44] Salson M., Lecroq T., Leonard M., Mouchard L., A four-stage algorithm for updating a Burrows-Wheeler transform, Theor. Comput. Sci., 410, 2009, 4350-4359.
• [45] Sidhu A. S. S., Garg E. M., Research paper on text data compression algorithm using hybrid approach, IJCSMC, 3, 13, 2014, 1-10.
• [46] Simangunsong P. B. N., A comparative study of image format compression deflate algorithms, IJERT, 6, 12, 2017, 226-231.
• [47] Sayood K., Introduction to data compression, 3rd edition, Morgan Kaufmann/Elsevier, 2016, Amsterdam.
• [48] Starosolski R., Algorytmy bezstratnej kompresji obrazów, Studia Informatica, 23, 4, 51, 2002, 277-300.
• [49] Starosolski R., Algorytmy bezstratnej kompresji danych, Studia Informatica, 24, 1, 52, 2003, 137-158.
• [50] Syed Z. A, Soomro T. R., Compression algorithms: Brotli, Gzip and Zopfli perspective, Ind. J. Sci. Technol., 11, 45, 2018, 1-4.
• [51] Tiwari V. S., Arya A., Chaturverdi S., Scalable prediction by partial match (PPM) and its application to route prediction, Appl. Inform., 5, 4, 2018, 1-16.
• [52] Universal Document Converter, PACKBITS Compression or why we support lossless TIFF compression method?, https://www.universal-document-converter.com/news/pack-bits-tiff-i2498.html [accessed: 27.07.2024].
• [53] Willems F. M. S., Shtarkov Y. M., Tjalkens T. J., The Context-Tree Weighting methods: basic properties, IEEE T. Inform. Theory., 41, 3, 1995, 653-664.
• [54] Yang Y., Mandt S., Theis L., An introduction to neural data compression, Found. Trends Comput. Graph. Vis., 15, 2, 2023, 113-200.
• [55] Yoyti A., Gupta G., Gupta K.L., An advanced comparison approach with RLE for image compression, IJARCSSE, 4, 2, 2014, 95-99.