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.
Masterarbeit, bei Vorkenntnissen auch Bachelorarbeit.
[1]: Fischer, Gagie, Gawrychowski & Kociumaka: Approximating LZ77 via Small-Space Multiple-Pattern Matching, arXiv abs/1504.06647 (2015)
Bei Interesse wenden Sie sich bitte an Patrick Dinklage und Johannes Fischer.