Parallele Approximation der Lempel-Ziv-77-Faktorisierung

Die Lempel-Ziv-77-Faktorisierung (LZ77) ist der Grundbaustein für viele bewährte Kompressionsverfahren wie gzip, LZMA, Brotli uvm. Die Eingabe wird in so genannte Faktoren zerlegt mit dem Ziel, sich wiederholende Phrasen durch Referenzen auf vorherige Vorkommen zu erstzen. Für die exakte (und vollständige) Berechnung der Faktorisierung wird jedoch linear viel Speicher und Zeit in der Eingagegröße benötigt, insbesondere bezüglich des Speichers mit hohem konstanten Faktor. Es ist daher üblich, den Speicherbedarf durch die Nutzung gleitender Fenster zu deckeln, sowie Heuristiken einzuführen, die eine effizientere Berechnung auf Kosten geringerer Kompressionsgüte ermöglichen.

In [1] wird ein Verfahren gezeigt, welches eine Approximation der LZ77-Faktorisierung mit Gütegarantie berechnet. In einer bereits abgeschlossenen Bachelorarbeit wurde der Algorithmus implementiert. Hier hat sich gezeigt, dass die Approximation vielversprechende Ergebnisse erzielt, auch wenn nicht alle in der Theorie beschriebenen Phasen zur Verbesserung der Güte durchlaufen werden.

In dieser Arbeit sollen die ersten beiden Phasen des Algorithmus im Shared-Memory-Modell (z.B. mit OpenMP) parallelisiert werden. Hierbei stellt die erste Phase des Algorithmus, in welcher parallel eine Hashtabelle aufgebaut werden muss, eine besondere Herausforderung dar. Die Arbeit soll eine praktische Evaluation in Form einer C++-Implementierung und Benchmarks als Ergebnis haben, wobei insbesondere Skalierungs-Experimente für eine Bestimmung des parallelen Speedups durchgeführt werden sollen.

Typ

Masterarbeit, bei Vorkenntnissen auch Bachelorarbeit.

Das sollten Sie mitbringen

  • Spaß an algorithmischen Problemstellungen
  • gute Kenntnisse in einer speicher/laufzeit-effizienten Programmiersprache (C++, Rust, etc.)
  • ggf. Erfahrung mit OpenMP oder anderen Frameworks für parallele Algorithmen

Literatur/Software

[1]: Fischer, Gagie, Gawrychowski & Kociumaka: Approximating LZ77 via Small-Space Multiple-Pattern Matching, arXiv abs/1504.06647 (2015)

Betreuer

Bei Interesse wenden Sie sich bitte an Patrick Dinklage und Johannes Fischer.

 
Last modified: 2022-04-12 09:34 by Patrick Dinklage
DokuWikiRSS-Feed