Suffixarray

Der einfachste Weg besteht darin, einen effizienten vergleichsbasierten Sortieralgorithmus zu verwenden, der höchstens ${\displaystyle O(n\log n)}$ Vergleiche benötigt. Da der Vergleich zweier Suffixe ${\displaystyle O(n)}$ Zeit benötigt, beträgt die komplette Laufzeit dieses Verfahrens ${\displaystyle O(n^{2}\log n)}$. Weiter entwickelte Algorithmen verbessern dies auf ${\displaystyle O(n\log n)}$, indem sie die Ergebnisse von Teilvergleichen ausnutzen und somit redundante Vergleiche vermeiden.

Dazu wird zunächst nur der erste Buchstabe jedes Suffixes betrachtet und daraus ein vorläufiger Suffixarray aufgebaut, der Suffixe mit gleichem Anfangsbuchstaben noch nicht untereinander sortiert hat. Suffixe mit unterschiedlichen Anfangsbuchstaben sind aber bereits in der richtigen Reihenfolge enthalten. In einem zweiten Schritt wird jede Gruppe von Suffixen mit gleichem Anfangsbuchstaben so sortiert, dass sie bezüglich der ersten beiden Anfangsbuchstaben korrekt sortiert sind. Der dritte Schritt sortiert alle Suffixgruppen mit zwei gleichen Anfangsbuchstaben so, dass sie bezüglich der ersten vier richtig sortiert sind, der vierte Schritt so, dass sie bezüglich der ersten acht richtig sortiert sind, und so weiter. Nach ${\displaystyle \log _{2}n}$ Schritten ist jedes Suffix vollständig richtig sortiert und der Suffixarray fertig aufgebaut. Jeder Teilschritt ist in Zeit ${\displaystyle O(n)}$ möglich, so dass sich die Gesamtlaufzeit ${\displaystyle O(n\log n)}$ ergibt.[1]

Zu dieser Klasse gehören der klassische Suffixarray-Algorithmus von Manber und Myers[2] sowie der in der Praxis deutlich effizientere Algorithmus von Larsson und Sadakane.[3]

Diese Algorithmenklasse wird erst seit 2003 erforscht. Der Zeichen des Strings ${\displaystyle S}$ werden dazu in zwei Zeichenketten x und y aufgeteilt. Anschließend wird der Algorithmus rekursiv auf x aufgerufen. Mit dem dadurch berechneten Suffixarray von x kann der Suffixarray von y effizient berechnet („induziert“) werden. Da die Aufteilung in x und y bekannt ist, kann daraus der Suffixarray von ${\displaystyle S}$ abgelesen werden.

Durch geschickte Wahl von x und y haben die meisten dieser Algorithmen eine Laufzeit von ${\displaystyle O(n)}$. Da Rekursion in der Praxis teuer ist, sind sie jedoch nicht immer zu bevorzugen.[1]

Auch hier wird mit einem bereits berechneten Suffixarray einer Zeichenkette x der Suffixarray einer Zeichenkette y effizient berechnet (induziert). Anstelle einer rekursiven Arbeitsweise kann beispielsweise der String ${\displaystyle S}$ mehrfach in verschiedenen Richtungen durchlaufen werden. Dabei werden die Zeichen in x bzw. y klassifiziert, teilweise sortiert und in einem späteren Schritt auf Basis anderer Teilergebnisse weitersortiert. Die Algorithmen dieser Klasse sind sehr divers. Fast alle haben jedoch gemeinsam, dass sie trotz einer häufig schlechten Worst Case-Laufzeit von ${\displaystyle O(n^{2}\log n)}$ in der Praxis meist schneller als rekursive Algorithmen sind. Auch benötigen sie im Allgemeinen deutlich weniger Speicherplatz als andere Algorithmen.[1]

Der derzeit schnellste Algorithmus dieser Klasse ist der Suffix-Array-Induced-Sorting-Algorithmus (kurz SAIS) von Nong, Zhang und Chan[4]. Er benötigt lediglich eine Laufzeit in ${\displaystyle O(n)}$. Der SAIS-Algorithmus erweist sich auch in der Praxis als sehr schnell, wenn bei der Implementierung verschiedene Effekte wie z. B. Cache-Misses berücksichtigt werden.[5]

