Praktische und Parallele Textkompression für hochrepetitive Daten

• Antragsteller: Professor Dr. Johannes Christian Fischer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 501086801

Wir wollen praktikable Algorithmen zum Komprimieren von hochrepetitiven Daten entwickeln, die die Unzulänglichkeiten aktuell gängiger Kompressoren wie gzip oder bzip2 überwinden. Diese wurden in den 1990er Jahren etabliert und zielten auf Hardware ab, die damals Standard war; ihr Hauptnachteil besteht darin, dass sie keine Wiederholungen von Teilstrings erfassen, die weit auseinander liegen. Das erste Ziel dieses Projekts besteht darin, ein Komprimierungswerkzeug zu entwickeln und zu engineeren, das auch von solchen weit voneinander entfernten Wiederholungen profitiert, aber dennoch nur einen moderaten Speicherbedarf hat.Als zweites Ziel wollen wir die Shared-Memory-Parallelität ausnutzen, die in praktisch jeder CPU vorhanden ist, um die Komprimierung zu beschleunigen, ohne zu viel Komprimierungsverhältnis zu verlieren. Hier möchten wir einen breiteren Blick auf Kompressionsalgorithmen werfen und insbesondere Grammatikkompressoren einbeziehen, die hervorragende Eigenschaften für eine effiziente Parallelisierung haben.Im Idealfall werden beide Ideen zur besseren Nutzung moderner Ressourcen in produktionsreife Software-Repositories (wie Linux-Distributionen) integriert, sodass Endverbraucher problemlos von unseren Algorithmenentwicklungsleistungen profitieren können.

• DFG-Verfahren: Sachbeihilfen