Search

Namen diplomskega dela je bil predstaviti temeljne algoritme za brezizgubno stiskanje podatkov in jih med seboj testirati. V teoretičnem delu najprej na splošno govorimo o značilnostih kodiranja podatkov. Tukaj razjasnimo razlike med več vrstami kod in se podrobneje osredotočimo na kode VLC. Omenjena je tudi informacijska teorija, pri čemer razložimo, zakaj je pomemben element na področju kodiranja. Nato se poglobimo v razlago dejanskih algoritmov, in sicer začnemo s statističnimi algoritmi, kjer opišemo delovanje Shannon-Fanojevega kodiranja, Huffmanovega kodiranja in aritmetičnega kodiranja. Potem preidemo na algoritme, ki dosegajo stiskanje s pomočjo slovarja, in opišemo prvotna algoritma LZ77 in LZ78 ter njuni varianti LZSS in LZW. Za konec opišemo še algoritem Burrows-Wheeler, ki združuje transformaciji Burrows-Wheeler in premakni-na-začetek z entropijskim kodiranjem. V praktičnem delu začnemo z implementacijo algoritmov Huffmanovega kodiranja, aritmetičnega kodiranja, LZSS, LZW in Bzip2. Algoritme implementiramo z odprtokodnimi implementacijami v programskem jeziku Java in za testiranje uporabimo sistem ALGator. Teste izvajamo na več znanih testnih zbirkah, ki so nastale z namenom testiranja brezizgubnega stiskanja. Te zbirke so Calgary, Canterbury, Silesia in Maximum. Po končanem testiranju rezultate primerjamo med seboj in ugotovimo učinkovitost implementiranih algoritmov. The purpose of the thesis is to present the fundamental lossless data compression algorithms, test and compare them. The theoretical part outlines some of the general characteristics of data coding and explores in more detail the differences between different types of codes, particularly VLC codes. Moreover, it touches on the information theory and explains why it plays an important role in coding. It also thoroughly explains actual algorithms, starting with statistical algorithms to describe the functioning of Shannon-Fano coding, Huffman coding and arithmetic coding. Next are algorithms that achieve compression using a dictionary, i.e. algorithms LZ77 and LZ78 and their respective variants LZSS and LZW. The last algorithm presented is the Burrows-Wheeler algorithm that involves the Burrows-Wheeler transformation and move-to-front transformation with entropy coding. As for the practical part, it deals with the implementation and testing of algorithms for Huffman coding, arithmetic coding, LZSS, LZW and Bzip2. The algorithms are implemented with open source implementations in the Java programming language. The ALGator system is used for testing them. The tests are performed on several widely known test collections that were developed for testing lossless compression. Those collections are Calgary, Canterbury, Silesia and Maximum. The comparison of test results determines the effectiveness of the implemented algorithms.

V diplomskem delu obravnavamo problem podgrafnega izomorfizma in njegovo integracijo v sistem ALGator. Iskanje izomorfnih podgrafov je dandanes prisotno na večih znanstvenih področjih, zato se vseskozi pojavljajo novi algoritmi za reševanje problema. Podrobneje smo opisali Ullmannov algoritem, izboljšani Ullmannov algoritem in algoritem RI, ki je najnovejši izmed naštetih. Njihove implementacije, katere so primerne za iskanje izomorfizmov tako na usmerjenih kot neusmerjenih neoznačenih grafih, smo zaradi integracije v sistem ALGator napisali v programskem jeziku Java. Sistem je namenjen predvsem raziskovalcem na področju razvoja algoritmov, saj omogoča enostavno testiranje njihove učinkovitosti in analizo pridobljenih rezultatov. Funkcionalnosti sistema smo v praksi uporabili na izbranemu problemu. Poleg definicije problema smo v projekt v ALGator-ju vključili vse implementirane algoritme (izboljšani Ullmannov algoritem je podan v dveh različicah) in opazovali njihovo učinkovitost. Eksperiment smo izvedli na več kot 50000 različnih parih grafov. Z analizo rezultatov v ALGator-ju smo pokazali, da je algoritem RI v primerjavi z ostalimi tremi algoritmi najhitrejši. Na drugi strani se je najslabše izkazal Ullmannov algoritem, njegovi izboljšani različici pa sta se v določenih scenarijih celo približala algoritmu RI. Z integracijo problema v sistem ALGator smo predstavili njegove zmogljivosti in navedli predloge za izboljšave. This thesis deals with a subgraph isomorphism problem and its integration into ALGator system. Detection of isomorphic subgraph is present in many scientific fields nowadays, therefore new problem solving algorithms constantly appear. We focus on a detailed description of Ullmann algorithm, improved Ullmann algorithm and RI algorithm, the most recent among listed. Those algorithms, which are suitable for isomorphism detection in directed or undirected unlabeled graphs, were implemented in Java programming language for the purpose of integration into ALGator. The system is intended for the use of algorithm development researchers, providing simplified testing of algorithm's efficiency and analysis of testing results. We have applied system functionalities on the selected problem. In addition to a problem definition we have included all the implemented algorithms into ALGator project (improved Ullmann algorithm is given in two versions) and observed their efficiency. We have executed the experiment on more than 50000 different pairs of graphs. The analysis of testing results with ALGator shows, that RI algorithm is the fastest one among all four algorithms. On the other hand Ullmann algorithm performed the worst, while the performance of its improved versions were even comparable with RI algorithm in certain scenarios. By integrating the problem into ALGator we have presented its capabilities and proposed some improvements.