\begin{slide}{Burrwos-Wheeler-Transformation}

eine \emph{umkehrbare} Transformation,
die (im Allg.) einen viel besser komprimierbaren String erzeugt.

Beispiel: \verb|abraca|.

\begin{minipage}{0.5\textwidth}
alle zyklischen \\
Permutationen:
\begin{small}
\begin{verbatim}
("abraca",0)
("bracaa",1)
("racaab",2)
("acaabr",3)
("caabra",4)
("aabrac",5)
\end{verbatim}
\end{small}
\end{minipage}%
\begin{minipage}{0.5\textwidth}
diese sortieren \\
(lexikographisch):
\begin{small}
\begin{verbatim}
("aabrac",5)
("abraca",0)
("acaabr",3)
("bracaa",1)
("caabra",4)
("racaab",2)
\end{verbatim}
\end{small}
\end{minipage}

die Folge der letzten Buchstaben und die Position der 0:

\verb|("caraab", 1)| 

daraus kann man die Eingabe rekonstruieren!

\end{slide}

\begin{slide}{Burrows-Wheeler (II)}

der transformierte String läßt sich besser komprimieren
(z. B. mit move-to-front, Huffman)

\begin{small}
\begin{verbatim}
t? Ihr dr .. ahn geneig    ten Menge, .. r unbekann
taeuscht, ..  Glueck ge    ten sang;  .. ch die ers
talten, D .. nkende Ges    ten steige .. iebe Schat
te Lieb u ..  Kommt ers    ten, Die f .. nde Gestal
te Widerk .. h! der ers    ten, Wie i .. gt ihr wal
teh ich n .. uehn. Da s    ten, die,  .. nnt die Gu
teigen au .. Schatten s    ten, halbv .. h einer al
teigt; Me ..  um mich s    ten? Fuehl ..  festzuhal

hheeeeaeeeehheheeeoiohiieehoeeoeddeeeuieruebftfFeeebyueeea
fiieeeeeeeereeetfekeeeeuaeaneauleaste id   ur essa  sus   e  
 oaiiiininbnerr   riirr errsssnnlhmihgiigrshgflslebruhr
geggessssssnstllullssttnsrks haeisSszeaaeeseeatrlrFfmhqeehaaaalZjz 
\end{verbatim}
\end{small}


\end{slide}

\begin{slide}{Burrows-Wheeler (Rekonstruktion)}

(Bastel-Aufgabe/Auflösung)

\begin{itemize}
\item
  Codewort $L=caraab$, bestimme $F=\operatorname{sort}(L)=aaabcr$
\item
  berechne $Z = \operatorname{zip} (L, F)=  [ ca, aa, ra, ab, ac, br ] $.
\item
  sortiere: $\operatorname{sort}(Z)= [ aa, ab, ac, br, ca, ra ] $
\item
  verfolge Buchstaben entlang der Vertauschungen
\end{itemize}

Kann geschickt implementiert werden  (mit Abzählen statt Sortieren)
$\to$ Dekodierung geht schnell.

Kodierung geht auch schnell (Matrix muß nicht im Speicher stehen)

Algorithmus (Burrows-Wheeler $\to$ move-to-front $\to$ Huffman)
ist implementiert in \verb|bzip2|


\end{slide}
