Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2718
Authors: Riegger, Philipp M.
Title: Eine Variante der Burrows-Wheeler Transformation mit Permutationen
Other Titles: A variant of the Burrows-Wheeler transformation with permutations
Issue Date: 2011
metadata.ubs.publikation.typ: Abschlussarbeit (Diplom)
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-65867
http://elib.uni-stuttgart.de/handle/11682/2735
http://dx.doi.org/10.18419/opus-2718
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.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
DIP_3117.pdf481,84 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.