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

• Erstellungsjahr: 2015

Zusammenfassung der Projektergebnisse

Algorithmen, die direkt auf komprimierten Datenstrukturen arbeiten und dabei ohne eine vollständige initiale Dekompression auskommen, führen in vielen Fällen zu einer Effizienzsteigerung gegenüber Verfahren, welche nach der Strategie "decompress-and-manipulate" arbeiten. In dem Projekt wurden einerseits effiziente Algorithmen für grundlegende Problemstellungen auf komprimierten Daten entwickelt, während für andere Problemstellungen nachgewiesen wurde, dass sie komplexitätstheoretisch schwierig sind. Als Datenstruktur zur Repräsentation komprimierter Objekte wurden Grammatiken herangezogen (Grammatik-basierte Kompression). Unser Hauptaugenmerk war dabei auf Wörter und Bäume gerichtet; in der Endphase des Projekts wurden auch komprimierte Matrizen untersucht. Mittels kontextfreier Wort- bzw. Baumgrammatiken, welche nur ein Wort bzw. einen Baum erzeugen (sogenannte straight-line Programme) lassen sich zum einen leistungsfähige Kompressoren realisieren, zum anderen existieren effiziente Algorithmen, welche direkt auf den Grammatiken arbeiten. Die entwickelten Algorithmen wurden angewendet auf (i) diverse Entscheidungsprobleme in der Gruppentheorie und (ii) die Verarbeitung von XML-Dokumenten. Für die Kompression von Bäumen wurde mit dem TreeRePair-Kompressor ein Verfahren entwickelt und implementiert, welches in der Praxis hervorragende Kompressionsraten erzielt.

Projektbezogene Publikationen (Auswahl)

• Compressed word problems in HNN-extensions and amalgamated products. Theory of Computing Systems, 49(2):283-305, 2011
  N. Haubold and M. Lohrey
  
• Leaf languages and string compression. Information and Computation, 209(6):951-965, 2011
  M. Lohrey
  
• Parameter reduction and automata evaluation for grammar-compressed trees. J. Comput. Syst. Sci., 78{5):1651-1669, 2012
  M. Lohrey, S. Maneth, and M. Schmidt-Schauß
  
• Compressed decision problems for graph products of groups and applications to (outer) automorphism groups. International Journal of Algebra and Computation, 22(8), 2013
  N. Haubold, M. Lohrey, and C. Mathissen
  
• XML tree structure compression using RePair. Inf. Syst., 38(8):1150-1167, 2013
  M. Lohrey, S. Maneth, and R. Mennicke
  
• XML compression via DAGs. Theory of Computing Systems, 2014
  M. Bousquet-Mélou, M. Lohrey, S. Maneth, and E. Noeth