% Komprimierung ist allgegenwärtig. Beispielsweise findet eine andauernde
% Komprimierung bei den natürlichen Sprachen statt: Oft benutzte Wörter
% verkürzen sich im Laufe der Zeit: "Haus", "Geld", "Tisch".
% Dieser Vortrag erklärt anschaulich die Grundprinzipien der Komprimierung
% anhand dreier einfacher Kompressionsverfahren. Auch vergleichen wir die
% Effektivität der behandelten Verfahren.
\documentclass[12pt,compress]{beamer}
\usepackage{amsmath}
\usepackage{url}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage[ngerman]{babel}
\usepackage{ulem} % sout
\usepackage{multicol}
\usepackage{comment}
\usepackage{setspace}
% Manual syntax highlighting
\newcommand{\synfunc} [1]{\color{blue!50!black}#1\color{black}}
\newcommand{\synstr} [1]{\color{red!50!black}#1\color{black}}
\newcommand{\synvar} [1]{\color{purple!50!black}#1\color{black}}
\newcommand{\synclass} [1]{\color{green!50!black}#1\color{black}}
\newcommand{\syncomment}[1]{\color{blue!20!black}#1\color{black}}
\newcommand{\syncool} [1]{\color{beamer@blendedblue}#1\color{black}}
\newcommand{\synoder} {\ \ \color{black}$\vee$\ \ }
\newcommand{\hr} {\rule[4pt]{\textwidth}{0.1pt}\\}
\newcommand{\hicolor} [1]{\color[rgb]{0.6,0.2,0.8}#1\color{black}}
\newcommand{\synhilight}[1]{\hicolor{\textbf{#1}}}
\newcommand{\doofcomment}{\ \ \syncomment{\# :-(}}
\newcommand{\gutcomment} {\ \ \syncomment{\# :)}}
\title{Komprimierung}
\author{Ingo~Blechschmidt, \\ Michael~Hartmann}
\date{6. Dezember 2006}
\usetheme{Warsaw} %Warsaw, Berkeley?
\usecolortheme{seahorse}
\usefonttheme{serif}
\useinnertheme{rectangles}
\usepackage{bookman}
\setbeamercovered{transparent}
\begin{document}
\frame{\titlepage}
\frame[t]{
\frametitle{Inhalt}
\tableofcontents
}
\section[RLE]{Laufl"angenkodierung}
\frame[t]{
\frametitle{Lauflängenkodierung (RLE)}
\begin{itemize}
\item Idee: Ersetzung von sich direkt wiederholenden Zeichen durch eine
Anweisung
\item Beispiel: \\
\texttt{aaabbccccccde} → \\
3 a, bb, 6 c, de
\item Sehr leicht umsetzbar
\item Effizient nur in Spezialfällen, beispspielsweise großen einfarbigen Bereichen
in Bildern
\end{itemize}
}
\section[Arithm.]{Arithmetische Kodierung}
\frame[t]{
\frametitle{Arithmetische Kodierung}
\begin{enumerate}
\item Unterteilung eines Einheitsintervalls entsprechend den relativen Häufigkeiten der
Zeichen des Texts
\item Weitere Unterteilung bis alle Zeichen genutzt
\item Kodierung einer beliebigen Zahl des schärfsten Intervalls
\end{enumerate}
}
\frame{
\begin{center}
\includegraphics[scale=0.45]{images/intervallunterteilung.png}
\end{center}
}
\section[Shannon--Fano]{Shannon--Fano-Kodierung}
\subsection{Grundideen}
\frame[t]{
\frametitle{Shannon--Fano-Kodierung}
\begin{block}{Shannon--Fano-Kodierung}
Entropiekodierung ("`Kompressionsverfahren"')
\end{block}
%Grundidee: Möglichst hohe Entropie durch effiziente Darstellung
\begin{itemize}
\item
\begin{tabbing}
Darstellung \= \textsl{häufiger} \= Zeichen durch \= \textsl{kurze} \= Bitfolgen \kill
Darstellung \> \textsl{häufiger} \> Zeichen durch \> \textsl{kurze} \> Bitfolgen; \\
Darstellung \> \textsl{seltener} \> Zeichen durch \> \textsl{lange} \> Bitfolgen
\end{tabbing}
\item Eindeutigkeit der Bitfolgen ("`Präfixfreiheit"')
\end{itemize}
Problembeispiel:
$A \mapsto 10 \quad B \mapsto 01 \quad C \mapsto 0$ \bigskip
$\left.\begin{array}{@{}l}
ABC \mapsto 10010 \\
ACA \mapsto 10010
\end{array}\right\}$ nicht eindeutig
}
\subsection{Algorithmus}
\frame[t]{
\frametitle{Algorithmus}
\begin{enumerate}
\item Sortierung der Zeichen nach rel. Häufigkeit
\item Einteilung der Zeichen in zwei Gruppen, sodass Summen der
Häufigkeiten etwa gleich
\item So lange fortfahren, bis Entsprechung jedes Zeichens durch einen Pfad
im Baum
\end{enumerate}
}
\subsection{Beispiel}
\frame[t]{
\frametitle{Beispiel}
Text (39 Zeichen): \\
{\small ABADDCCAABABEDAECBDDDAAAABAAAABBCAECECE}
\medskip
\begin{tabular}{@{}l|rrrrr}
Zeichen & A & B & C & D & E \\\hline
Abs. Häufigkeit & 15 & 7 & 6 & 6 & 5
\end{tabular}
\vspace*{5mm}%
\includegraphics[scale=0.3]{images/shannon-baum.png} % ausprobieren? wie meinst? kompilieren und anschauen. nein, auf keinen fall, wer weiss, was da nicht alles kaputt gehen kann. try 'n error
% wollen wir das bild um 90° grad drehen (geht einfach) aber dann muss man halt den kopf neigen
% oder wir schneiden die folie aus
}
\frame[t]{
\frametitle{Beispiel}
\hspace*{-1cm}%
\begin{minipage}{1.1\textwidth}\begin{multicols}{2}
\scriptsize
\begin{itemize}
\item Original \\ ($117 \,\mathrm{bit}$; Entropie $\approx 0{,}82 \,\mathrm{bit}$): \\
{\tiny
00000100001101101001000000000
10000011000110001000100010110
11011000000000000001000000000
000001001010000100010100010100
}\bigskip
\begin{tabular}{@{}l|rrrrr}
Zeichen & A & B & C & D & E \\\hline
Abs. Häufigkeit & 15 & 7 & 6 & 6 & 5 \\\hline
Benötigte Bits & 3 & 3 & 3 & 3 & 3
\end{tabular}\bigskip
\begin{tabular}{@{}l|rr}
Bit & 0 & 1 \\\hline
Abs. Häufigkeit & 87 & 30
\end{tabular}\bigskip
$A \mapsto 000$ \\
$B \mapsto 001$ \\
$C \mapsto 010$ \\
$D \mapsto 011$ \\
$E \mapsto 100$
\columnbreak
\item Komprimiert \\ ($89 \,\mathrm{bit}$; Entropie $\approx 0{,}99261 \,\mathrm{bit}$ (!)): \\
{\tiny
1110110010010101111110
1110000001110000110001
0010011111111110111111
11101001110000100001000
}\bigskip
\begin{tabular}{@{}l|rrrrr}
Zeichen & A & B & C & D & E \\\hline
Abs. Häufigkeit & 15 & 7 & 6 & 6 & 5 \\\hline
Benötigte Bits & 2 & 2 & 2 & 3 & 3
\end{tabular}\bigskip
% 11101100100101011111101110000001110000110001001001111111111011111111101001110000100001000 (0.99 WOW! fast 1!!!) die entropie koennte doch 8 sein? nicht bei einem alphabet von nur zwei zeichen, dort ist die maximale entropie ld 2 = 1 optimal
% 40/89*-l(40/89)/l(2) + 49/89*-l(49/89)/l(2) =
% .99261088987494049154
\begin{tabular}{@{}l|rr}
Bit & 0 & 1 \\\hline
Abs. Häufigkeit & 40 & 49
\end{tabular}\bigskip
% 11 B 10 C 01 D 001 E 000
$A \mapsto 11$ \\
$B \mapsto 10$ \\
$C \mapsto 01$ \\
$D \mapsto 001$ \\
$E \mapsto 000$
\end{itemize}
\end{multicols}\end{minipage}
}
\section[Huffman]{Huffman-Kodierung}
\subsection{Algorithmus}
\frame[t]{
\frametitle{Huffman-Kodierung: Algorithmus}
\begin{enumerate}
\item Wald erstellen mit allen vorkommenden Zeichen
\item Neuen Baum erstellen; die beiden Bäume mit geringster Häufigkeit als
Blätter nutzen
\item So lange fortfahren, bis nur noch ein Baum vorhanden
\end{enumerate}
}
\subsection{Beispiel}
\frame[t]{
\frametitle{Beispiel}
Text (39 Zeichen): \\
{\small ABADDCCAABABEDAECBDDDAAAABAAAABBCAECECE}
\medskip
\begin{tabular}{@{}l|rrrrr}
Zeichen & A & B & C & D & E \\\hline
Abs. Häufigkeit & 15 & 7 & 6 & 6 & 5
\end{tabular}
\vspace*{5mm}%
\includegraphics[scale=0.35]{images/huffman-baum.png}
}
\frame[t]{
\frametitle{Beispiel}
\hspace*{-1cm}%
\begin{minipage}{1.1\textwidth}\begin{multicols}{2}
\scriptsize
\begin{itemize}
\item Original \\ ($117 \,\mathrm{bit}$; Entropie $\approx 0{,}82 \,\mathrm{bit}$): \\
{\tiny
00000100001101101001000000000
10000011000110001000100010110
11011000000000000001000000000
000001001010000100010100010100
}\bigskip
\begin{tabular}{@{}l|rrrrr}
Zeichen & A & B & C & D & E \\\hline
Abs. Häufigkeit & 15 & 7 & 6 & 6 & 5 \\\hline
Benötigte Bits & 3 & 3 & 3 & 3 & 3
\end{tabular}\bigskip
\begin{tabular}{@{}l|rr}
Bit & 0 & 1 \\\hline
Abs. Häufigkeit & 87 & 30
\end{tabular}\bigskip
$A \mapsto 000$ \\
$B \mapsto 001$ \\
$C \mapsto 010$ \\
$D \mapsto 011$ \\
$E \mapsto 100$
\columnbreak
\item Komprimiert \\ ($87 \,\mathrm{bit}$; Entropie $\approx 0{,}99762 \,\mathrm{bit}$ (!!!)): \\
{\tiny
0100011011010110100100
0100111110011110110011
0110110000010000001001
001010111101111101111
}\bigskip
\begin{tabular}{@{}l|rrrrr}
Zeichen & A & B & C & D & E \\\hline
Abs. Häufigkeit & 15 & 7 & 6 & 6 & 5 \\\hline
Benötigte Bits & 1 & 3 & 3 & 3 & 3
\end{tabular}\bigskip
\begin{tabular}{@{}l|rr}
Bit & 0 & 1 \\\hline
Abs. Häufigkeit & 41 & 46
\end{tabular}\bigskip
% 0 B 100 C 101 D 110 E 111
$A \mapsto 0$ \\
$B \mapsto 100$ \\
$C \mapsto 101$ \\
$D \mapsto 110$ \\
$E \mapsto 111$
\end{itemize}
\end{multicols}\end{minipage}
}
\subsection{Verwendung}
\frame[t]{
\frametitle{Verwendung}
Verwendung von Deflate (LZ77 kombiniert mit Huffman-Kodierung):
\begin{itemize}
\item zip
\item gzip
\item png
\item tiff
\item pdf
\item cab
\end{itemize}
}
\section[Grenzen]{Grenzen der Komprimierbarkeit}
\frame[t]{
\frametitle{Grenzen der Komprimierbarkeit}
\begin{itemize}
\item Entropie als untere Schranke der Komprimierbarkeit
\item Beweis der Nichtexistenz \\
eines Perfekten Verfahrens™:
\begin{itemize}
\item \textsl{Annahme:} Existenz eines Verfahrens, dass jeden beliebigen
Text um ein Bit verkürzt
\item \textsl{Dann:} Rekursive Anwendung denkbar
\item \textsl{Schluss:} Komprimierung jedes beliebigen Texts auf ein Bit
\item \textsl{Aber:} $256 < \infty$!
\end{itemize}
\end{itemize}
}
\frame{
\begin{center}
\Huge Fragen?
\end{center}
}
\appendix
\section{Bildquellen}
\frame[t]{
\frametitle{Bildquellen}
\scriptsize
\begin{itemize}
\item \url{http://upload.wikimedia.org/wikipedia/de/d/db/ShannonCodeAlg.png}
\item \url{http://upload.wikimedia.org/wikipedia/de/d/d8/HuffmanCodeAlg.png}
\item \url{http://upload.wikimedia.org/wikipedia/de/5/56/ArithmetischesCodierenBeispiel.png}
\end{itemize}
}
\end{document}
Download