Quantitative Aspekte Grammatik-basierter Kompression

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

Grammatik-basierte Kompression wurde in den letzten zwei Jahrzehnten sowohl aus theoretischer als auch praktischer Sicht untersucht. Abgesehen von der Klasse der Lempel-ZivKompressoren sind jedoch nur wenige quantitative Aussagen über die Kompressionsgüte von Grammatik-basierten Kompressoren bekannt. Ein gutes Beispiel hierfür sind die sogenannten globalen Kompressoren (wie z.B. der RePair Algorithmus), welche in der Praxis hervorragend abschneiden, die jedoch andererseits eine große Lücke zwischen den bekannten oberen und unteren Schranken für die Approximationsrate aufweisen. Für Grammatik-basierte Baumkompressoren ist die Forschungslücke hinsichtlich quantitativer Aussagen noch größer. Hauptziel des Projekts ist die Entwicklung neuer Techniken, mittels derer sich genaue quantitative Aussagen über die Kompressionsgüte von Grammatik-basierten Wort- und Baumkompressoren ableiten lassen. In der zweiten Projektphase soll der Fokus auf der Approximationsrate der globalen Kompressoren sowie der Analyse grammatik-basierter Baumkompressoren liegen. Insbesondere soll die Analyse der durchschnittlichen Größe minimaler DAGs (directed acyclic graphs) von Bäumen für diverse Wahrscheinlichkeitsverteilungen vorangetrieben werden. Eine Hauptanwendung für die Untersuchungen ist die universelle Baumkompression.

• DFG-Verfahren: Sachbeihilfen