Bitparallele Mustersuche in grammatikkomprimierten Daten
Abschlussarbeit (Bachelor)

Zusammenfassung
Diese Arbeit erweitert einen bestehenden Suchalgorithmus des Projekts Grampress, der Muster direkt in grammatikkomprimierten Daten findet. Kern der Erweiterung ist eine bitparallele Mustersuche. Sie ersetzt die bisherige Verarbeitung, die jede Position des Musters einzeln prüft. Dadurch werden viele Positionen des Musters gleichzeitig bearbeitet. Zusätzlich verarbeitet der Algorithmus Regeln mit rechten Seiten beliebiger Länge und unterstützt eine Existenzsuche, die beim ersten Treffer abbricht. Ein Vergleich beider Implementierungen auf realen Datensätzen zeigt, wie stark die Laufzeit dadurch sinkt.
Schlagworte
Bitparallel
Bitwort
Bitvektor
Suchalgorithmus
Mustersuche
kompression
Early-Exit
Bitwort
Bitvektor
Suchalgorithmus
Mustersuche
kompression
Early-Exit
Umfang
IV, 39 S.
Link zur Veröffentlichung
Sammlungen
