Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
% arara: pdflatex
% arara: pdflatex
% arara: pdflatex
% options:
% thesis=B bachelor's thesis
% thesis=M master's thesis
% czech thesis in Czech language
% slovak thesis in Slovak language
% english thesis in English language
% hidelinks remove colour boxes around hyperlinks
\documentclass[thesis=B,czech]{FITthesis}[2012/06/26]
\usepackage[utf8]{inputenc} % LaTeX source encoded as UTF-8
\usepackage{graphicx} %graphics files inclusion
\usepackage[]{algorithm2e}
\usepackage{listings}
\usepackage{float}
% \usepackage{amsmath} %advanced maths
% \usepackage{amssymb} %additional math symbols
\usepackage{dirtree} %directory tree visualisation
% % list of acronyms
% \usepackage[acronym,nonumberlist,toc,numberedsection=autolabel]{glossaries}
% \iflanguage{czech}{\renewcommand*{\acronymname}{Seznam pou{\v z}it{\' y}ch zkratek}}{}
% \makeglossaries
\newcommand{\tg}{\mathop{\mathrm{tg}}} %cesky tangens
\newcommand{\cotg}{\mathop{\mathrm{cotg}}} %cesky cotangens
\newcommand{\classname}[1]{\texttt{#1}}
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
% ODTUD DAL VSE ZMENTE
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
\department{Katedra softwarového inženýrství}
\title{Implementace kompresních metod LZ77, LZ78, LZW v~jazyce Java}
\authorGN{Ladislav} %(křestní) jméno (jména) autora
\authorFN{Zemek} %příjmení autora
\authorWithDegrees{Ladislav Zemek} %jméno autora včetně současných akademických titulů
\author{Ladislav Zemek} %jméno autora bez akademických titulů
\supervisor{Ing. Radomír Polách}
\acknowledgements{Rád bych poděkoval Ing. Radomírovi Poláchovi za pomoc a vstřícnost při vedení bakalařské práce.}
\abstractCS{Tato bakalářská práce se~zabývá návrhem, analýzou, implementací a~testováním tří kompresních metod LZ77, LZ78 a~LZW do~knihovny SCT. Knihovna je koncipována tak, aby v~budoucnu nabídla uživatelům velkou škálu kompresních metod a~tak usnadnila výběr vhodné metody pro jejich projekt. Uvnitř této práce se zabývám popisem a vhodnou implementací daných algoritmů. U~všech metod se mi podařilo při vhodně zvolených parametrech dosáhnout zmenšení testovaných korpusů vždy alespoň o~25~\%. Přínosem této práce je přispění do knihovny, která může usnadnit vývojářům práci s kompresními metodami.}
\abstractEN{This bachelor thesis deals with the design, analysis, implementation and~testing of~three compression methods LZ77, LZ78 and~LZW in~the~SCT library. The~library is designed to~offer users a~wide range of~compression methods to~facilitate the~choice of~the~right method for their project. Inside this thesis I~deal with suitable design and~description of~given algorithms. For all methods, I~managed to~reduce the tested corpuses with~appropriately selected parameters at~least by~25~\%. The benefit of~this work is contributing to a~library that can make it easier for developers to work with compression metod.}
\placeForDeclarationOfAuthenticity{V~Praze}
\declarationOfAuthenticityOption{4} %volba Prohlášení (číslo 1-6)
\keywordsCS{Komprese dat, dekomprese dat, Java, LZ77, LZ78, LZW, SCT}
\keywordsEN{Compression, decompression, LZ77, LZ78, LZW, SCT}
%\website{https://gitlab.fit.cvut.cz/zemeklad/BP} %volitelná URL práce, objeví se v tiráži - úplně odstraňte, nemáte-li URL práce
\begin{document}
%\newacronym{CVUT}{{\v C}VUT}{{\v C}esk{\' e} vysok{\' e} u{\v c}en{\' i} technick{\' e} v Praze}
%\newacronym{FIT}{FIT}{Fakulta informa{\v c}n{\' i}ch technologi{\' i}}
\begin{introduction}
V~době, kdy se začali počítače rozšiřovat do~běžného života, vznikla potřeba ukládat čím dál větší objem dat. Z~dnešního pohledu to nevypadá jako problém, jednoduše si uložíte několika gigabytový soubor na svůj pevný disk, který má kapacitu stovky gigabytů. Dříve ovšem měli pevné disky kapacitu jen desítky megabytů, což je téměř sto tisíckrát méně než dnes. Paměti tedy rozhodně nebylo nazbyt. Proto bylo potřeba data nějakým způsobem zmenšit a tím šetřit místo na disku. Samozřejmě za předpokladu, že nedojde ke~ztrátě informací.
Právě za tímto účelem vznikla bezztrátová komprese dat, která zakóduje data pomocí důmyslných algoritmů. Nová data pak mají výrazně menší velikost než ta původní.\cite{komprese} Jsou tedy vhodnější pro uložení na~disk nebo k~odeslání přes internet. Data je následně možné dekódovat pomocí dekomprese, což je inverzní operace ke kompresi. Výstupem dekomprese jsou původní data.
Jelikož v~knihovně SCT nejsou naimplementovány zmíněné algoritmy, rozhodl jsem se je do knihovny doplnit.
\end{introduction}
\chapter{Pojmy}
V~této kapitole bych rád vysvětlil a definoval některé pojmy.
\begin{itemize}
\item \textbf{Komprese/komprimace dat} -- Zmenšování objemu dat.
\item \textbf{Bezztrátová komprese dat} -- Komprese dat, při které nedochází ke ztrátě informace.
\item \textbf{Dekomprese/dekomprimace dat} -- Inverzní operace ke kompresi. Ze zmenšených dat obnoví původní.
\item \textbf{Triplet} -- V~této bakalářské práci je tripletem myšlena jakákoliv n-tice. Je tomu tak proto, že v~knihovně SCT je každá n-tice zpracovávána pomocí třídy TripletProcessor. Neznamená to tedy vždy trojici (LZ77). V~závislosti na metodě může jít i o~dvojici (LZ78) nebo jednici (LZW).
\item \textbf{Adaptivní kompresní metoda} -- Tyto metody si vytváří struktůry za běhu programu v~závislosti na vstupních datech. Vytvořené struktůry jsou používá ke komprimaci dat a není potřeba je ukládat společně s~daty.\cite{pojmy}
\item \textbf{Slovníkové kompresní metody} -- Tyto metody používají pro komprimaci slovník, který v~průběhu komprimace i dekomprimace roste přidáváním nových frází. Proto patří slovníkové metody mezi adaptivní kompresní metody.\cite{pojmy}
\item \textbf{Symetrická kompresní metoda} -- Komprimace i dekomprimace má stejnou složitost.\cite{pojmy}
\item \textbf{Asymetrická kompresní metoda} -- Komprimace i dekomprimace má odlišnou složitost.\cite{pojmy}
\item \textbf{Entropie} -- Míra neurčitosti systému.\cite{entropie} V kontextu této práce se jedná o míru náhodnosti dat.
\item \textbf{Řetězec} -- Posloupnost symbolů z abecedy.
\item \textbf{Délka řetězce} -- Počet symbolů v řetězci.
\item \textbf{Korpus} -- Soubor dat vytvořený pro účely testování kompresních metod.
\item \textbf{Kompresní poměr} -- Udává efektivitu s jakou se podařilo zkomprimovat data. Vypočte se jako: $$ K = \frac{v_{k}}{v} $$
Kde $v_{k}$ je velikost dat po kompresi a $v$ je velikost původních dat. Pokud je hodnota $ K < 1 $, pak byl soubor zmenšen. Pokud je $ K \geq 1 $, data se nezmenšil a komprese byla neúspěšná.
Cílem této bakalářské práce je seznámení se s~kompresními algoritmy LZ77, LZ78, LZW a~jejich následná implementace do knihovny SCT (Small Compression Toolkit). Součástí této práce je také jejich otestování z~hlediska časové a~paměťové náročnosti, případně porovnání efektivity s ostatními implementovanými metodami. Knihovna SCT by pak měla ušetřit práci programátorům, kteří díky ní nebudou muset vymýšlet vlastní implementaci těchto algoritmů.
Jedná se o~poměrně zastaralé metody, které vznikly v~80.~letech 20.~století a~dnes je již v~efektivitě překonávají jiné. Nicméně metodu LZ77 je možné použít například v~programu CRUSH.\cite{crush} Z~LZ77 bylo odvozeno mnoho dalších kompresních algoritmů, které jsou velmi často používány. LZ78 byla taktéž předlohou pro jiné algoritmy například LZW nebo LZMA. \cite{inspire} Samotná se příliš nevyužívá, protože nedosahuje tak dobrého komprimačního poměru. Naopak metoda LZW bývala poměrně hojně využívá při komprimaci monochromatických obrázků a~obecně je velmi efektivní tam, kde se opakuje velké množství dat. LZW se používala v~dřívějších verzích formátu PDF, později byla nahrazená efektivnějším algoritmem.\cite{lzwEN} Tyto algoritmy patří mezi základní kompresní metody a~jelikož je hlavním cílem SCT poskytnout co největší spektrum kompresních algoritmů, rozhodl jsem se je do knihovny doimplementovat.
\section{Analýza požadavků}
V~této části bych se rád věnoval požadavkům, které mi zadal vedoucí práce a jejich analýze. Každý softwarový projekt by měl začínat analýzou toho, co si zákazník přeje, aby program dělal nebo dodržoval. Požadavek musí být proveditelný, testovatelný a také musí byt definovaný dostatečné detailně pro účely návrhu.\cite{req} Obvykle se požadavky dělí na funkční a nefunkční.
\subsection{Funkční požadavky}
Funkční požadavky objasňují, jaké má mít požadovaný software funkce, co má umět a jak se má chovat v~daných situacích. Podle zadání a diskuse s~vedoucím práce jsem určil tyto požadavky jako funkční:
\begin{itemize}
\item \textbf{Implementace LZ77, LZ78, LZW}
\item \textbf{Dekomprese} -- Práce zahrnuje i implementaci dekompresních algoritmů ke všem zmíněným metodám.
\item \textbf{Parametry} -- Algoritmům bude možné změnit jejich parametry, jako je například veliskost bufferů, počet prvků ve slovníku nebo jak velké části souboru se budou komprimovat najednou. Parametry bude možné měnit při spouštění přes příkazovou řádku a nebo přímo v knihovně pomocí tříd, které poskytují parametry metodám.
\item \textbf{Komprimace po částech} -- Algoritmy budou schopné rozdělit soubor na menší části a ty pak komprimovat. Dekomprimace bude probíhat nad celým souborem ne po častech, nicméně algoritmy budou schopny dekomprimovat i soubor, který byl předtím zakomprimován po částech. Velikost částí si určí uživatel pomocí parametru, případně využije výchozích nastavených hodnot.
\item \textbf{Spustitelnost} -- Program bude možné pustit se zvolenými parametry z~příkazové řadky. Nepůjde tedy pouze o~implementaci metod do knihovny, ale i~o~vytvoření jejich klienta, kterého bude možné prakticky využít.
\end{itemize}
\subsection{Nefunkční požadavky}
Nefunkční požadavky, jsou takové požadavky, které přímo neříkají, co má program umět. Jedná se převážně o~omezující nebo zpřesňující podmínky, kterými se má návrh řídit. Tyto požadavky jsem určil jako nefunkční:
\begin{itemize}
\item \textbf{Knihovna SCT} -- Implementace bude provedena do knihovny SCT.\cite{sct} Kód této open-source knihovny je dostupná na fakultním gitlabu.
\item \textbf{Triplety} -- Program bude pro ukládání dat do souboru využívat již naimplementované metody třídy TripletProcesor a pro definování jednotlivých složek v~tripletu třídu TripletFieldId.
\item \textbf{Velikostí slovníků a bufferů} -- Aby nedocházelo k~nekontrolovatelnému růstu slovníku a tím i k~zvyšování pamětové i časové náročnosti, budou mít algorytmy LZ78 a LZW parametr, který zhora omezí počet prvků ve slovníku. U~metody LZ77 bude pomocí dvou parametrů omezeno prohlížecí i aktuální okénko.
\item \textbf{Velikosti prvků v~tripletu} -- Toto omezení vychází z~implementace třídy \classname{TripletProcessor}, která dokáže zpracovávat pouze čísla, která je možné zapsat pomocí 28 bitů, tedy maximálně číslo 134 217 728.
\item \textbf{Jazyk Java} -- Algritmy budou implementovány v~jazyce Java, protože celá knihovna SCT je v tomto jazyce napsána.
\item \textbf{Řetězení} -- Implementace metody bude dodržovat myšlenku řetězení, tedy že různé kompresní metody bude možné za sebe zapojovat a docílit tak několikanásobné komprese.
V~této kapitole pojednávám přímo o~jednotlivých metodách, na jakém principu fungují a v~čem se liší. Také zde určím jejich asymptotickou složitost komprese i dekomprese a jejich výhody a nevýhody.
\section{LZ77}
\subsection{Popis}
Tento kompresní algoritmus vynalezli v~roce 1977 pánové Abraham Lempel a Jakob Ziv. Jedná se o~slovníkovou, jednoprůchodovou, adaptivní a bezztrátovou metodu. Je založena na principu klouzavého okénka (floating window), které si lze představit jako vyříznutou část dat. Při běhu programu se okénko posouvá v~datech pouze jedním směrem a to od začátku do konce. Je rozděleno na dvě části - prohlížecí okénko (search buffer) a aktuální okénko (look-ahead buffer). Jejich velikost je velmi zásadní pro efektivitu celého algoritmu. V~zásadě se dá řict, že velikost prohlížecího okénka musí být vždy větší nebo rovna velikosti aktuálního okénka, nicméně v~praxi je prohlížecí okénko obvykle tisíci násobně větší než aktuální.\cite{vohoLZ77}
\subsection{Komprese}
Hlavní myšlenka tohoto algoritmu spočívá v~nalenzení co nejdelšího prefixu z~nezakódovaných dat, který je zároveň obsažený i v~prohlížecím okénku. Tato metoda umožňuje menší vylepšení efektivity, pokud se při vyhledávání neomezím pouze na prohlížecí okénko, ale jen na podmínku, že prefix v~něm musí začínat. V~některých případech je možné nalezt nejdelší prefix, který přesahuje do aktualního okénka. Je tedy možné zakódovat větší část dat. Slovník této metody je tvořen všemi podřetězci, které začínají v~prohlížecím okénku.
Zde je jednoduchý pseudokód, který popisuje tuto metodu:
\IncMargin{1em}
\begin{algorithm}[H]
prohlížecí a aktualní okénko jsou prázdná\;
\While{na vstupu jsou data}{
přidej na konec aktualního okénka symbol ze vstupu\;
najdi prefix $p$ z~aktualního okénka, který začíná v~prohlížecím okénku\;
\eIf{$p$ bylo nalezeno}{
zapiš trojici $(i, j, k)$, kde $i$ je vzdálenost prvního znaku nalezeného $p$ od začátku aktualního okénka, $j$ je délka $p$ a~$k$ je první nasledující symbol po $p$\;
posun klouzavé okénko o~$j+1$\;
}{
zapiš triplet $(0, 0, m)$, kde $m$ je první symbol v~aktualním okénku\;
posuň klouzavé okénko o~$1$\;
}
}
\caption{Pseudokód komprese metody LZ77.\cite{algoLZ77_78}}
\end{algorithm}\DecMargin{1em}
\subsection{Složitost komprese}
Dle mého názoru je složitost tohoto algoritmu $O(nm)$, kde $ n $ je délka vstupních dat a $ m $ je velikost prohlížecího okénka.
Na první pohled není uplně zřejmé, jak jsem k~tomuto závěru došel. Rozhodl jsem se tedy své tvrzení dokázat pomocí matematického důkazu.
Mějme asymptotickou složitost znázorněnou sumou, která vyjadřuje nejvyšší možný počet operací potřebných pro komprimaci souboru:
kde $P$ je množina všech prefixů nalezených v~datech, $m$ je velikost prohlížecího okénka a $p_{i}$ velikost $i$-tého prefixu z~$P$.
Protože součet sumy nezáleží na $ m $, mohu ho vytknout před sumu:
Součet sumy je vždy rovný velikosti dat, protože procházím celá vstupní data a rozděluji je na podřetězce, které najdu v~prohlížecím okénku. Nezáleží tedy na délce jednotlivých podřetězců, jejich součet velikostí bude vždy roven velikosti vstupních dat, tedy $ n $. Proto:
$$\sum_{i=1}^{|P|} m p_{i} = mn$$
z čehož plyne, že složitost komprese je $O(nm)$.
Je třeba říci, že na vyhledání prefixu nebude vždy potřeba stejný počet operací, proto jsem se rozhodl použít tzv. omikron $ O~$, který složitost omezuje shora.
\subsection{Dekomprese}
Algoritmus je poměrně jednoduchý. Nejdříve načte ze vstupu triplet, který v~sobě obsahuje informaci o~tom, odkud a jak dlouhou část prohlížecího okénka je potřeba zapsat na výstup. Poslední část tripletu je jeden byte, který je taktéž potřeba zapsat. Následně zapsaná data rovněž přidáme na konec prohlížecího okénka. Zde je jednoduchý pseudokód:\newline
\begin{algorithm} [H]
prohlížecí okénko je prázdné\;
\While{na vstupu jsou data}{
ze vstupu načti triplet $ (i, j, k) $, kde $i$ je vzdálenost prvního znaku hledaného podřetězce $p$ od konce prohlížecího okénka, $j$ je délka $p$ a $k$ je první nasledující symbol po $p$\;
\eIf{$i$ se rovná 0}{
zapiš $k$\;
pridej na konec prohlížecího okénka $k$\;
}{
$v:=$ aktuální velikost prohlížecího okénka\;
$z:= v~- i$\;
$p:=$ podřetězec prohlížecího okénka od indexu $z$ az do $z + j$-\;
$p:= p + k$\;
zapiš $p$\;
do prohlížecího okénka přidej $p$\;
}
}
\caption{Pseudokód dekomprese metody LZ77.\cite{algoLZ77_78}}
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
\end{algorithm}
\subsection{Složitost dekomprese}
Oproti kompresi je složitost dekomprese vcelku trivialní. Řekněme, že $ t $ je počet tripletů, pro každý triplet bude potřeba $ p_{i} $ operací, při čtení podřetězce z~prohlížecího okénka. To znamená, že celkový počet operací bude roven sumě všech délek podřetězců. Tato suma se však rovná velikosti puvodního nekomprimovaného souboru, tedy $ n $. Čímž dostáváme: $$\sum_{i=1}^{t} p_{i} = n$$ z~čehož plyne, že složitost dekomprese je $ \Theta(n) $.
Složitosti komprese i dekomprese jsou rozdílné, jedná se tedy o~asymetrickou metodu.
\subsection{Výhody}
\begin{itemize}
\item \textbf{Paměť} -- Díky posuvnému okénku se v jednu chvíli zpracovává poměrně malá čast dat, proto neroste paměťová náročnost s~velikostí vstupu.
\item \textbf{Rychlost dekomprese} -- Při vhodně zvolené implementaci je algoritmus dekomprese lineárně závislý pouze na velikosti dat. Jeho složitost je tedy $\Theta(n)$, kde n je velikost původních dat.
\end{itemize}
\subsection{Nevýhody}
\begin{itemize}
\item \textbf{Náhodná data} -- Pokud mají data příliš velkou míru entropie, algoritmus dosahuje velmi špatných výsledků, často i komprimovaný soubor zvětší. To se týká například některých formátů obrázku (jpeg).
\item \textbf{Rychlost komprese} -- Složitost $O(nm)$ je oproti dekompresi $ m $ krát větší. To znamená, že algoritmus bude pomalejší, protože $ m $ je obvykle velké číslo v~řádech tisíců až desetitisíců.
\end{itemize}
\section{LZ78}
\subsection{Popis}
Metoda byla vynalezena stejnými autory jako LZ77 v~roce 1978. Z~počátku se jednalo o~velmi oblíbenou komprimační metodu až do doby než byly některé její časti patentovány.
Jedná se o~paměťově velmi náročnou metodu. Je tomu tak hlavně kvůli obvykle velkému slovníku. Metoda totiž v~původní verzi přidává do slovníku položku vždy, když zapisuje triplet, což se děje velmi často. Existuje mnoho způsobu, jak tento problém vyřešit. Například v~případě vyčerpání paměti tzv. zamrazit slovník nebo smazat a vytvořit nový. Nejznámější modifikací je LZW, kterou se také zabývám v~této práci.\cite{stringologyLZ78}
\subsection{Komprese}
Prvním krokem tohoto algoritmu je inicializace slovníku. Tento krok je velmi důležitý pro správný průběh dekomprese. Do slovníku se přidá slovo délky jedna za každé písmeno abecedy souboru. Abeceda je množina všech znaků, které se mohou v~souboru objevit. Obvykle se používá množina všech bytů (0~-~255), pokud komprese kóduje po bytech. Dále nastaví řetězec $ str $ jako prázdný.
Následující krok se opakuje pro každý byte ze vstupu. Pokud spojení řetězce $ str $ a načtený byte $ b $ nejsou ve slovníku, na výstup se přidá triplet obsahující index $ str $ ve slovníku a $ b $. V~opačném případě se na konec řetězce $ str $ přidá byte $ b $. Výstupem teto metody je posloupnost dvojic -- číslo, byte.
Zde je jednoduchý pseudokód, popisující kompresi:\newline
\begin{algorithm}[H]
inicializace $slovníku$\;
$str :=$ prázdný řetězec\;
\While{na vstupu jsou data}{
ze vstupu načti byte $ b $\;
\eIf{$str + b$ není ve $slovníku$}{
zapiš triplet $(i, b)$, kde $i$ je index $str$ ve $slovníku$\;
přidej na konec $slovníku$ slovo $str + b$ \;
$str :=$ prázdný řetězec\;
}{
$str = str + b$\;
}
}
\caption{Pseudokód komprese metody LZ78.\cite{algoLZ77_78}}
\end{algorithm}
\subsection{Složitost komprese}
Tento algoritmus velmi ovlivňuje zvolená implementace. Pokud se slovník representuje pomocí datové struktůry strom, složitost je $ \Theta(n) $, kde n je velikost vstupních dat v~bytech. Protože dokáže v~konstantní složitosti $ \Theta(1) $ říci, jestli slovník již obsahuje daný řetězec či nikoliv. Pro každy vstupní symbol vykoná $ \Theta(1) $ operací. Pro uplnost doplním jednoduchou rovnici, která ukazuje, že v~asymptotické složitosti se konstantní složitost neprojeví: $$ \Theta(1 * n ) = \Theta(n) $$
\subsection{Dekomprese}
Jak je vidět na pseudokódu níže, algoritmus je velmi jednoduchý. Prvním a~zásadním krokem je inicializace slovníku přesně stejnou abecedou jako v~kompresi. Následně se načte triplet ze vstupu, podle něj se najde slovo ve slovníku a zapiše do souboru společně s~následujícím bytem. Tento zapsaný řetězec je přidán do slovníku na konec (přiřadí se mu nejvyšší index).\newline
\begin{algorithm}[H]
inicializace $slovníku$\;
\While{na vstupu jsou data}{
ze vstupu načti triplet $ (i, b) $, kde $ i $ je index do $slovníku$ a $ b $ je následující byte\;
$str := slovník[i]$ + $ b $\;
zapiš $ str $\;
přidej na konec $slovníku$ slovo $str$ \;
}
\caption{Pseudokód dekomprese metody LZ78.\cite{algoLZ77_78}}
\end{algorithm}
\subsection{Složitost dekomprese}
Jak bylo řečeno v~popisu, jedná se o~symetrickou metodu. Složitost je tedy stejná jako u~komprese a tedy $ \Theta(n) $, kde $ n $ je velikost původních dat. Podobně jako u~metody LZ77, máme sice menší vstup, nicméně je potřeba přičíst i~režiji slovníku na zrekonstruováná slova. Jedná se o~strom, to znamená, že metoda pro rekonstrukci slova udělá počet operací rovný délce slova. Pokud tedy všechny délky posčítáme, dostaneme $ n $.
\subsection{Výhody}
\begin{itemize}
\item \textbf{Rychlost komprese i dekomprese} -- Při vhodně zvolené implementaci je algoritmus komprese i dekomprese lineárně závislý pouze na velikosti dat. Jejich složitost je $\Theta(n)$, kde n je velikost původních dat.
\item \textbf{Implementace} -- Metoda je poměrně jednoduchá na implementaci, především pak dekomprese.
\item \textbf{Velikost tripletů} -- Do souboru se ukládají pouze dvojice -- číslo, byte.
\end{itemize}
\subsection{Nevýhody}
\begin{itemize}
\item \textbf{Paměť} -- Paměťová náročnost roste s~velikostí vstupu. Proto se při implementaci musí počítat s~tím, že metoda vyčerpá přidělenou pamět a~podle toho se zachovat.
\item \textbf{Náhodná data} -- Podobně jako u~metody LZ77, při velké entropii dat dochází k~horší kompresi, někdy muže dojít až k~zvětšení souboru.
\end{itemize}
\section{LZW}
Tuto slovníkovou, symetrickou, adaptivní a jednoprůchodovou metodu vytvořili Abraham Lempel, Jacob Ziv a Terry Welch v~roce 1984. Jedná se o~modifikaci metody LZ78. Hlavním rozdílem je, že algoritmu pro dekomprimaci dat stačí pouze indexy ve slovníku. Již tedy nepotřebuje následující byte jako jeho předchůdce. To má ale také za následek rychlejší růst počtu frází ve slovníku. Slovník tedy typicky bývá větší než u~LZ78 a spotřebovává rychleji paměť. Je tedy potřeba s~tím počítat při implementaci a tento problém vhodně vyřešit. Obecně platí, že čím větší slovník, tím lepší kompresní poměr. Algoritmus je navržen tak aby byl rychlý, nicméně ne vždy je optimální, protože neprovádí žádnou analýzu dat během komprese.\cite{stringologyLZW}
Metoda se stala velmi oblíbenou kolem roku 1987, protože poskytovala nejlepší kompresní poměr. Byla využita například ve formátu GIF, později ve formátu PDF nebo v~unixovém nástroji $ compress $. Stala se první široce využívanou kompresní metodou na počítačích.\cite{stringologyLZW}
První krok algoritmu je inicializace, která probíhá totožně jako v~metodě LZ78. Následně se načte byte $ b $ ze vstupu. Pokud je řetězec $ str + b $ ve slovníku, nastaví se jako $ str $. Pokud není, do souboru se zapíše triplet $ (i) $, kde $ i $ je index fráze $ str $. Do slovníku se pak přidá fráze $ str + b $ a jako nové $ str $ se nastaví $ b $. To je hlaní změna oproti metodě LZ78, která umožnuje právě vynechání nasledujícího bytu v~tripletu. Tento postup se opakuje dokud jsou na vstupu data. Zde je pseudokód komprese LZW:\newline
\begin{algorithm}[H]
inicializace $slovníku$\;
$str :=$ prázdný řetězec\;
\While{na vstupu jsou data}{
ze vstupu načti byte $ b $\;
\eIf{slovo $str + b$ není ve $slovníku$}{
zapiš triplet $(i)$, kde $i$ je index $str$ ve $slovníku$\;
přidej na konec $slovníku$ slovo $str + b$ \;
$str := b$ \;
}{
$str = str + b$\;
}
}
\caption{Pseudokód komprese metody LZW.\cite{algoLZW}}
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
\end{algorithm}
\subsection{Složitost komprese}
Metoda obsahuje pouze drobné změny oproti LZ78, které nemají vliv na asymptotickou složitost. Je totožná se složitostí komprese LZ78, tedy $\Theta(n)$. Proto si dovolím vynechat její odvození.
\subsection{Dekomprese}
Princip dekomprese není na první pohle pochopitelný, protože nepřidávám do slovníku slovo tvořené právě zapisovaným řetězcem, ale tím který byl zapsaný v~minulém běhu a pouze prvním znakem zapisovaného řetězce. Tato skutečnost je dána tím, že komprimace přidává do slovníku slovo délky $ n $, končící právě načteným bytem, ale do souboru zapisuje index předchozího slova délky $ n - 1 $, tedy bez načteného bytu. Dekomprimační algoritmus pak vždy ví, že do slovníku je potřeba přidat slovo z~minulého běhu zakončené prvním znakem z~fráze nalezené ve slovníku.
Specialní případ nastane, pokud algoritmus ze vstupu načte triplet s~indexem, který není ve slovníku. Toto číslo však může být pouze o~jedna větší než nejvyšší obsazený index, jinak se jedná o~chybu kompresního algoritmu. V~tomto případě do slovníku vloží slovo, které bylo vloženo v~předchozím kroku zakončené jeho prvním znakem.
K~tomuto případu dochází, pokud bylo pro komprimaci použito slovo na posledním indexu (naposledy přidaná fráze do slovníku).
Zde je pseudokód, popisující tento algoritmus:\newline
\begin{algorithm}[H]
inicializace $slovníku$\;
$str :=$ prázdný řetězec\;
\While{na vstupu jsou data}{
ze vstupu načti triplet $ (i) $\;
\eIf{$slovník$ obsahuje slovo s~indexem $ i $}{
$ fráze := slovník[i]$\;
zapiš $fráze$\;
přidej na konec $slovníku$ slovo $str $ + první znak $ fráze $ \;
}{
$fráze = str $ + první znak ze $str$\;
zapiš $str$\;
přidej na konec $slovníku$ slovo $fráze$\;
}
$str := fráze$
}
\caption{Pseudokód komprese metody LZW.\cite{algoLZW}}
\end{algorithm}
\subsection{Složitost dekomprese}
V~závislosti na implementaci se muže složitost tohoto algoritmu lišit. Nicméně pokud struktůru slovníku representuje strom je možné dosáhnout složitosti $ \Theta(n) $, kde $ n $ je velikost původních dat před kompresí. Metoda LZW je navíc symetrická, takže složitost je stejná jako u~komprese. Důvod proč jsem došel k~této složitosti je analogický s~určením složitosti dekomprese u~LZ78. Nejvice kroků bude potreba udělat tam, kde se ze slovníku rekonstruuje řetězec, což odpovídá celkové velikosti dat. Ostatní operace mají zanedbatelnou režii a při určování asymptotické složitosti se zanedbávají.
\subsection{Výhody}
\begin{itemize}
\item \textbf{Rychlost komprese i dekomprese} -- Stejně jako u~LZ78 je hlavní výhodou rychlost. Při správné implementaci $ \Theta(n) $.
\item \textbf{Velikost tripletů} -- Do souboru se ukládají pouze číslo. Na jeden triplet je tedy potřeba uložit nejmeně dat z~metod, kterými se zabývá tato práce.
\item \textbf{Kompresní poměr} -- Na běžném anglickém textu dosahuje metoda velmi dobrých výsledků, typicky zmenší soubor zhruba o~50 %.
\end{itemize}
\subsection{Nevýhody}
\begin{itemize}
\item \textbf{Paměť} -- Paměťová náročnost roste s~velikostí vstupu. Roste dokonce rychleji než u~LZ78. Proto se při implementaci musí počítat s~tím, že metoda vyčerpá přidělenou pamět.
\item \textbf{Náhodná data} -- Podobně jako u~předchozích metod, dochází při velké entropii dat k~horší kompresi. Může dojít až k~zvětšení souboru.
\end{itemize}
\section{Závěr analýzy}
Hlavním přínosem těchto metod je samotný princip na jakém fungují. Především pak LZ77 z~které vznikla řada algoritmů, které se dnes využívají v~praxi. Největší nevýhodou těchto algoritmů je špatný kompresní poměr na datech, ve kterých se neopakují delší řetězce znaků. Další nevýhodou LZ78 a LZW je velká náročnost na paměť. Jejich kompresní poměr je obvykle závislí na velikosti slovníku. Nicméně i přes tyto nevýhody se LZW v~některých programech používá dodnes, protože je velmi rychlá a vhodná na klasický text.
\chapter{Implementace}
V~této kapitole popisuji realizaci metod přímo v~knihovně SCT. Zásadní věcí v~implementaci těchto metod je reprezentace slovníků, ať už u~komprese nebo dekomprese. Efektivní přidávání a hledání ve slovníku je zásadní pro efektivitu těchto metod. Vysvětluji jaké parametry bude moci nastavit uživatel a~jak ovlivní efektivitu nebo paměťovou náročnost. Jakým způsobem metody načítají data ze vstupu a~jak zapisují triplety do souboru.
\section{Řetězení}
V~knihovně se používá princip řetězení (chaining). To znamená, že některé metody se dají zapojovat za sebe. Zde je ukázka kódu:
\begin{lstlisting}
ChainBuilder.create(io::openParse)
.chain(lz77::compress)
.chain(t2b)
.end(bytes -> io.saveObject(bytes, f2.toPath()))
.accept(f1.toPath());
\end{lstlisting}
Výše uvedený kód ukazuje použití implementovaných metod. Důležitý je princip, podle kterého je naimplementovaná metoda \classname{compress}. Hlavní podmínkou pro chainování jsou dva parametry metody. První je vstupní parametr a druhý výstupní. Respektive druhým parametrem je objekt consumer, který má za parametr datový typ výstupu. Ukázka kódu:
\begin{lstlisting}
public void compress(ByteBuffer byteBuffer,
Consumer<TripletSupplier> tripletSupplierConsumer) {...}
\end{lstlisting}
Zde je vstupní parametr typu \classname{ByteBuffer}, to znamená že předchozí metoda v~řetězci musela mít druhý parametr typu \classname{Consumer<ByteBuffer>}. Vystupním parametrem je \classname{TripletSuplier}, následující metoda tedy musí mít první parametr \classname{TripletSuplier}. V~tomto připadě je to objekt \classname{t2b}, který je instancí třídy \classname{TripletToByteConverter}, která implementuje rozhraní \newline \classname{Chainable<TripletSupplier, List<byte[]>>}.
Další možností je implementovat celý objekt tak, aby mohl být řetězený, pomocí implementace rozhraní \classname{Chainable<x, y>}, kde x je datový typ vstupního parametru a y datový typ pro výstup. Zde je hlavička třídy, kterou je možné řetězit:
\begin{lstlisting}
public abstract class TripletToByteConverter<T>
implements Chainable<TripletSupplier, List<byte[]>>
{...}
\end{lstlisting}
Uvnitř metody se pak volá třídní metoda consumera \classname{accept}, která posílá data do další metody v řetězci. Objekt musí mít vždy implementovanou metodu \classname{setConsumer}, která nastavý consumera. Ten funguje stejne jako u~metody.
\section{Načítání a zápis do souboru}
Načítání ze souboru se u~komprese a dekomprese liší. Zatím co v~prvním případě, načítám ze souboru byty u~dekomprese se jedná o~načtení celého objektu ze souboru. Je tomu tak proto, že po kompresi se ukládá celé pole bytů jako objekt, aby bylo možné správně načítat uložené triplety. Dekomprese ukládá data do souboru po bytech, aby byl soubor stejný jako před komprimací.
O~vše se stará třída \classname{FileIO}, která má jako parametr velikost, podle které rozděluje načítaný soubor na menší části a ty se následně zkomprimují a v~podobě tripletů uloží do souboru. Zkomprimované soubory se načítají i dekomprimují jako celek, aby nedocházelo k~narušení slovníků. Mohlo by se stát, že načteme menší nebo větší část tripletů než jaká byla vytvořena z~jedné části pri kompresi. Takový případ by pak způsobil špatné sestavení slovníku, což by vedlo k~chybám v~dekompresi.
Nedílnou součástí všech implementovaných kompresních metod jsou triplety. Jejich zpracování a následný zápis je zprostředkován pomocí rozhraní\newline \classname{TripletSupplier}, které se vždy používá jen pro vytvoření anonymní vnitřní trídy, která implementuje metodu visit, jejímž parametrem je \classname{TripletProcessor}. Ten dokáže pomocí metody \classname{write} zapsat jednotlivé části tripletu do souboru.\newpage Zde je ukázka kódu:
\begin{lstlisting}
output.accept((TripletSupplier) new TripletSupplier() {
@Override
public void visit(TripletProcessor visitor) {
visitor.write(nodeFieldId, num);
visitor.write(characterFieldId, b);
}
});
\end{lstlisting}
Metoda \classname{write} má dva parametry. Druhým parametrem je hodnota zapisované složky tripletu. Prvním je objekt reprezentovaný třídou \classname{TripletFieldId}, který popisuje, kolik bitů má zapisovaná hodnota. \classname{TripletProcessor} se postará o~správný zápis bitů. To je velká výhoda, protože u~všech metod vždy dopředu vím, jaké největší číslo může být zapsáno.
Například, pokud metoda pracuje se slovníkem, jehož maximálně počet frází je $ 2^{10}$. Není potřeba zapisovat indexy jako integer, který má 32 bitů. Pro zapsání jakéhokoliv indexu je potřeba nejvýše 11 bitů, zbytek jsou redundantní data. Tento postup v~tomto případě ušetří na každém tripletu 22 bitů, což je velká úspora paměti, která výrazně zlepší kompresní poměr. Samotná implementace třídy \classname{TripletFieldId} umožnuje zapsat pouze číslo o~velikosti 28 bitů. Tato skutečnost ale není omezující, protože slovník s~takovým počtem frází ($ 2^{29} $ a více) by byl velmi neefektivní.
\section{Parametry}
Každá metoda má třídu s~názvem \classname{<jméno metody>ProviderParametrs}. Tato třída reprezentuje všechny nastavitelné parametry, které ovlivňují kompresi i dekompresi. Metodám se předává jako jediný parametr v~konstruktoru. Tyto parametry jsou podrobně popsány dále v~realizaci metod.
Každá metoda má třídu s~názvem \classname{<jméno metody>Client}. Tato třída obsahuje statickou funkci $main$, to v Javě znamená, že je možné jí spustit. Jedná se o~spustitelný program z~příkazové řádky, který komprimuje popřípadě dekomprimuje soubor podle zvoleného přepínače a parametrů. Jednotlivé klienty a jejich použití popisuji pro každou metodu zvlášť v~kapitolách realizace. Klient je zatím spustitelný ve složce \classname{sct/targets} příkazem:
\begin{lstlisting}
java -jar sct-RELEASE.jar <input> <output> <options>
\end{lstlisting}
Při změně klienta je potřeba v~souboru \classname{pom.xml} změnit cestu k~správné $main$ funkci, kterou chcete spustit a následně zkompilovat projekt.\newpage
\section{Realizace LZ77}
\subsection{Struktůra adresáře}
Na schématu adresářové struktůry můžete vidět třídu LZ77, která inicializuje kodér \classname{LZ77TripletCoder}. Ten se stará o~kompresi i dekompresi a zápis tripletů. Podrobnější popis tříd a jejich funkcí naleznete dále v~textu.
\begin{figure}[H]
\dirtree{%
.1 .
.1 lz77.
.2 LZ77.java.\DTcomment{třída volající metody komprese nebo dekomprese}.
.2 LZ77Client.java.\DTcomment{klient, spustitelný přes příkazovou řádku}.
.2 LZ77ProviderParameters.java\DTcomment{třída obsahující všechny parametry}.
.2 LZ77Test.java\DTcomment{testovací třída}.
.1 triplet.
.2 coder.
.3 LZ77TripletCoder.java\DTcomment{Třída zrpacující vstup při kompresi i~dekompresi, dědí ze třídy \classname{TripletCoder}}.
}
\renewcommand\figurename{Struktura}
\caption{adresářová struktura metody LZ77}
\label{dirtree}
\end{figure}
\subsection{Parametry}
Pro metodu LZ77 jsou důležité tři parametry. Velikost prohlížecího okna, aktualního okna a počet bytů, který udává, po jak velkých částech se bude soubor komprimovat.
Velikost prohlížecího i aktualního okna se zadává jako exponent $ e $. Následně se pak velikost oken vypočte jako $ 2^{e-1} $, $ e $ je pak nejvyšší počet bitů, potřebný pro zapsání jakehokoliv indexů do tripletu. Velikost třetího parametru se pak pohybuje obvykle od statisíců do desítek milionů (0,1~-~10~mb), nicméně není vyloučeno použít i jiné hodnoty. Na jak velké části se soubor rozdělí, ovlivní výslednou komprimaci a to jak pozitivně tak i negativně. Jako parametr prohlížecího okna se obvykle volí čísla od 11 do 16, tj. velikost okna 1024 -- 32768 znaků. Aktualní okno je typicky mnohem menší, obvykle 64 -- 256 znaků, tomu odpovídá parametr od 7 do 9.
Na začátku komprese se uloží jako první specialní triplet, který v~této práci označuji jako hlavička souboru. V~případě LZ77 obsahuje informaci o~tom, jaký byl exponent velikosti prohlížecího a aktualního okna. Tato informace je důležitá pro načítání dat z~tripletů při dekompresi. Udává kolik bitů je potreba prečíst, abychom získali uložené číslo. Bez této hlavičky by nebylo možné soubor dekomprimovat.
\subsection{Implementace komprese}
Ve třídě \classname{LZ77} je implementována metoda \classname{compress}, která zajišťuje správný průběh komprese. Vstupním parametrem je \classname{byteBuffer}, což je instance třídy \classname{ByteBuffer}. Pokud je vstupní parametr null, je to signál, že je komprese u~konce. Na úplném začátku algoritmu se do souboru zapíše hlavička.
Pomocí \classname{byteBufferu} a parametrů se inicializuje instance třídy \linebreak \classname{LZ77TripletCoder}, která se stará o~samotnou kompresi a zápis tripletů. Komprese souboru se volá pomocí metody \classname{encode}, ta má jako parametr konsumera, do kterého se zapisují triplety.
Většina předchozího textu je jen popis použití nástrojů knihovny, který je u~všech metod podobný, proto ho dále nebudu popisovat. Z~hlediska implementace je nejduležitější metoda \classname{encode}, která zajištuje celý algoritmus komprese LZ77.
Protože načítání vstupů funguje tak, že program načte celou část souboru po bytech do pole, rozhodl jsem se toho využít při implementaci. Místo pole do kterého bych byty přidával a odebíral tak, aby vždy odpovídali rozměrům prohlížecího a aktualního okénka, jsem se rozhodl, použít pouze indexy v~poli bytů, které metoda dostane jako vstupní parametr.
První index ukazuje, kde v~poli začíná prohlížecí okno. Druhý, kde je začátek aktualního a tedy i konec prohlížecího okna a třetí, kde je konec aktualního okna. Těmito indexy si tedy ohraničím klouzavé okénko. To se pak velmi snadno posouvá daty. Vždy jen ke všem indexům přičtu velikost zakódovaného řetězce.
Na počátku algorimu jsou první dva indexy rovny nule, druhý se pak s~prvním komprimovaným řetězcem začne zvětšovat. Index který ukazuje na začátek se začne měnit až když prohlížecí okénko odpovídá požadované velikosti. Poslední index, který ukazuje na konec aktualního okénka, je na začátku rovný požadované velikosti, v~pruběhu komprimace se zvětšuje dokud nenarazí na konec pole.
Samotné hledání prefixu z~aktualního okénka probíhá tak, že vezmu první byte v~aktualním okénku a pokusím se ho najít v~prohlížecím okénku. Pokud je nalezena shoda, vezmu následující byte z~aktualního okénka a porovnám ho s~následujícím bytem v~prohlížecím okénku. Pokud jsou schodné, postup opakuji, pokud ne, zapamatuji si toto slovo jako kandidáta na nejdelší prefix. A~celý postup opakuji dokud neprojdu celé prohlížecí okno a nenajdu největší možný prefix v aktualním okně. Prostor pro hledání nejdelšího slova se postupně zmenšuje díky skutečnosti, že v~poli před kandidátem na nejdelší slovo žádné delší nemůže být, protože vím, že nejdelší nalezené slovo v~předchozí časti je právě kandidát. Aktualní okénko je stejné, jako na začátku, mění se až po nalezení nejdelšího slova.\pagebreak
Po nalezení nejelšího slova se všechny indexy posunou o~jeho velikost zvětšenou o~1 a do konsumera se uloží triplet, který je tvořen třemi složkami: $$ (i, j, b) $$ Kde $i$ je vzdálenost začátku slova od počátku aktualního okénka. Na zapsání je potřeba počet bitů, který udává první parametr zadaný uživatelem. Další složkou je číslo $j$, což je délka slova. Počet bitů pro zápis čísla $j$ udává druhý parametr. Poslední složkou je byte $b$, což je následující byte po nalezeném slově v~aktualním okně. Ten má vždy 8 bitů.
Po kompresi se všechny triplety převedou pomocí třídy \linebreak \classname{TripletToByteConverter} na byty a následně zapíšou do souboru.
\subsection{Implementace dekomprese}
Uvnitř třídy \classname{LZ77TripletCoder} je naimplementovaná metoda \classname{decode}, která má jako vstupní parametr input třídy \classname{TripletProcessor}, což je výsledek zpracování vstupu třídou \classname{ByteToTripletConverter}, která převádí vstupní byty na triplety.
Implementace dekomprese je velmi jednoduchá. Na začátku si inicializuji proměnou $ builder $ třídy \classname{ByteBuilder}, čož je třída obalující pole bytů a poskytující některé vhodné metody pro práci s~polem, především pak metodu \classname{appent}, která přidá byte na konec pole.
Následující krok se opakuje dokud jsou v~proměnné $input$ triplety. Načtu triplet $ (i, j, b) $. Pokud jsou první i druhá složka rovny nule, pak na konec $builderu$ přidám byte $b$ z~třetí složky tripletu, jinak najdu byte vzdálený $i$ bytů od konce $builderu$. Od tohoto bytu přidám $j$ znaků na konec $builderu$. Sekvence zapsaných bytů odpovídá zakódovanému prefixu. Na konec $builderu$ přidám byte $b$ z~načteného tripletu.
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
Pokud dojdou triplety, $input$ vratí číslo $ -1 $ v~následující načtené složce tripletu.
V~případě této metody není problém dekódovat i triplety, které vznikli z~jiné části při kompresi. Díky skutečnosti, že při dekódování tripletu mám k~dispozici vždy celé pole předchozích bytů, vždy správně najdu index od kterého kopírovat data. To je také duvod, proč nemusí být v~hlavičce velikost částí na rozdíl od dalších dvou metod.
Po dekomprimaci se pole bytů zapíše do souboru. Nový soubor je totožný s~tím před komprimací.\pagebreak
\subsection{Spustitelný klient}
Klient metody LZ77 může být spuštěn s~těmito přepínači:
\begin{itemize}
\item \textbf{-h} -- vypíše nápovědu
\item \textbf{-d} -- spustí dekompresi vstupního souboru, s~tímto přepínačem není potřeba zadávat další parametry, program je bude ignorovat, protože si načte hlavičku, ve které jsou všechny potřebné parametry
\item \textbf{-sb <$e$>} -- tento přepínač říká, jak velké prohlížecí okénko bude použito ($ 2^{e-1} $)
\item \textbf{-lb <$e$>} -- tento přepínač říká, jak velké aktualní okénko bude použito ($ 2^{e-1} $)
\item \textbf{-p <$n$>} -- tento přepínač říká, po jak velkých částech bude probíhat komprese (v~bytech)
\end{itemize}
Poznámka: Pokud při kompresi některý z~posledních tří přepínačů chybí nebo je v~některém chyba, metoda se zavolá s~výchozími parametry, které jsou: -sb~$14 $ -lb $8 $ -p $ 1 000 000 $.\newpage
\section{Realizace LZ78}
\subsection{Struktůra adresáře}
Na schématu adresářové struktůry můžete vidět třídu LZ78, která inicializuje kodér \classname{LZ78TripletCoder}. Ten se stará o~kompresi i dekompresi a zápis tripletů. Podrobnější popis tříd a jejich funkcí naleznete dále v~textu.
\begin{figure}[H]
\dirtree{%
.1 .
.1 lz78.
.2 dictionary.
.3 DecodeDictionary.java.\DTcomment{interface pro dekompresi}.
.3 DecodeList.java.\DTcomment{slovník dekomprese pomocí seznamu}.
.3 DecodeTree.java.\DTcomment{slovník dekomprese pomocí stromu}.
.3 DecodeNode.java.\DTcomment{třída reprezentující frázi/uzel pro dekomprese}.
.3 EncodeDictionary.java.\DTcomment{slovník komprese}.
.3 EncodeNode.java.\DTcomment{třída reprezentující uzel komprese}.
.2 LZ78.java.\DTcomment{třída volající metody komprese nebo dekomprese}.
.2 LZ78Client.java.\DTcomment{klient, spustitelný přes příkazovou řádku}.
.2 LZ78ProviderParameters.java\DTcomment{třída obsahující všechny}.
.2 LZ78Test.java\DTcomment{testovací třída}.
.1 triplet.
.2 coder.
.3 LZ78TripletCoder.java\DTcomment{Třída zrpacující vstup při kompresi i~dekompresi, dědí ze třídy \classname{TripletCoder}}.
}
\renewcommand\figurename{Struktura}
\caption{adresářová struktura metody LZ78}
\label{dirtree}
\end{figure}
\subsection{Parametry}
Metoda má pouze dva parametry. Prvním je velikost slovníku, tedy počet frází, které je možné uložit. Druhým parametrem je velikost částí (v~bytech). Jeho význam je stejný jako u~metody LZ77. Podobně jako u~LZ77 se první parametr zadává pomocí exponentu $e$. Velikost slovníku se pak vypočte jako $2^{e-1}$, $e$ je počet bitů potřebný pro zapsání jakehokoliv indexu ze slovníku. Obvykle se $ e $ pohybuje kolem hodnot 12-19, což odpovídá 2048 -- 262 144 frází ve slovníku.
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
\subsection{Hlavička souboru}
Prvním udajem v~hlavičce je parametr $ e $, který udává kolik bitů má číslo indexu v~tripletu. Druhým údajem je velikost částí. Důležitost druhého parametru vysvětlím v~části o~implementaci dekomprese.
\subsection{Implementace komprese}
Kompresi zajišťuje metoda \classname{encode} uvnitř třídy \classname{LZ78TripletCoder}.
Jako struktůru pro slovník jsem se rozhodl použít strom, jehož uzly jsou reprezentováni pomocí třídy \classname{EncodeNode}. Strom je implementovaný tak, že každý uzel má v~sobě mapu potomků. To umožňuje velmi rychlé vyhledávání frází.
Slovník reprezentuje metoda \classname{EncodeDictionary}, \classname{compress} vždy načte byte a předá ho slovníku, aby ho zpracoval pomocí metody \classname{processByte}.
Slovník si drží ukazatel na kořen stromu a na aktualní uzel. Kořen sám funguje jako prázdný znak, který má v~mapě potomků všech 256 bytů. Jedná se o~inicializaci slovníku, která je popsaná v~kapitole o~analýze algoritmu LZ78 a probíhá v~konstruktoru slovníku.
Na začátku je ukazatel na aktualní uzel rovný ukazateli kořenu. Vždy když se zavolá metoda \classname{processByte}, zkontroluje se zda má aktualní uzel v~mapě potomků uzel na hodnotě načteného bytu. Pokud ano, ukazatel na aktualní uzel se posune do potomka. Pokud ne, zapíše se triplet $$ (i, b) $$ kde $i$ je číslo aktualního uzlu a $b$ je načtený byte. Aktualnímu uzlu se přidá potomek do mapy na hodnotu $b$. Ukazatel na aktualní uzel se posune do kořene.
Tímto způsobem se ve slovníku zjišťuje, jestli obsahuje hledanou frázi. Pokud slovník zjistí, že ji neobsahuje, přidá jí.
V~průběhu komprese se kontroluje kolik frází je již ve slovníku. Pokud počet frází dosáhne maxima, které udává parametr, slovník se zamrazí. Komprese pokračuje dál, nicméně slovník se už nezvětšuje.
\subsection{Implementace dekomprese}
Kompresi zajišťuje metoda \classname{decode} uvnitř třídy \classname{LZ78TripletCoder}.
Pro účely testování jsem naimplementoval dva slovníky pro dekompresi. Liší se především tím, s~jakou složitostí přidávají a získávají ze slovníku fráze.
Na uplném začátku se načte hlavička a inicializuje slovník jako u~komprese. Dále se načte triplet ze souboru. Jeho složky jsou index $ i $ a následující byte $ b $. Index určuje, kde se nachází fráze ve slovníku. Zde se implementace liší.
Třída \classname{DecodeList} representuje slovník jako pole frází. Pomocí indexu z tripletu najdu frázi a tu poté zapíšu do souboru. Následně je na konec slovníku přidána fráze složená ze zapsaného řetězce a bytu $ b $.
Třída \classname{DecodeTree} si slovník udržuje jako strom, podobně jako při kompresi. Rozdíl je v~tom, že všechny uzly jsou uloženy v~poli ve stejném pořadí v~jakém byly přidány, aby bylo možné hledat uzel na indexu $ i $ v~konstatní složitosti. Fráze se pak zrekonstruuje rekurzivně pomocí odkazů na rodiče, který každý uzel osahuje. Kořen funguje jako zarážka rekurze, protože jeho rodič je null. Ukončovací podmínka tedy zní: Pokud je rodič null, zastav rekurzi.
Poté co je fráze získaná ze slovníku, zapíše se na konec výstupního souboru společně s~následujícím bytem $ b $. Následně je do stromu vložen potomek uzlu s indexem $ i $ na hodnotou $ b $, což ředstavuje novou frázi.
V~přidávání frází do slovníku se tyto implementace také liší. Zatímco třída \classname{DecodeList} vytvoří novou frázi tak, že zkopíruje řetězec a přidá k~němu byte $ b $, třída \classname{DecodeTree} přidá uzlu na indexu $ i $ pouze potomka do mapy s~klíčem hodnoty $ b $.
Třída \classname{DecodeList} má tedy složitější přidávání frází, ale jednodušší hledání ve slovníku. U~třídy \classname{DecodeTree} je tomu přesně naopak. Tato třída sice najde uzel v konstantním čase, ale renstrukce slova je podobně složitá, jako kopírování u první metody. Nicméně testování těchto dvou implementací ukázalo, že se v~rychlosti dekomprese neprojeví žádné velké rozdíly. Je to způsobeno tím, že počet kopírování a rekonstrukcí slov je stejný.
V~průběhu dekomprese, algoritmus zaznamenává, kolik dat bylo dekódováno. Pokud počet dekódovaných dat dosáhne velikosti druhého parametru z~hlavičky, stávající slovník se vymění za nově vytvořený. Nový slovník je vytvořen pomocí konstruktoru a obsahuje poze fráze vzniklé při inicializaci. Proces tvorby slovníku začne od znovu stejně jako při kompresi nové části. Tímto zpusobem se správně dekódují jednotlivé části souboru.
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
\subsection{Spustitelný klient}
Klient metody LZ78 může být spuštěn s~těmito přepínači:
\begin{itemize}
\item \textbf{-h} -- vypíše nápovědu
\item \textbf{-d} -- spustí dekompresi vstupního souboru, s~tímto přepínačem není potřeba zadávat další parametry, program je bude ignorovat, protože si načte hlavičku, ve které jsou všechny potřebné parametry
\item \textbf{-nc <$e$>} -- tento přepínač říká, kolik maximálně frází muže být ve slovníku ($ 2^{e-1} $)
\item \textbf{-p <$n$>} -- tento přepínač říká, po jak velkých částech bude probíhat komprese (v~bytech)
\end{itemize}
Poznámka: Pokud při kompresi některý z~posledních dvou přepínačů chybí nebo je v~některém chyba, metoda se zavolá s~výchozími parametry, které jsou: -nc $17 $ -p $ 1 000 000 $.\newpage
\section{Realizace LZW}
\subsection{Struktůra adresáře}
Na schématu adresářové struktůry můžete vidět třídu LZW, která inicializuje kodér \classname{LZWTripletCoder}. Ten se stará o~kompresi i dekompresi a zápis tripletů. Metoda LZW využívá pro reprezentaci uzlů ve slovníku stejné třídy jako LZ78. Podrobnější popis tříd a jejich funkcí naleznete dále v~textu.
\begin{figure}[H]
\dirtree{%
.1 .
.1 lz78.
.2 dictionary.
.3 DecodeNode.\DTcomment{třída reprezentující frázi/uzel pro dekomprese}.
.3 EncodeNode.\DTcomment{třída reprezentující frázi/uzel pro kompresi}.
.1 lzW.
.2 dictionary.
.3 DecodeDictionary.java.\DTcomment{slovník dekomprese}.
.3 EncodeDictionary.java.\DTcomment{slovník komprese}.
.2 LZW.java.\DTcomment{třída volající metody komprese nebo dekomprese}.
.2 LZWClient.java.\DTcomment{klient, spustitelný přes příkazovou řádku}.
.2 LZWProviderParameters.java\DTcomment{třída obsahující všechny parametry}.
.2 LZWTest.java\DTcomment{testovací třída}.
.1 triplet.
.2 coder.
.3 LZWTripletCoder.java\DTcomment{Třída zrpacující vstup při kompresi i~dekompresi, dědí ze třídy \classname{TripletCoder}}.
}
\renewcommand\figurename{Struktura}
\caption{adresářová struktura metody LZW}
\label{dirtree}
\end{figure}
\subsection{Parametry a hlavička souboru}
Metoda má totožnou hlavičku i nastavitelné parametry jako LZ78.
\subsection{Implementace komprese}
Kompresi zajišťuje metoda \classname{encode} uvnitř třídy \classname{LZWTripletCoder}.
Od imlementace komprese LZ78 se tato implementace liší pouze v~chování při zápisu tripletu, který má pouze jedinou složku: $$ (i) $$ Zapisuje totiž pouze index ve slovníku. Poté přidá nového potomka aktualnímu uzlu, s~hodnotou posledního načteného bytu. Následně neposune ukazatel do kořene stromu, jako je tomu u~LZ78, ale do potomka kořene, který má hodnotu jako zpracovávaný byte.
\subsection{Implementace dekomprese}
Dempresi zajišťuje metoda \classname{decode} uvnitř třídy \classname{LZWTripletCoder}.
Třída \classname{DecodeDictionary} ve složce \classname{lzw} representuje slovník, který používá struktůru stromu. Jeho uzly jsou uloženy v~poli, aby bylo možné hledat index fráze v~konstantní složitosti. Fráze se pak sestavý pomocí rekurzivního procházení přes rodiče až do kořene.
Hlavním rozdíl proti dekompresi LZ78 je, že načtený index z~tripletu nemusí být ve slovníku. V~takovém případě je dekódovaný řetězec stejný jako poslední přidaná fráze. Do stromu se přidá uzel s~hodnotou, která odpovídá prvnímu znaku naposledy přidané fráze. Tento uzel je potomkem naposledy přidaného uzlu.
Pokud index ve slovníku je, načte se příslušná fráze. Tato fráze se zapíše do souboru. Do slovníku přidej předchozímu použitému uzlu potomka s~hodnotou prvního znaku fráze.
\subsection{Spustitelný klient}
Klient metody LZW může být spuštěn s~těmito přepínači:
\begin{itemize}
\item \textbf{-h} -- vypíše nápovědu
\item \textbf{-d} -- spustí dekompresi vstupního souboru, s~tímto přepínačem není potřeba zadávat další parametry, program je bude ignorovat, protože si načte hlavičku, ve které jsou všechny potřebné parametry
\item \textbf{-nc <$e$>} -- tento přepínač říká, kolik maximálně frází muže být ve slovníku ($ 2^{e-1} $)
\item \textbf{-p <$n$>} -- tento přepínač říká, po jak velkých částech bude probíhat komprese (v~bytech)
\end{itemize}
Poznámka: Pokud při kompresi některý z~posledních dvou přepínačů chybí nebo je v~některém chyba, metoda se zavolá s~výchozími parametry, které jsou: -nc $17 $ -p $ 1 000 000 $.\newpage
\chapter{Testovaní}
Při určování kvality algoritmu se obvykle zjišťuje efektivita a časová náročnost. Efektivitu jsem se rozhodl vyjádřit pomocí kompresního poměru. Ten se vypočítá jako podíl velikostí zkomprimovaného a původního souboru. Časová naročnost je udaj, za kolik sekund program dosáhne správného výstupu.
Všechny tři metody jsou efektivní na datech, kde se opakují podřetězce, tedy například na běžném anglickém textu. Proto jsem se rozhodl k~testování použít korpus Calgary. Ten se skládá z~18 souborů s~anglickým textem o~celkové velikosti 3 190 KB. Abych demonstroval i~nevýhody těchto algoritmů, jako druhý korpus použiji ten s~názvem Prague. Tak zvaný pražský korpus je specifický svou různorodostí. Obsahuje totiž soubory s~textem i s~náhodnými daty o~velikosti 56 900 KB. Dosáhnout dobrého kompresního poměru na pražském korpusu je obecně velmi těžké.
Všechna měření uvedená v~této kapitole byla pořízena na počítači s~těmito parametry:
Procesor -- Intel Core i7 (frekvence jednoho jádra - 2,5 GHz)
RAM -- 8 GB
Operační systém -- Windows 10 (testování -- příkazová řádka Git Bash)
\section{Měření LZ77}
V~tabulkách \ref{table:lz77Cal} a \ref{table:lz77Prag} můžete vidět statistiku běhu algoritmu LZ77 na korpusech Calgary a Prague v~závislosti na vstupním parametru $ e $. Ostatní parametry se při testování neměnily. Velikost aktualního okénka je 8 tedy 128 znaků a velikost částí je 2 miliony bytů (2 MB).
Jak je vidět v~obou tabulkách měření (\ref{table:lz77Cal} a \ref{table:lz77Prag}), hlavní problém metody LZ77 je rostoucí časová složitost s~velikostí prohlížecího okna. Zjednodušeně by se dalo říct, že s~velikostí parametru $ e $ roste složitost komprese exponencialně. Tomu odpovídají i naměřené časy. Komprese s~parametrem $ e $ trvá téměř dvojnásobný čas než s~$ e-1 $ a čtyřnásobný než s~$ e-2 $. Nicméně kompresní poměr je poměrně dobrý. Především u~korpusu Calgary.
Zajímavým poznatkem měření je mírně klesající doba dekomprese. S~větším parametrem klesá kompresní poměr, což znamená, že se zmenšuje i počet tripletů v~souboru. Klesající tendence doby dekomprese je způsobená menší režijí na načítání a zpracování tripletů. Z~dat v~tabulkách je také vidět, že složitost dekomprese nezávisí na $ e $.
Z~obou tabulek je patrné, že s~rostoucím parametrem $ e $, se zlepšuje kompresní poměr, ovšem doba běhu komprese exponencialně roste. Nicméně na korpusu Calgary došlo k~poměrně dobré kompresi již při parametru 12, což odpovídá prohlížecímu oknu velikosti 2048 znaků. Oproti tomu na Prague není komprese dobrá ani při parametru 15, což odpovídá 16384 znakům v~prohlížecím okně. Je také patrné, že při testování na Calgary se kompresní poměr zlepšuje rychleji než na Prague. Jinými slovy pomyslná křivka kompresního poměru klesá rychleji u~Calgary.
Neefektivní kompresi na korpusu Prague způsobuje především velká náhodnost dat. Algoritmus nenachází delší prefixy a ve spoustě případů zapisuje triplet, který zabírá více místa než řetězec, který kóduje.
V~tabulce \ref{table:lz77Cal} uvádím pouze hodnoty parametru $ e $ od 10 do 17. Je tomu tak proto, že $ e < 10 $ se témeř nepoužívá, kvůli špatné efektivitě algoritmu a $ e > 17 $ už kompresi v~tomto případě nezlepšilo. V tabulce \ref{table:lz77Prag} je tomu pro $ e < 10 $ obdobně. Pro $ e > 15 $ běží již algoritmus přiliž dlouho a je tedy nepoužitelný. Pro představu pokud $ e = 16 $ algoritmus běží zhruba 10 minut a pro $ e = 17 $ 20 minut.
Ačkoliv se může z~tabulek zdát, že čím větší $ e $, tím lepší kompresní poměrn není tomu tak. Pro každý soubor existuje hranice, kdy už se komprese přestane zlepšovat. Způsobuje to zapisování čísel do tripletů. Parametrem $ e $ se nespecifikuje pouze velikost oken, ale i počet bitů potřebný pro zápis čísel do tripletu. Při příliš velkém $ e $ se stane, že pro zapisování tripletů bude používáno více bitů, ale jejich počet zůstane téměř stejný jako u~menších $ e $.
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
\begin{table}[H]
\centering
\begin{tabular}{| l | l | l | l | l | l | l | l | l |}
\hline
Parametr $ e $ & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ \hline
Kompresní poměr & 0,75 & 0,65 & 0,60 & 0,57 & 0,53 & 0,51 & 0,49 & 0,47 \\ \hline
Čas komprese (s) & 3,9 & 4,4 & 5,5 & 7,5 & 12,0 & 20,5 & 32,6 & 57,0 \\ \hline
Čas dekomprese (s) & 3,5 & 3,1 & 3,0 & 2,9 & 3,1 & 3,1 & 3,0 & 2,8 \\
\hline
\end{tabular}
\caption{testování LZ77 na Calgary}
\label{table:lz77Cal}
\end{table}
\begin{table}[H]
\centering
\begin{tabular}{| l | l | l | l | l | l | l |}
\hline
Parametr $ e $ & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline
Kompresní poměr & 0,85 & 0,85 & 0,84 & 0,83 & 0,80 & 0,78 \\ \hline
Čas komprese (s) & 30,9 & 42,6 & 62,5 & 103,0 & 180,0 & 330,5 \\ \hline
Čas dekomprese (s) & 34,6 & 32,8 & 31,5 & 30,5 & 27,5 & 26,9 \\
\hline
\end{tabular}
\caption{testování LZ77 na Prague}
\label{table:lz77Prag}
\end{table}
\section{Měření LZ78}
V tomto měření byla pro dekompresi použita implementace pomocí stromu.
Podobně jako u~měření LZ77, i zde dopadlo lépe testování na Calgary. Korpus Prague má příliš náhodná data a slovník vytváří pouze krátké fráze.
U~této a LZW metody jsem měřil i hloubku stromů, které reprezentují slovník. Zatím co u~Calgary meli slovníky jednotlivých částí souboru obvykle hloubku kolem sta, u~Prague ve většině případů nepřesáhla deset. V~některých případech byla hloubka pouze tři. Což znamená, že nejdelší zakódovaný řetězec mel délku tři. To se muže zdát jako nesmysl, ale do prvních třech pater stromu se vejde ($ 256^{2} + 256^{3} $) podřetězců delky dva a tři. To je 16 842 752 uzlů, což více než osmkrát přesahuje maximální počet uzlů ve slovníku pro parametr 22. K~těmto případům obvykle docházé na datech s~vysokou entropií. Z toho důvodu se tyto metody nepoužívají pro komprimaci obrázků. Ve vetšině případů je totiž zvětšují.
Z~naměřených dat v~tabulkách \ref{table:lz78Cal} a \ref{table:lz78Prag} je vidět, že mé odhady složitosti byly správné. Rychlost komprese i dekomprese je přibližně stejná a nezávisí na velikosti parametru $ e $. Nicméně čas komprese mírně roste s~vyšším parametrem $ e $, kdežto dekomprese mírně klesá. Zatímco u~komprese je to způsobeno větší režijí při přidávání frází do slovníku, u~dekomprese se jedná o~stejný důvod jako u~LZ77. S~vyšším parametrem se snižuje počet tripletů a tím i režije s~jejich načítáním a zpracováním.
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
Korpus Calgary dokázala metoda LZ77 zmenšit na 47~\% původní velikosti, což je nejlepší výsledek z~měření, nicméně metoda LZ78 zmenší Calgary na 51~\% za 35 krát kratší dobu než LZ77. Dá se tedy říci, že metoda LZ78 provádí podobně efektivní kompresi v~mnohem lepším čase.
\begin{table}[H]
\centering
\begin{tabular}{| l | l | l | l | l | l | l |}
\hline
Parametr $ e $ & 16 & 17 & 18 & 19 & 20 & 21 \\ \hline
Kompresní poměr & 0,67 & 0,62 & 0,60 & 0,54 & 0,53 & 0,51 \\ \hline
Čas komprese (s) & 1,4 & 1,5 & 1,5 & 1,5 & 1,6 & 1,6 \\ \hline
Čas dekomprese (s) & 1,9 & 1,8 & 1,8 & 1,7 & 1,7 & 1,7 \\
\hline
\end{tabular}
\caption{testování LZ78 na Calgary}
\label{table:lz78Cal}
\end{table}
\begin{table}[H]
\centering
\begin{tabular}{| l | l | l | l | l | l | l |}
\hline
Parametr $ e $ & 17 & 18 & 19 & 20 & 21 & 22 \\ \hline
Kompresní poměr & 0,81 & 0,76 & 0,74 & 0,75 & 0,75 & 0,75 \\ \hline
Čas komprese (s) & 13,4 & 13,9 & 13,9 & 14,5 & 14,6 & 15,0 \\ \hline
Čas dekomprese (s) & 24,5 & 23,8 & 21,8 & 21,0 & 22,7 & 22,1 \\
\hline
\end{tabular}
\caption{testování LZ78 na Prague}
\label{table:lz78Prag}
\end{table}
\pagebreak
\section{Měření LZW}
Metoda LZW je v mnoha ohledech podobná jako LZ78. Není tomu jinak ani u výsledků měření. Ty dopadly velmi podobně, co se rychlosti komprese týká, nicméně LZW dosáhla stejného komprimačního poměru s nižším parametrem. Při porovnání tabulek \ref{table:lzwCal} a \ref{table:lz78Cal} můžeme pozorovat, že při $ e = 20 $ byl komprimační poměr u LZW na korpusu Calgary lepší, než u LZ78.
Podobně jako u ostatních metod není čas dekomprese závislý na vstupním parametru $ e $. Je ovlivněn počtem tripletů na vstupu, nicméně jak jsem již psal u předchozích metod, ani zde neznamená vyšší parametr lepší kompresi.
V tabulce \ref{table:lzwPrag} je vidět, že od parametru $ e=20 $ se kompresní poměr nezlepšuje. Příčinou je rostoucí velikost tripletů zatímco jejich množství se zmenšuje jen velmi málo nebo vůbec. K tomu obvykle dochází, pokud se slovník nenaplní frázemi. To nastane v případě, že je parametr příliš velký oproti velikosti části souboru, který komprimuje. Tento případ nastal u měření s parametrem $ e = 21 $ a $ e = 22 $ v tabulce \ref{table:lzwPrag}.
Z dat je patrné že komprese i dekomprese probíhají velmi rychle.
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
\begin{table}[H]
\centering
\begin{tabular}{| l | l | l | l | l | l | l | l |}
\hline
Parametr $ e $ & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ \hline
Kompresní poměr & 0,76 & 0,73 & 0,68 & 0,64 & 0,59 & 0,54 & 0,50 \\ \hline
Čas komprese (s) & 1,4 & 1,4 & 1,4 & 1,5 & 1,5 & 1,6 & 1,6 \\ \hline
Čas dekomprese (s) & 2,1 & 2,0 & 1,9 & 1,9 & 1,8 & 1,8 & 1,7 \\
\hline
\end{tabular}
\caption{testování LZW na Calgary}
\label{table:lzwCal}
\end{table}
\begin{table}[H]
\centering
\begin{tabular}{| l | l | l | l | l | l | l |}
\hline
Parametr $ e $ & 17 & 18 & 19 & 20 & 21 & 22 \\ \hline
Kompresní poměr & 0,89 & 0,86 & 0,80 & 0,75 & 0,75 & 0,75 \\ \hline
Čas komprese (s) & 12,3 & 12,8 & 14,2 & 14,7 & 15,3 & 15,5 \\ \hline
Čas dekomprese (s) & 29,5 & 28,3 & 25,3 & 24,2 & 24,1 & 24,1 \\
\hline
\end{tabular}
\caption{testování LZW na Prague}
\label{table:lzwPrag}
\end{table}
\begin{conclusion}
Cílem této práce bylo navrhnout, analyzovat, implementovat a testovat kompresní algoritmy LZ77, LZ78 a LZW. Implementace byla provedena jako součást knihovny SCT.
Výsledkem práce je knihovna SCT rozšířená o výše zmíněné algoritmy. Analýza těchto metod mino jiné ukázala, že nejsou vhodné pro data s vysokou datovou entropií. Nicméně i přesto se hodí pro komprimaci běžného textu, případně i dat, kde se opakují delší podřetězce. Metody LZ78 a LZW dosahují v kratším čase podobného kompresního poměru jako LZ77. Je tedy možné je označit za efektivnější.
Všechny metody byly testovány na předem zvolených korpusech Calgary a Prague, aby bylo možné výsledky porovnávat. Všem metodám se povedlo korpus Calgary zmenšit o zhruba 50 \% a Prague o 25 \%.
I přes své nevýhody jsou metody poměrně efektivní a je možné je prostřednictvým knihovny SCT užívat v praxi.
\end{conclusion}
\bibliographystyle{csn690}
\begin{thebibliography}{1}
\bibitem{komprese}
\textit{Data Compression} [online]. [cit. 2018-04-22]. Dostupné z: \url{https://www.techopedia.com/definition/884/data-compression}
\bibitem{pojmy}
\textit{Lexikon pojmů} [online]. [cit. 2018-05-07]. Dostupné z: \url{http://stringology.org/DataCompression/lexikon.html}
\bibitem{entropie}
\textit{Informace, entropie a fyzika} [online]. [cit. 2018-05-07]. Dostupné z: \url{https://popelka.ms.mff.cuni.cz/~lessner/mw/index.php/U\%C4\%8Debnice/Informace/Informace,_entropie_a_fyzika}
\bibitem{crush}
\textit{Crush} [online]. [cit. 2018-04-23]. Dostupné z: \url{https://sourceforge.net/projects/crush}
\bibitem{inspire}
\textit{LZMA Compression} [online]. [cit. 2018-04-23]. Dostupné z: \url{https://www.advancedinstaller.com/user-guide/lzma-compression.html}
\bibitem{lzwEN}
\textit{LZW} [online]. [cit. 2018-04-23]. Dostupné z: \url{https://www.prepressure.com/library/compression-algorithm/lzw}
\bibitem{req}
\textit{Modelování požadavků} [online]. [cit. 2018-04-23]. Dostupné z: \url{https://edux.fit.cvut.cz/oppa/BI-SI1/prednasky/BI-SI1-P03m.pdf}
\bibitem{sct}
\textit{Small compression toolkit} [online]. [cit. 2018-05-06]. Dostupné z: \url{https://gitlab.fit.cvut.cz/polacrad/sct}
\bibitem{vohoLZ77}
\textit{Algoritmus LZ77} [online]. [cit. 2018-04-25]. Dostupné z: \url{http://voho.eu/wiki/algoritmus-lz77/}
\bibitem{stringologyLZ78}
\textit{Algoritmus LZ78} [online]. [cit. 2018-04-28]. Dostupné z: \url{http://stringology.org/DataCompression/lz78/index_cs.html}
\bibitem{algoLZ77_78}
\textit{Jan Holub. Data compression, dictionary metod I.} [online]. [cit. 2018-04-28]. Dostupné z: \url{https://edux.fit.cvut.cz/courses/MI-KOD/_media/lectures/05/mi-kod-05-dictionary.pdf}
\bibitem{algoLZW}
\textit{Jan Holub. Data compression, dictionary metod II.} [online]. [cit. 2018-04-28]. Dostupné z: \url{https://edux.fit.cvut.cz/courses/MI-KOD/_media/lectures/06/mi-kod-06-dictionary.pdf}
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
\bibitem{stringologyLZW}
\textit{Algoritmus LZW} [online]. [cit. 2018-04-28]. Dostupné z: \url{http://www.stringology.org/DataCompression/lzw-e/index_cs.html}
\end{thebibliography}
\appendix
\chapter{Seznam použitých zkratek}
% \printglossaries
\begin{description}
\item[SCT] Small compression toolkit
\item[LZ] Lempel-ziv
\end{description}
% % % % % % % % % % % % % % % % % % % % % % % % % % % %
% % Tuto kapitolu z výsledné práce ODSTRAŇTE.
% % % % % % % % % % % % % % % % % % % % % % % % % % % %
%
% \chapter{Návod k~použití této šablony}
%
% Tento dokument slouží jako základ pro napsání závěrečné práce na Fakultě informačních technologií ČVUT v~Praze.
%
% \section{Výběr základu}
%
% Vyberte si šablonu podle druhu práce (bakalářská, diplomová), jazyka (čeština, angličtina) a kódování (ASCII, \mbox{UTF-8}, \mbox{ISO-8859-2} neboli latin2 a nebo \mbox{Windows-1250}).
%
% V~české variantě naleznete šablony v~souborech pojmenovaných ve formátu práce\_kódování.tex. Typ může být:
% \begin{description}
% \item[BP] bakalářská práce,
% \item[DP] diplomová (magisterská) práce.
% \end{description}
% Kódování, ve kterém chcete psát, může být:
% \begin{description}
% \item[UTF-8] kódování Unicode,
% \item[ISO-8859-2] latin2,
% \item[Windows-1250] znaková sada 1250 Windows.
% \end{description}
% V~případě nejistoty ohledně kódování doporučujeme následující postup:
% \begin{enumerate}
% \item Otevřete šablony pro kódování UTF-8 v~editoru prostého textu, který chcete pro psaní práce použít -- pokud můžete texty s~diakritikou normálně přečíst, použijte tuto šablonu.
% \item V~opačném případě postupujte dále podle toho, jaký operační systém používáte:
% \begin{itemize}
% \item v~případě Windows použijte šablonu pro kódování \mbox{Windows-1250},
% \item jinak zkuste použít šablonu pro kódování \mbox{ISO-8859-2}.
% \end{itemize}
% \end{enumerate}
%
%
% V~anglické variantě jsou šablony pojmenované podle typu práce, možnosti jsou:
% \begin{description}
% \item[bachelors] bakalářská práce,
% \item[masters] diplomová (magisterská) práce.
% \end{description}
%
% \section{Použití šablony}
%
% Šablona je určena pro zpracování systémem \LaTeXe{}. Text je možné psát v~textovém editoru jako prostý text, lze však také využít specializovaný editor pro \LaTeX{}, např. Kile.
%
% Pro získání tisknutelného výstupu z~takto vytvořeného souboru použijte příkaz \verb|pdflatex|, kterému předáte cestu k~souboru jako parametr. Vhodný editor pro \LaTeX{} toto udělá za Vás. \verb|pdfcslatex| ani \verb|cslatex| \emph{nebudou} s~těmito šablonami fungovat.
%
% Více informací o~použití systému \LaTeX{} najdete např. v~\cite{wikilatex}.
%
% \subsection{Typografie}
%
% Při psaní dodržujte typografické konvence zvoleného jazyka. České \uv{uvozovky} zapisujte použitím příkazu \verb|\uv|, kterému v~parametru předáte text, jenž má být v~uvozovkách. Anglické otevírací uvozovky se v~\LaTeX{}u zadávají jako dva zpětné apostrofy, uzavírací uvozovky jako dva apostrofy. Často chybně uváděný symbol "{} (palce) nemá s~uvozovkami nic společného.
%
% Dále je třeba zabránit zalomení řádky mezi některými slovy, v~češtině např. za jednopísmennými předložkami a spojkami (vyjma \uv{a}). To docílíte vložením pružné nezalomitelné mezery -- znakem \texttt{\textasciitilde}. V~tomto případě to není třeba dělat ručně, lze použít program \verb|vlna|.
%
% Více o~typografii viz \cite{kobltypo}.
%
% \subsection{Obrázky}
%
% Pro umožnění vkládání obrázků je vhodné použít balíček \verb|graphicx|, samotné vložení se provede příkazem \verb|\includegraphics|. Takto je možné vkládat obrázky ve formátu PDF, PNG a JPEG jestliže používáte pdf\LaTeX{} nebo ve formátu EPS jestliže používáte \LaTeX{}. Doporučujeme preferovat vektorové obrázky před rastrovými (vyjma fotografií).
%
% \subsubsection{Získání vhodného formátu}
%
% Pro získání vektorových formátů PDF nebo EPS z~jiných lze použít některý z~vektorových grafických editorů. Pro převod rastrového obrázku na vektorový lze použít rasterizaci, kterou mnohé editory zvládají (např. Inkscape). Pro konverze lze použít též nástroje pro dávkové zpracování běžně dodávané s~\LaTeX{}em, např. \verb|epstopdf|.
%
% \subsubsection{Plovoucí prostředí}
%
% Příkazem \verb|\includegraphics| lze obrázky vkládat přímo, doporučujeme však použít plovoucí prostředí, konkrétně \verb|figure|. Například obrázek \ref{fig:float} byl vložen tímto způsobem. Vůbec přitom nevadí, když je obrázek umístěn jinde, než bylo původně zamýšleno -- je tomu tak hlavně kvůli dodržení typografických konvencí. Namísto vynucování konkrétní pozice obrázku doporučujeme používat odkazování z~textu (dvojice příkazů \verb|\label| a \verb|\ref|).
%
% \begin{figure}\centering
% \includegraphics[width=0.5\textwidth, angle=30]{cvut-logo-bw}
% \caption[Příklad obrázku]{Ukázkový obrázek v~plovoucím prostředí}\label{fig:float}
% \end{figure}
%
% \subsubsection{Verze obrázků}
%
% % Gnuplot BW i barevně
% Může se hodit mít více verzí stejného obrázku, např. pro barevný či černobílý tisk a nebo pro prezentaci. S~pomocí některých nástrojů na generování grafiky je to snadné.
%
% Máte-li například graf vytvořený v programu Gnuplot, můžete jeho černobílou variantu (viz obr. \ref{fig:gnuplot-bw}) vytvořit parametrem \verb|monochrome dashed| příkazu \verb|set term|. Barevnou variantu (viz obr. \ref{fig:gnuplot-col}) vhodnou na prezentace lze vytvořit parametrem \verb|colour solid|.
%
% \begin{figure}\centering
% \includegraphics{gnuplot-bw}
% \caption{Černobílá varianta obrázku generovaného programem Gnuplot}\label{fig:gnuplot-bw}
% \end{figure}
%
% \begin{figure}\centering
% \includegraphics{gnuplot-col}
% \caption{Barevná varianta obrázku generovaného programem Gnuplot}\label{fig:gnuplot-col}
% \end{figure}
%
%
% \subsection{Tabulky}
%
% Tabulky lze zadávat různě, např. v~prostředí \verb|tabular|, avšak pro jejich vkládání platí to samé, co pro obrázky -- použijte plovoucí prostředí, v~tomto případě \verb|table|. Například tabulka \ref{tab:matematika} byla vložena tímto způsobem.
%
% \begin{table}\centering
% \caption[Příklad tabulky]{Zadávání matematiky}\label{tab:matematika}
% \begin{tabular}{|l|l|c|c|}\hline
% Typ & Prostředí & \LaTeX{}ovská zkratka & \TeX{}ovská zkratka \tabularnewline \hline \hline
% Text & \verb|math| & \verb|\(...\)| & \verb|$...$| \tabularnewline \hline
% Displayed & \verb|displaymath| & \verb|\[...\]| & \verb|$$...$$| \tabularnewline \hline
% \end{tabular}
% \end{table}
%
% % % % % % % % % % % % % % % % % % % % % % % % % % % %
\chapter{Obsah přiloženého CD}
%upravte podle skutecnosti
\begin{figure}
\dirtree{%
.1 readme.txt\DTcomment{stručný popis obsahu CD}.
.1 exe\DTcomment{adresář se spustitelnou formou implementace}.
.1 src.
.2 impl\DTcomment{zdrojové kódy implementace}.
.2 thesis\DTcomment{zdrojová forma práce ve formátu \LaTeX{}}.
.1 text\DTcomment{text práce}.
.2 thesis.pdf\DTcomment{text práce ve formátu PDF}.
.2 thesis.ps\DTcomment{text práce ve formátu PS}.
}
\end{figure}
\end{document}