Algorithmen für komprimierte Daten (ALKODA)
Final Report Abstract
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.
Publications
- 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ß
(See online at https://doi.org/10.1016/j.jcss.2012.03.003) - 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
(See online at https://doi.org/10.1016/j.is.2013.06.006) - XML compression via DAGs. Theory of Computing Systems, 2014
M. Bousquet-Mélou, M. Lohrey, S. Maneth, and E. Noeth
(See online at https://doi.org/10.1007/s00224-014-9544-x)
