Suffix-Array

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.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Suffix array — In computer science, a suffix array is an array giving the suffixes of a string in lexicographical order.DetailsConsider the string abracadabra , of length 11. It has eleven suffixes: abracadabra , bracadabra , racadabra , and so on down to a .… …   Wikipedia

  • Compressed suffix array — The Compressed Suffix Array[1][2] is a compressed data structure for pattern matching. Given a text T of n characters from an alphabet Σ, the compressed suffix array support searching for arbitrary patterns in T. For an input pattern P of m… …   Wikipedia

  • Suffix tree — In computer science, a suffix tree (also called suffix trie, PAT tree or, in an earlier form, position tree) is a data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many… …   Wikipedia

  • Generalised suffix tree — A generalised suffix tree is a suffix tree for a set of strings. Given the set of strings D=S 1,S 2,dots,S d of total length n, it is a Patricia trie containing all n suffixes of the strings. It is mostly used in bioinformaticsref|BRCR.… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • Suffixarray — In der Informatik ist ein Suffixarray ein Array, das die Suffixe eines Strings in lexikographischer Reihenfolge angibt. Inhaltsverzeichnis 1 Details 2 Algorithmen 3 Anwendungen …   Deutsch Wikipedia

  • Joshua MT Tool — is an open source tool for statistical machine translation which is parsing based. The toolkit achieves state of the art translation performance on the French English translation task. Contenido 1 History 2 Goals 3 Main functions implemented in… …   Wikipedia Español

  • Compressed data structure — The term compressed data structure arises in the computer science subfields of algorithms, data structures, and theoretical computer science. It refers to a data structure whose operations are roughly as fast as those of a conventional data… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”