Algorithmen für komprimierte Daten (ALKODA)

• Antragsteller: Professor Dr. Markus Lohrey
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2008 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 76592132

Algorithmen, welche direkt auf komprimierten Daten arbeiten, ermöglichen die Manipulation komprimierter Datenstrukturen, ohne eine vorherige Dekompression notwendig zu machen. Hierdurch kann eine Effizienzsteigerung gegenüber Verfahren, welche nach der Strategie „decompress-and-manipulate arbeiten, erreicht werden. Hauptanliegen des ALKODA-Projekts ist die Entwicklung effizienter Algorithmen für grundlegende Problemstellungen auf komprimierten Daten, bzw. der Nachweis, dass solche Algorithmen unter allgemeinen komplexitätstheoretischen Annahmen nicht existieren. Die untersuchten Problemstellungen sollen Anwendungen in vielen Bereichen ermöglichen. Dies soll zu einem grundlegenden Verständnis für die Grenzen effizienter Algorithmen auf komprimierten Daten führen. Als Datenstruktur zur Repräsentation komprimierter Objekte werden grammatikalische Formalismen herangezogen (Grammatik-basierte Kompression). Ergebnisse für diese sehr allgemeine Datenstruktur lassen sich auf eine Reihe von Praxis-relevanten komprimierten Repräsentationen, wie die der Lempel-Ziv Familie, übertragen. Der bisher überwiegend für Strings angewendete Ansatz der Grammatik-basierten Kompression soll auch für Bäume weiterentwickelt werden.

• DFG-Verfahren: Sachbeihilfen