Eine exakte Suchanfrage besteht aus einem Suchmuster ${\displaystyle P}$, das in einem Text ${\displaystyle T}$ gesucht werden soll. Eine Textstelle zählt nur dann als exaktes Vorkommen von ${\displaystyle P}$, wenn jedes Zeichen der Textstelle mit ${\displaystyle P}$ übereinstimmt. Damit unterscheiden sich diese Anfragen von den nicht exakten Anfragen, bei denen eine festgelegte Anzahl an abweichenden Zeichen erlaubt ist. Es wird bei den exakten Suchanfragen zwischen Entscheidungsanfragen ("Kommt ${\displaystyle P}$ in ${\displaystyle T}$ vor?"), Anzahlanfragen ("Wie oft kommt ${\displaystyle P}$ in ${\displaystyle T}$ vor?") und Aufzählungsanfragen ("An welchen Stellen kommt ${\displaystyle P}$ in ${\displaystyle T}$ vor?") unterschieden, wobei Entscheidungsanfragen ggf. mithilfe von Anzahlanfragen und Anzahlanfragen mit Aufzählungsanfragen beantwortet werden können[6].

Um die Anzahl der exakten Vorkommen von ${\displaystyle P}$ zu bestimmen, müssen im Suffixarray zu ${\displaystyle T}$ alle Suffixe gesucht werden, die mit ${\displaystyle P}$ beginnen. Da das Suffixarray sortiert ist, liegen diese Suffixe alle direkt hintereinander und bilden einen Block. Daher reicht es aus, den lexikographisch kleinsten und den lexikographisch größten Suffix zu bestimmen, die mit ${\displaystyle P}$ beginnen. Mithilfe der binären Suche können diese jeweils in ${\displaystyle O(m\cdot \log n)}$ gefunden werden, wobei ${\displaystyle m}$ im Folgenden für die Länge von ${\displaystyle P}$ und ${\displaystyle n}$ für die Länge von ${\displaystyle T}$ steht. Die Anzahl der Vorkommen von ${\displaystyle P}$ ist dann gleich der Anzahl der Suffixe, die in diesem Block liegen. Damit kann die Anzahl der Vorkommen insgesamt in ${\displaystyle O(m\cdot \log n)}$ bestimmt werden. Wenn zusätzlich die Ausgabe der Anfangspositionen aller exakten Vorkommen gefordert ist, müssen stattdessen die Werte des Suffixarrays in dem Block zurückgegeben werden. Die Laufzeit hierfür beträgt ${\displaystyle O(m\cdot \log n+\vert O_{P}\vert )}$, wobei ${\displaystyle \vert O_{P}\vert }$ für die Anzahl der Vorkommen von ${\displaystyle P}$ in ${\displaystyle T}$ steht[7].

Verfeinerte Verfahren können unter Zuhilfenahme von weiteren Datenstrukturen bessere Laufzeiten erzielen. Wenn das sogenannte LCP-Array (englisch longest common prefix) zu ${\displaystyle T}$ bestimmt und eine geeignete RMQ-Datenstruktur (englisch range minimum query) zu dem LCP-Array konstruiert wurde, können Entscheidungs- sowie Anzahlanfragen in ${\displaystyle O(m)}$ und Aufzählungsanfragen in ${\displaystyle O(m+\vert O_{P}\vert )}$ beantwortet werden[8].

Das Suffixarray eines Texts ${\displaystyle T}$ wird häufig als Zwischenschritt benutzt, um den zugehörigen Suffixbaum in Linearzeit zu konstruieren[9]. Der Suffixbaum kann anschließend ebenfalls als Index genutzt werden, um Suchanfragen zu beantworten.

Verschiedene Kompressionsverfahren können unter Einsatz des Suffixarrays effizient umgesetzt werden. So kann die Faktorisierung der LZ77-Komprimierung in Linearzeit implementiert werden[10]. Darüber hinaus kann man aus einem bestehenden Suffixarray mit sehr geringem Aufwand die Burrows-Wheeler-Transformation des Textes errechnen. Dazu wird nacheinander für jedes Suffix des Suffixarrays das Zeichen bestimmt, das im Text genau eine Position vor dem Suffix steht, und in einem Array abgelegt[11]. Das resultierende Array ist dann identisch zur Burrows-Wheeler-Transformation des Textes und kann beispielsweise für das bzip2-Kompressionsverfahren verwendet werden.