Eine Variante der Burrows-Wheeler Transformation mit Permutationen

Abstract

In der Datenkompression werden häufig verschiedene Verfahren miteinander kombiniert, um höhere Kompressionsraten zu erzielen. Die Burrows-Wheeler Transformation (BWT) komprimiert einen gegebenen Datenblock zwar nicht, sortiert ihn jedoch so um, dass er mit einfachen Verfahren wie der Huffman-Kodierung besser komprimiert werden kann und eignet sich daher als Vorverarbeitungsschritt. Sowohl die Transformation selbst als auch ihre Umkehrung sind in Linearzeit berechenbar. Bei der BWT werden Zeichen gruppiert, auf die gleiche oder ähnliche Zeichenketten, sogenannte Kontexte, folgen. Es werden also Ähnlichkeiten innerhalb der Eingabedaten genutzt, um einen besser komprimierbaren Datenblock zu erzeugen. Eine Variante der BWT nach Kufleitner erweitert diesen Begriff der Ähnlichkeit. Diese echte Verallgemeinerung der BWT nutzt Permutationen, um Teile der Eingabedaten so zu manipulieren, dass die Kontexte gleicher Zeichen ähnlicher und diese Zeichen damit besser gruppiert werden. Wir stellen hier diese Variante der BWT sowie Algorithmen für die Transformation und ihre Umkehrung vor. Die Burrows-Wheeler Transformation mit Permutationen (BWTP) wird darin erstmals veröffentlicht und ein Beweis für die Umkehrbarkeit dargestellt. Ein an {\ttfamily bzip2} angelehntes, im Rahmen dieser Diplomarbeit entwickeltes Datenkompressionsprogramm namens {\ttfamily bwt_enc} wird vorgestellt. Es kombiniert einen effizienten Algorithmus zur Berechnung der BWTP mit der Huffman-Kodierung und einigen anderen Verfahren. Die Auswirkung verschiedener Parameterkombinationen und Permutationen werden untersucht und {\ttfamily bwt_enc} wird mit mehreren verbreiteten Datenkompressionsprogrammen verglichen.