Entwurf und Implementierung eines Verfahrens zur Stringsuche in grammatikkomprimierten Daten

Abstract

Diese Arbeit behandelt die Suche nach Mustern in grammatikkomprimierten Texten. Als Eingabe werden eine Grammatik, die genau ein Wort erzeugt, sowie ein unkomprimiertes Muster betrachtet. Ziel ist es, Mustervorkommen zu erkennen und zu zählen, ohne den Text vollständig zu dekomprimieren. Hierzu wird ein Suchalgorithmus entwickelt, der auf der Struktur der Grammatik arbeitet und Mustervorkommen an Regelgrenzen identifiziert. Grundlage des Verfahrens sind sogenannte R- und L-Mengen, welche passende Präfix- und Suffixpositionen des Musters erfassen und deren Kombination zur Erkennung vollständiger Matches genutzt wird.