Analiza algoritmilor de compresie fără pierderi de date bazați pe dicționar

Abstract

Teza de master propusă cercetează domeniul algoritimilor de compresie fără pierderi de date, accentuându-se pe algoritmi bazați pe dicționar. Lucrarea este compusă din lista de abrevieri, introducerea, trei capitole, concluzii, bibliografia din 21 de titluri și 8 anexe. Capitolul “ANALIZA DOMENIULUI PRIVIND ALGORITMI DE COMPRESIE FĂRĂ PIERDERI DE DATE BAZAȚI PE DICȚIONAR” descrie algoritmi care vor fi cercetate – LZ77, LZSS, LZ78, LZW, LZMW și LZAP. Sunt descrise în detalii modul de lucru a metodelor de compresie și decompresie și structurile de date utilizate; sunt evidențiate avantajele și dezavantajele fiecărui algoritm. Capitolul oferă exemple de utilizare practică a algoritmilor, precum aplicații și formate de fișiere. Scopul capitolului este de a oferi o bază teoretică solidă pentru implementarea algoritmilor. Capitolul “METODE PRIVIND IMPLEMENTAREA ALGORITMILOR DIN DOMENIUL DE STUDIU” detaliază procesul de implementare a algoritmilor în limbajul de programare C++, utilizând o arhitectură modulară bazată pe clase. Limbajul C++ a fost ales pentru eficiența sa și pentru capacitățile extinse de manipulare a fișierelor și datelor. În cadrul aplicației dezvoltate fiecare algoritm este definit printr-o clasă specifică, iar testele sunt realizate printr-o interfață text simplă. Implementarea se concentrează pe crearea unui instrument flexibil, capabil să comprime și să decomprimate fișiere utilizând diferiți algoritmi, măsurând în același timp performanța acestora. Capitolul “ANALIZA ALGORITMILOR CU APLICAȚIA ELABORATĂ” analizează performanța algoritmilor cu ajutorul aplicației create prin testarea lor pe colecții diferite de fișiere diverse, cum ar fi texte, imagini și fișiere binare. Sunt evaluate rata de compresie și viteza procesului, iar rezultatele sunt comparate pentru a evidenția situațiile în care fiecare algoritm excelează.

The proposed master's thesis researches the field of lossless compression algorithms, focusing on dictionary-based algorithms. The work is composed of the list of abbreviations, the introduction, three chapters, conclusions, the bibliography of 21 titles and 8 appendices. The chapter «DOMAIN ANALYSIS OF DICTIONARY BASED LOSSLESS COMPRESSION ALGORITHMS» describes algorithms that will be studied - LZ77, LZSS, LZ78, LZW, LZMW and LZAP. The working process of the compression and decompression methods and data structures used are described in detail. The advantages and disadvantages of the algorithm are highlighted. The chapter provides examples of practical use of the algorithms, as well as applications and the file formats. The aim of the chapter is to provide a solid theoretical basis for implementing algorithms. The chapter «METHODS REGARDING THE IMPLEMENTATION OF ALGORITHMS IN THE FIELD OF STUDY» details the process of implementing algorithms in the C++ programming language, using a modular architecture based on classes. The C++ language was chosen for its efficiency and extensive file and data manipulation capabilities. Within the developed application, each algorithm is defined by a specific class, and the tests are performed through a simple text interface. The implementation focuses on creating a flexible tool capable of compressing and decompressing files using different algorithms while measuring their performance. The chapter «ANALYSIS OF ALGORITHMS WITH ELABORATE APPLICATION» analyzes the performance of algorithms with the help of the application created by testing them on different collections of various files such as texts, images and binary files. Compression rate and process speed are evaluated, and results are compared to highlight situations where each algorithm excels.