- Suffix-Array
-
In der Informatik ist ein Suffixarray ein Array, das die Suffixe eines Strings in lexikographischer Reihenfolge angibt.
Inhaltsverzeichnis
Details
Betrachte den String "abracadabra" der Länge 11. Er hat elf Suffixe: "abracadabra", "bracadabra", "racadabra", und so weiter bis zu "a". In lexikographischer Reihenfolge sortiert sind es folgende Suffixe:
a abra abracadabra acadabra adabra bra bracadabra cadabra dabra ra racadabra
Wenn der Originalstring verfügbar ist, kann jedes Suffix durch den Index (Hinweis: Die Indizierung kann mit der Null oder mit der Eins beginnen, hier beginnt sie mit der Eins.) seines ersten Zeichens spezifiziert werden. Das Suffixarray ist ein Array dieser Indizes in lexikographischer Reihenfolge. Für den String "abracadabra" lautet das Suffixarray {11,8,1,4,6,9,2,5,7,10,3}, weil "a" beim elften Zeichen beginnt, "abra" beim achten Buchstaben und so weiter.
Genau genommen hat der String "abracadabra" ein zwölftes Suffix: Den leeren String (mit Index 12). Aber da der leere String lexikographisch immer vor allen anderen sortiert wird, geht bei Vernachlässigung dieses Suffixes keine Information verloren.
Algorithmen
Der einfachste Weg, ein Suffixarray zu konstruieren, ist einen effizienten vergleichsbasierten Sortieralgorithmus zu verwenden. Dieser benötigt O(nlogn) Suffixvergleiche, aber ein Suffixvergleich benötigt O(n) Zeit, so dass die komplette Laufzeit dieses Verfahrens O(n2logn) ist. Weiter entwickelte Algorithmen verbessern das auf O(nlogn) durch Ausnutzung der Ergebnisse von Teilvergleichen, um redundante Vergleiche zu vermeiden. Einige Θ(n)-Algorithmen sind bekannt, die mit einem geringem Speicherbedarf von O(n) mit kleinen Konstanten auskommen.
Anwendungen
Das Suffixarray eines Strings kann als Index genutzt werden, um schnell jeden Substring innerhalb des Strings zu lokalisieren. Jedes Vorkommen eines Substrings zu finden ist äquivalent zum Finden aller Suffixe, die mit diesem Substring beginnen. Dank der lexikographischen Ordnung werden diese Suffixe im Suffixarray zusammen gruppiert und können effizient mittels einer binären Suche gefunden werden. Wenn sie naiv implementiert ist, benötigt die binäre Suche O(mlogn) Zeit, wobei m die Länge des Substrings ist. Um wiederholte Vergleiche zu vermeiden, werden zusätzliche Datenstrukturen, die Information über das längste gemeinsame Präfix (engl. longest common prefix, kurz: LCP) von Suffixen liefern, konstruiert. Damit kann eine Suchzeit von O(m + logn) erreicht werden.
Suffix sortierende Algorithmen können benutzt werden, um die Burrows-Wheeler-Transformation (BWT) durchzuführen. Bei der BWT werden allerdings statt der Suffixe eines Strings seine zyklischen Permutationen sortiert. Dies kann man beheben, indem ein spezielles Zeichen, das nicht im String vorkommt und lexikographisch das kleinste Zeichen ist, an das Ende des Strings angehängt wird. Zyklische Permutationen zu sortieren ist dann äquivalent zum Sortieren von Suffixen.
Geschichte
Suffixarrays wurden ursprünglich von Gene Myers und Udi Manber entwickelt, um den Speicherverbrauch im Vergleich zu Suffixbäumen zu reduzieren. Damit begann auch die Entwicklung von komprimierten Suffixarrays und BWT-basierten komprimierten Volltextindizes.
Literatur
- Udi Manber and Gene Myers (1991). "Suffix arrays: a new method for on-line string searches". SIAM Journal on Computing, Volume 22, Issue 5 (October 1993), pp. 935-948.
- Pang Ko and Srinivas Aluru (2003). "Space efficient linear time construction of suffix arrays." In Combinatorial Pattern Matching (CPM 03). LNCS 2676, Springer, 2003, pp 203-210.
- Juha Kärkkäinen and Peter Sanders (2003). "Simple linear work suffix array construction". In Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP '03). LNCS 2719, Springer, 2003, pp. 943-955.
- Klaus-Bernd Schürmann and Jens Stoye (2005). "An incomplex algorithm for fast suffix array construction". In Proceedings of ALENEX, 2005.
Weblinks
Wikimedia Foundation.
