Implementierung und Evaluation von grammatikbasierter Kompression

Abstract

Diese Arbeit befasst sich mit der Implementierung und Evaluation grammatikbasierter Kompressionsverfahren zur verlustfreien Datenkompression. Ziel dieser Verfahren ist es, eine Eingabesequenz durch eine kompakte kontextfreie Grammatik darzustellen, die genau ein Wort erzeugt, ein sogenanntes Straight-Line Program (SLP). Durch die Identifikation wiederkehrender Teilstrings können Redundanzen innerhalb der Daten reduziert und Speicherbedarf sowie Übertragungsaufwand verringert werden.