Praktische Evaluation zweier Lempel–Ziv Algorithmen mit platzsparenden Datenstrukturen

Beschreibung

Die Lempel-Ziv (LZ) Faktorisierung dient seit geraumer Zeit der verlustfreien Kompression von Daten. Dabei werden verschiedene Varianten von der ursprünglichen LZ77- und von der LZ78-Faktorisierung genutzt. Diese sind beispielsweise die Basis von den Kompressionstechniken Gzip, WinZip und 7zip. Auch GIF–- und PNG–-Dateien beinhalten LZ-Varianten. Man kann durch die Faktorisierung sich wiederholende Strukturen (z.B. in DNA) erkennen und diese nutzen um beispielsweise Datenstrukturen und auch Algorithmen effizienter zu gestalten. In den vielfältigen Einsatzgebieten wird die Berechnung der Faktorisierung oft als Flaschenhals betitelt, weswegen die Forschung an Algorithmen, die die Faktorisierung berechnen, wichtig ist. Dabei muss die Zeit- und Speicherkomplexität nicht nur theoretisch, sondern auch praktisch ermittelt werden. Deshalb behandelt diese Arbeit die praktische Umsetzung und Einordnung des Algorithmus aus Lempel-Ziv Computation In Compressed Space. Im zweiten Teil der Arbeit werden die Auswirkungen verschiedener Datenstrukturen für den klassischen LZ78 auf den Verbrauch von Speicher und Zeit betrachtet.

Typ

Bachelorarbeit.

Bearbeiter

Viktor Schäfer (2016).

Betreuer

 
Last modified: 2016-05-03 11:06 (external edit)
DokuWikiRSS-Feed