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-11-22T07:47:34
ER  -