Suffixbaum (Informatik)

Ein wichtiger Bereich der Informatik ist die Verarbeitung von Zeichenketten (z. B. Buchstaben oder Zahlen), welche auf Englisch als Strings bezeichnet werden. Zur Speicherung von Strings können als Datenstrukturen sogenannte Suffixbäume genutzt werden. Suffixbäume erlauben unter anderem die schnelle Suche von Wörtern in einem langen Text. In der Bioinformatik kommen sie insbesondere im Umgang mit biologischen Sequenzen wie DNA-, RNA- oder Proteinsequenzen zum Einsatz.

Als gerichteten Baum bezeichnet man in der Informatik einen speziellen Graphen, der aus Knoten und Kanten besteht, die in eine bestimmte Richtung zeigen, sodass keine Zyklen entstehen (siehe Abbildung). Der oberste Knoten ist die Wurzel des Baumes. Jeder Knoten, von dem weitere Kindknoten ausgehen, ist ein innerer Knoten, während Knoten ohne ausgehende Kindknoten als Blätter bezeichnet werden.

Ein Suffixbaum für einen String der Länge n ist ein gerichteter Baum mit den folgenden Eigenschaften:

• Der Baum hat genau n Blätter, die von 1 bis n nummeriert werden.
• Jeder innere Knoten mit Ausnahme der Wurzel hat mindestens zwei Kindknoten.
• Jede Kante zwischen zwei Knoten ist mit einem nicht-leeren Substring des Strings beschriftet.
• Alle Kanten, welche denselben Knoten verlassen, müssen Beschriftungen haben, die mit unterschiedlichen Zeichen beginnen.
• Der String, den man enthält, wenn man alle Kantenbeschriftungen auf dem Weg von der Wurzel bis zum i-ten Blatt zusammensetzt, ist das i-te Suffix des Strings.

Für gewöhnlich wird ein $-Zeichen an das Ende des Strings und somit auch an das Ende jedes Suffix angefügt, welches anzeigt, wann ein Suffix zu Ende ist.

Der unten abgebildete Baum ist ein unvollständig ausgefüllter Suffixbaum für den String ANANAS$. Ordnen Sie die Substrings ihren jeweiligen Kanten zu. Ziehen Sie dafür die Substrings per Drag & Drop in den Suffixbaum.