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
39
40
41
42
% 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{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
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
% ODTUD DAL VSE ZMENTE
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
\department{Katedra softwarového inženýrství}
\title{Implementace kompresních metod LZ77, LZ78 a~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 odborné vedení, pomoc a vstřícnost při vedení bakalařské práce.}
\abstractCS{Tato bakalař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 vhodným návrhem a~popisem 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~30~\%. Přínosem této práce je přispění do knihovny, která může v budoucnu usnadnit některým vývojářům práci.}
\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 in~the~future 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~30~\%. The benefit of~this work is contributing to a~library that can make it easier for some developers to work in the~future.}
\placeForDeclarationOfAuthenticity{V~Praze}
\declarationOfAuthenticityOption{4} %volba Prohlášení (číslo 1-6)
\keywordsCS{Komprese dat, dekomprese dat, chaining, Java, LZ77, LZ78, LZW, SCT}
\keywordsEN{Compression, decompression, chaining, 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, prostě si uložíte několika gigabytový soubor na svůj pevný disk s~kapacitou stovek gigabytů. Ovšem tehdy měli pevné disky 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, 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.
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 následné otestování z~hlediska časové a~paměťové náročnosti, případně porovnání efektivity se stávajícími kompresními algoritmy v~knihovně. Tato knihovna by pak měla ušetřit spoustu práce programátorům, kteří díky ní nebudou muset vymýšlet vlastní implementaci těchto algoritmů.
\section{Existující řešení}
V~knihovně je zatím naimplementovaná pouze metoda ACB, je tedy jasné, že mnou zvolené algoritmy zatím neobsahuje. Jedná se o~poměrně zastaralé metody, které vznikli 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ů. LZ78 byla taktéž předlohou pro jiné algoritmy například LZW nebo BTLZ. \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}
\begin{conclusion}
%sem napište závěr Vaší práce
\end{conclusion}
\bibliographystyle{csn690}
\begin{thebibliography}{1}
\bibitem{komprese}
\textit{Komprese dat} [online]. [cit. 2018-04-22]. Wikipedie. Dostupné z: \url{https://cs.wikipedia.org/wiki/Komprese_dat}
\bibitem{crush}
\textit{Crush} [online]. [cit. 2018-04-23]. Dostupné z: \url{https://sourceforge.net/projects/crush}
\bibitem{inspire}
\textit{LZ77 and LZ78} [online]. [cit. 2018-04-23]. Wikipedie. Dostupné z: \url{https://en.wikipedia.org/wiki/LZ77_and_LZ78}
\bibitem{lzwEN}
\textit{LZW} [online]. [cit. 2018-04-23]. Dostupné z: \url{https://www.prepressure.com/library/compression-algorithm/lzw}
\bibitem{req}
\textit{Analýza požadavků} [online]. [cit. 2018-04-23]. Wikipedie. Dostupné z: \url{https://cs.wikipedia.org/wiki/Anal\%C3\%BDza_po\%C5\%BEadavk\%C5\%AF}
\end{thebibliography}
\appendix
\chapter{Seznam použitých zkratek}
% \printglossaries
\begin{description}
\item[SCT] Small compression toolkit
\item[LZ] Lempel-ziv
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
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
\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}