Suffixarrays – Eine Datenstruktur um lange Texte zu indizieren
Posted in Algorithmen, Datenstrukturen on January 10th, 2009 by Benjamin Milde – Be the first to commentEinleitung
Das Suffixarray ist eine einfach Datenstruktur, die zusätzliche Informationen zum Auffinden aller Vorkommenisse eines Teilstrings eines Textes bereithält. Dieser Artikel befasst sich intensiv mit der Theorie aber auch mit der Umsetzung und den dazu passenden Algorithmen in der Praxis.
Um einen Text zu durchsuchen und eine bestimmte Zeichenkette zu finden, muss ohne Vorarbeit min. jedes Zeichen des Textes einmal verglichen werden. Dieser Vorgang ist bestenfalls in O(n).
Bei naiver Implementierung, liegt die Suche mit einem Suffix-Array in O(mlog(n)). m ist dabei die länge des Suchwortes. Dieser Geschwindigkeitsvorteil hat seinen Preis, je nach Größe des Textes wird ca. das 4-Fache der Textlänge an zusätzlichem Speicherplatz benötigt. Auf Kosten weiteren Speicherplatzes kann die Suche noch weiter verbessert werden.