Das Finden mehrerer Vorkommen einer Zeichenkette ist eine wichtige Aufgabe bei vielen Problemen mit Strings und begegnet uns in vielen Programmen im Alltag. Sei es bei der Suche eines Wortes in einem Dokument oder bei der Nutzung von Programmen zur Komprimierung von Texten. Eine LCE-Anfrage berechnet das längste gemeinsame Präfix zu zwei Positionen eines Strings. Anstatt die Berechnung direkt auf dem String auszuführen, wird der String mit dem hierarchical-stable-parsing-Verfahren in Gruppen zerlegt. Diese dienen zum Aufbau des HSP-Baums. Die Evaluation von LCE-Anfragen mit Hilfe des HSP-Baums ist Thema dieser Arbeit. Dabei soll eine geeignete Datenstruktur zur Repräsentation des Baums und ein Algorithmus zur Evaluation implementiert werden.

Eingebettete Systeme, wie Smartphones oder Navigationsgeräte, beschränken die Größe des verfügbaren Speichers. Ein optionales Ziel ist eine LCE-Anfrage zum modifizierten HSP-Baum, welcher in der Höhe reduziert ist und weniger Speicher benötigt.

Deterministic Sparse Suffix Sorting on Rewritable Texts

Masterarbeit.

Bei Interesse wenden Sie sich bitte an Dominik Köppl.