TY - THES A3 - Lohrey, Markus AB - Das Ziel grammatik-basierter Datenkompression ist es ein Wort (oder einen Text) durch eine kontextfreie Grammatik darzustellen, die ausschließlich dieses Wort erzeugt. Eine kontextfreie Grammatik mit dieser Eigenschaft wird als Straight-line Program (SLP) bezeichnet. Grammatik-basierte Kompression ist ein nützliches Werkzeug um Daten zu komprimieren und verschiedene Anfragen effizient mit Hilfe der komprimierten Repräsentation zu beantworten ohne diese vorher zu dekomprimieren. Im ersten Teil dieser Arbeit werden die grammatikbasierten Kompressoren LZ78, BiSection, RePair, Greedy und LongestMatch untersucht, die zu den bekanntesten Algorithmen in diesem Bereich zählen. In der bedeutenden Veröffentlichung "The smallest grammar problem" von Charikar et al. wurden untere und obere Schranken für die Approximationsgüte verschiedenster grammatik-basierter Kompressoren gezeigt, darunter die oben genannten. Leider besteht für jeden Algorithmus eine Lücke zwischen der unteren und oberen Schranke. In dieser Arbeit werden diese Lücken für die Kompressoren LZ78 und BiSection geschlossen. Des Weiteren werd für RePair und für Greedy die unteren Schranken verbessert. Ein weiteres Ergebnis dieser Arbeit verbessert ein Resultat von Arpe und Reischuk, welches grammatik-basierte Kompression über beliebigen Alphabeten und binären Alphabeten verbindet. Im zweiten Teil dieser Arbeit betrachten wir grammatik-basierte Kompression für Bäume. Das Prinzip ist ähnlich, da in diesem Kontext ein Baum durch eine lineare, kontextfreie Baumgrammatik erzeugt wird. Eine solche Grammatik wird Tree Straight-line Program (TSLP) genannt. Als Hauptresultat in diesem Zusammenhang werden zwei Algorithmen präsentiert, die für einen Baum mit n Knoten und konstant vielen verschiedenen Beschriftungen der Knoten ein TSLP der Gr öße O(n/log n) generieren. Zusätzlich wird erreicht, dass das TSLP logarithmische Tiefe hat. Diese Eigenschaften können in logarithmischen Platz oder alternativ in linearer Zeit erreicht werden. Entsprechende Resultate für grammatik-basierte Kompression von Wörtern sind wohl bekannt. Es werden zusätzlich zwei Anwendungen präsentiert: Zuerst werden TSLPs für die Umwandlung von arithmetischen Formeln zu arithmetischen Schaltkreisen der Größe O((n*log m)/log n) und Tiefe O(log n) genutzt, wobei n die Größe der Formel und m die Anzahl verschiedener Variablen in der Formel ist. Als zweite Anwendung wird eine binäre Kodierung von unbeschrifteten Binärbäumen auf der Basis von grammatik-basierter Baumkompression präsentiert. Es wird gezeigt, dass diese Kodierung unter gewissen Voraussetzungen asymptotisch optimal ist. AU - Hucke, Danny DA - 2019 DO - 10.25819/ubsi/610 KW - Datenkompression KW - Kompression KW - Bäume KW - Grammar-based compression KW - strings LA - eng PY - 2019 TI - Grammar-based compression for strings and trees TT - Grammatik-basierte Kompression von Wörtern und Bäumen UR - https://nbn-resolving.org/urn:nbn:de:hbz:467-15361 Y2 - 2024-12-02T16:21:58 ER -