Suffixbaum
aus Wikipedia, der freien Enzyklopädie
Ein Suffixbaum ist eine vielseitige Datenstruktur, die effiziente Lösungen zahlreicher Probleme im Bereich der Stringverarbeitung ermöglicht.
Inhaltsverzeichnis |
[Bearbeiten] Definition
Ein Suffixbaum T für einen String S mit m Symbolen ist ein gerichteter Baum mit m Blättern. Jede Kante ist mit einem Teilstring von S beschriftet. Jeder innere Knoten von T hat mindestens zwei Kinder, deren Kantenbeschriftungen nie mit dem gleichen Symbol beginnen. Für jedes Blatt i in T ergeben die Beschriftungen der Kanten auf dem Pfad von der Wurzel zu i aneinander gehängt das Suffix von S, das an Index i beginnt. Somit enthält T alle Suffixe von S, wobei mehrfach auftretende Teilstrings nur einmal in T enthalten sind (siehe Abbildung).
[Bearbeiten] Anwendungen
Dadurch ermöglicht ein Suffixbaum die effiziente Lösung zahlreicher Probleme im Bereich der Stringverarbeitung. Die Konstruktion des Baumes ist in linear wachsender Laufzeit und linear wachsendem Speicherplatzbedarf möglich. Ein Suffixbaum ermöglicht etwa im Bereich des exakten Stringvergleichs in einem Text der Länge m nach Vorverarbeitung in O(m) das Suchen von k Mustern der Länge n mit einer Laufzeitkomplexität von nur O(k+n). Auch im Bereich des weichen Stringvergleichs ermöglicht ein Suffixbaum effiziente Verfahren, etwa beim Matching mit wildcards oder k-mismatch (siehe Gusfield 1999:199ff.) oder in Form einer Beschleunigung der Ermittlung der Levenshtein-Distanz über hybrides dynamic programming (siehe Gusfield 1999:279ff.).
Für eine ausführliche Darstellung und mehr als 20 weitere Anwendungen von Suffixbäumen siehe Gusfield (1999:89ff.).
[Bearbeiten] Geschichte
- Morrison (1968): Patricia-Trie.
- Weiner (1973): Erster Algorithmus zur Konstruktion von Suffixbäumen mit linear wachsender Laufzeit.
- McCreight (1976): Weiterentwicklung mit höherer Speicherplatzeffizienz.
- Ukkonen (1995): Konzeptionell neuer, einfacherer Algorithmus mit Laufzeit- und Speicherplatzkomplexität O(n), ermöglicht zudem eine on-line Konstruktion des Baumes.
- Giegerich & Kurtz (1995): Beschleunigter Algorithmus mittels funktionaler Sprache und lazy evaluation: Aufbau während des Suchens, nur relevante Teile des Baums werden erstellt, wenn noch nicht vorhanden.
[Bearbeiten] Literatur
- Gusfield, Dan (1999 [1997]) Algorithms on Strings, Sequences and Trees.
- Böckenhauer, Hans-Joachim & Dirk Bongartz (2003) Algorithmische Grundlagen der Bioinformatik.
