Suffixarray

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Informatik ist ein Suffixarray ein Array, das die Suffixe einer Zeichenkette in lexikographischer Reihenfolge angibt.

Beispiel[Bearbeiten]

Betrachte den String S=abracadabra der Länge 11. Da auch der leere String ein gültiges Suffix ist, fügen wir an das Ende von S den Endmarker $ hinzu, um den leeren String bzw. das Ende von S ausdrücken zu können. Der String mit den zugehörigen Positionen seiner Zeichen lautet also:

i 1 2 3 4 5 6 7 8 9 10 11 12
S[i] a b r a c a d a b r a $

Dieser String hat zwölf Suffixe, die auch durch ihre Startposition i in S beschrieben werden können:

Suffix i
abracadabra$ 1
bracadabra$ 2
racadabra$ 3
acadabra$ 4
cadabra$ 5
adabra$ 6
dabra$ 7
abra$ 8
bra$ 9
ra$ 10
a$ 11
$ 12

Der leere String ist lexikografisch kleiner als jedes Suffix von S. Daher ist der Endmarker $ per Konvention ebenfalls lexikografisch kleiner als jedes andere Zeichen im String. Somit können alle Suffixe lexikografisch sortiert werden:

Suffix i
$ 12
a$ 11
abra$ 8
abracadabra$ 1
acadabra$ 4
adabra$ 6
bra$ 9
bracadabra$ 2
cadabra$ 5
dabra$ 7
ra$ 10
racadabra$ 3

Als Array dargestellt ergibt sich {$, a$, abra$, …}.

Wenn der Originalstring bekannt ist, kann jedes Suffix platzsparend durch den Index seines ersten Zeichens spezifiziert werden. Das Suffixarray ist ein Array dieser Indizes in lexikographischer Reihenfolge. Für den String abracadabra$ lautet das Suffixarray somit A={12,11,8,1,4,6,9,2,5,7,10,3}: Das Suffix „a“ bzw. „a$“ beginnt am elften Zeichen, „abra“ beim achten und so weiter.


Der Endmarker $ ist nützlich, wenn mehrere Strings kombiniert werden. Beispielsweise ist in S'=abracadabra$mississippi$ sofort klar, dass der Text aus den beiden Strings abracadabra und mississippi besteht. Wenn nur ein String betrachtet werd, kann dieses Suffix übergangen werden: Da der leere String lexikographisch immer vor allen anderen sortiert wird, geht in diesem Fall keine Information verloren.

Algorithmen[Bearbeiten]

Es gibt mehrere Möglichkeiten, um aus einem gegebenen Text der Länge n ein Suffix Array zu konstruieren.

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

Der Suffix-Array-Induced-Sorting-Algorithmus (kurz SAIS) von Nong, Zhang und Chan[1] benötigt lediglich eine Laufzeit in O(n). Bei diesem Verfahren werden aus der Sortierung einiger Suffixe mittels sogenannter induzierter Sortierung die anderen Suffixe sortiert. 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.[2]

Anwendungen[Bearbeiten]

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(m \log n) 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 + \log n) erreicht werden.

Suffixsortierende 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. Der im Beispiel verwendete Endmarker $ erfüllt genau diese Eigenschaften.

Geschichte[Bearbeiten]

Suffixarrays wurden ursprünglich 1990 von Gene Myers und Udi Manber entwickelt, um den Speicherverbrauch im Vergleich zu Suffixbäumen zu reduzieren. Ungefähr eine Dekade später begann dann die Entwicklung von komprimierten Suffixarrays und BWT-basierten komprimierten Volltextindizes.

Literatur[Bearbeiten]

  • Udi Manber and Gene Myers "Suffix arrays: a new method for on-line string searches". SIAM Journal on Computing, Volume 22, Issue 5 (October 1993), S. 935−948.
  • Pang Ko and Srinivas Aluru "Space efficient linear time construction of suffix arrays." In Combinatorial Pattern Matching (CPM 03). LNCS 2676, Springer, 2003, S. 203−210.
  • Juha Kärkkäinen and Peter Sanders "Simple linear work suffix array construction (PDF; 193 kB)". In Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP '03). LNCS 2719, Springer, 2003, S. 943−955.
  • Klaus-Bernd Schürmann and Jens Stoye "An incomplex algorithm for fast suffix array construction (PDF; 204 kB)". In Proceedings of ALENEX, 2005.

Einzelnachweise[Bearbeiten]

  1. Nong Ge, Sen Zhang, and Wai Hong Chan "Two Efficient Algorithms for Linear Time Suffix Array Construction". In IEEE Transactions on Computers 60, no. 10 (October 2011), S. 1471–1484.
  2. Nataliya Timoshevskaya and Wu-chun Feng "SAIS-OPT: On the characterization and optimization of the SA-IS algorithm for suffix array construction". In 2014 IEEE 4th International Conference on Computational Advances in Bio and Medical Sciences (ICCABS), 2014.

Weblinks[Bearbeiten]