Erzeugung von Symboltabellen für die Komprimierung von Zeichenketten mit Hilfe von Frequent-Substring Trees
Erzeugung von Symboltabellen für die Komprimierung von Zeichenketten mit Hilfe von Frequent-Substring Trees
(Projekt aus Eigenmitteln)
Titel des Gesamtprojektes:
Projektleitung:
Projektbeteiligte:
Projektstart: 19. September 2022
Projektende:
Akronym: FST
Mittelgeber:
URL:
Abstract
Mit dem andauernden Anstieg globaler Datenvolumina gewinnt die Datenbankkompression immer weiter an Relevanz. Während die Kompression numerischer Datentypen umfassend erforscht wurde, erfährt die Kompression von Zeichenketten erst neuerdings wieder verstärkte wissenschaftliche Beachtung.
Ein vielversprechender Ansatz zur Stringkompression ist die Kompression mittels Symboltabellen, bei der wiederkehrende Substrings innerhalb einer Datenbank durch kurze Codes substituiert werden. Eine korrespondierende Tabelle ermöglicht dabei eine reibungslose Rekonstruktion der Originaldaten. Dieser Ansatz besticht durch kurze Kompressions- und Dekompressionszeiten, wobei die Kompressionsrate stark von der Qualität der Symboltabelle abhängig ist.
Das Forschungsprojekt FST fokussiert sich auf die Erzeugung optimierter Symboltabellen zur Maximierung der Kompressionsrate. Dafür werden die namensgebenden Frequent-Substring Trees konstruiert, eine Trie-artige Datenstruktur, die alle potenziellen Tabelleneinträge abbildet und die mit Hilfe von Metadaten die Identifizierung optimaler Einträge ermöglicht.
Das primäre Ziel des Forschungsprojektes ist die Steigerung der Kompressionsrate von Stringkompressionsverfahren, ohne die Kompressions- und Dekompressionszeiten signifikant zu beeinträchtigen.