Generation of Symbol Tables for String Compression with Frequent-Substring Trees (FST)
Internally funded project
Acronym: FST
Start date : 19.09.2022
Project details
Scientific 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.
