Bachelorarbeit

Implementierung und Untersuchung zweier Kernkomponenten von bzip von Franz Brauße

Thema

Zusammenfassung

Es wird die adaptive Arithmetische Kodierung in Teilen basierend auf Sayoods Beschreibung implementiert, einige Optimierungen einzeln vorgestellt und anhand zweier Korpora untersucht, wie Rechengenauigkeit, Kompressionsgüte und -geschwindigkeit zusammenhängen. Die Vergleichsbasis bildet Saids FastAC. Dortig zusätzlich vorgenommene Optimierungen zur Geschwindigkeitssteigerung und deren Auswirkungen auf die Kompressionsgüte werden betrachtet.

Der zweite Teil umfasst einen Beweis der Korrektheit der Burrows-Wheeler-Transformation und eine Beschreibung der Implementierung derselben über effiziente Varianten des Multi-Key-Quicksort mit und ohne vorherigem Bucketsort-Schritt, die bzips Geschwindigkeit erreichen. Schließlich werden diese sowie die Standardsortieralgorithmen denen von bzip2 für einen Block gegenübergestellt.