Suffixbaum

Suffixbaum für den Text BANANE. Jedes Substring wird mit einem besonderen Charakter beendet $. Die sechs Pfade von der Wurzel bis zu den Blättern (als Kästchen gezeigt) entsprechen den sechs Suffixen A $, Na $, Ana $, Nana $, Anana $ und Banane $. Die Zahlen in den Blättern geben die Startposition des entsprechenden Suffix an. Suffix -Links, gezogen, werden während der Bauarbeiten verwendet.

Im Informatik, a Suffixbaum (auch genannt Patbaum oder in einer früheren Form, Stellbaum) ist komprimiert Trie enthält alle Suffixe des angegebenen Textes als ihre Schlüssel und Positionen im Text als ihre Werte. Suffix -Bäume ermöglichen besonders schnelle Implementierungen vieler wichtiger String -Operationen.

Die Konstruktion eines solchen Baums für die Schnur ${\ displayStyle S}$ braucht Zeit und Raum linear in der Länge von ${\ displayStyle S}$. Nach dem Bau können mehrere Vorgänge schnell ausgeführt werden, beispielsweise die Suche nach a Substring in ${\ displayStyle S}$Ein Substring, wenn eine bestimmte Anzahl von Fehlern zulässig ist, und die Übereinstimmungen für a regulären Ausdruck Muster usw. Suffix Bäume liefern auch eine der ersten linearen Lösungen für die Das längste übliche Substringproblem. Diese Beschleunigungen sind kostenpflichtig: Das Speichern des Suffixbaums einer Saitenbaum erfordert in der Regel erheblich mehr Platz als die Speicherung der Saite selbst.

Geschichte

Das Konzept wurde zuerst von vorgestellt von Weiner (1973). Eher als das Suffix ${\ displayStyle s [i..n]}$, Weiner lagte in seinem Trie^[1] das Präfixkennung Für jede Position, dh die kürzeste Zeichenfolge beginnt bei ${\ displayStyle i}$ und nur einmal auftreten ${\ displayStyle S}$. Seine Algorithmus d nimmt einen unkomprimierten^[2] Trie für ${\ displayStyle s [k+1..n]}$ und erweitert es in einen Trie für ${\ displayStyle s [k..n]}$. Auf diese Weise beginnend vom trivialen Trie für ${\ displayStyle s [n..n]}$, ein Trie für ${\ displayStyle s [1..n]}$ kann von gebaut werden von ${\ displayStyle n-1}$ aufeinanderfolgende Anrufe zum Algorithmus d; Die Gesamtlaufzeit ist jedoch ${\ displayStyle o (n^{2})}$. Weiner Algorithmus b behält mehrere Hilfsdatenstrukturen bei, um eine über alle Laufzeit in der Größe des konstruierten Tries linear zu erreichen. Letzteres kann immer noch sein ${\ displayStyle o (n^{2})}$ Knoten, z. zum ${\ displaystyle s = a^{n} b^{n} a^{n} b^{n} \ $.}$ Weiner Algorithmus c Verwendet schließlich komprimierte Versuche, um eine lineare Gesamtspeichergröße und Laufzeit zu erreichen.^[3] Donald Knuth Anschließend charakterisierte letztere als "Algorithmus des Jahres 1973". Das Textbuch Aho, Hopcroft & Ullman (1974, Abschn. Stellbaum.

McCreight (1976) war der erste, der einen (komprimierten) Tries aller Suffixe von baute ${\ displayStyle S}$. Obwohl das Suffix beginnt bei ${\ displayStyle i}$ In der Regel länger als der Präfix -Kennung, unterscheiden sich ihre Pfaddarstellungen in einem komprimierten Trie nicht in der Größe. Andererseits konnte McCreight auf die meisten Hilfsdatenstrukturen von Weiner verzichten. Es blieben nur Suffix -Links.

Ukkonen (1995) Die Konstruktion vereinfacht weiter.^[4] Er stellte den ersten Online-Bau von Suffixbäumen zur Verfügung, das jetzt als bekannt als bekannt ist Ukkonens Algorithmusmit Laufzeit, die den damals schnellsten Algorithmen entsprach. Diese Algorithmen sind alle linear ${\ displayStyle o (n \ log n)}$ Im Algemeinen.

Farach (1997) gab den ersten Suffix -Baumkonstruktionsalgorithmus, der für alle Alphabete optimal ist. Insbesondere ist dies der erste lineare Zeitalgorithmus für Zeichenfolgen, die aus einem Alphabet von ganzen Zahlen in einem Polynombereich stammen. Farachs Algorithmus ist die Grundlage für neue Algorithmen für den Bau beider Suffixbäume und für die Konstruktion von Suffix -Bäumen geworden Suffix -ArraysZum Beispiel im externen Speicher, komprimiert, prägnant usw.

Definition

Der Suffixbaum für die Schnur ${\ displayStyle S}$ von Länge ${\ displayStyle n}$ wird als ein Baum definiert, so dass:^[5]

• Der Baum hat genau n Blätter nummeriert von ${\ displayStyle 1}$ zu ${\ displayStyle n}$.
• Außer für die Wurzel, jeder Interner Knoten Hat mindestens zwei Kinder.
• Jede Kante ist mit einem nicht leeren Substring von gekennzeichnet ${\ displayStyle S}$.
• Keine zwei Kanten, die mit einem Knoten beginnen, können String-Labels haben, die mit demselben Zeichen beginnen.
• Die Zeichenfolge, die durch Verkettung aller Stringmarken auf dem Pfad von der Wurzel zu Blatt erhalten wurde ${\ displayStyle i}$ Zauber dass Suffix ${\ displayStyle s [i..n]}$, zum ${\ displayStyle i}$ aus ${\ displayStyle 1}$ zu ${\ displayStyle n}$.

Da ein solcher Baum nicht für alle Saiten existiert, ${\ displayStyle S}$ wird mit einem terminalen Symbol gepolstert, das nicht in der Zeichenfolge zu sehen ist (normalerweise bezeichnet $). Dies stellt sicher, dass kein Suffix ein Präfix eines anderen ist und dass es geben wird ${\ displayStyle n}$ Blattknoten, eine für jeden der ${\ displayStyle n}$ Suffixe von ${\ displayStyle S}$. Da sich alle internen Nicht-Wurzelknoten verzweigen, kann es höchstens geben n- 1 solcher Knoten und n+(n- 1)+1 = 2n insgesamt Knoten (n Laub, n-1 interne Nicht-Root-Knoten, 1 Wurzel).

Suffix -Links sind ein wichtiges Merkmal für ältere lineare Konstruktionsalgorithmen, obwohl die meisten neueren Algorithmen, die auf dem Farachs-Algorithmus basieren, auf Suffix-Links verzichten. In einem vollständigen Suffixbaum haben alle internen Nicht-Wurzelknoten eine Suffix-Verbindung zu einem anderen internen Knoten. Wenn der Pfad vom Wurzel zum Knoten die Zeichenfolge buchstabiert ${\ displaystyle \ chi \ alpha}$, wo ${\ displayStyle \ chi}$ ist ein einzelner Charakter und ${\ displayStyle \ alpha}$ ist eine Zeichenfolge (möglicherweise leer), eine Suffix -Verbindung zum internen Knoten, der dargestellt wird ${\ displayStyle \ alpha}$. Siehe zum Beispiel die Suffix -Link vom Knoten für Ana zum Knoten für N / A in der obigen Abbildung. Suffix -Links werden auch in einigen Algorithmen verwendet, die auf dem Baum laufen.

A Verallgemeinerter Suffixbaum ist ein Suffixbaum für eine Reihe von Saiten anstelle einer einzigen Schnur. Es repräsentiert alle Suffixe von diesen Saiten. Jede Zeichenfolge muss durch ein anderes Beendigungssymbol beendet werden.

Funktionalität

Ein Suffixbaum für eine Schnur ${\ displayStyle S}$ von Länge ${\ displayStyle n}$ kann eingebaut werden ${\ displayStyle \ theta (n)}$ Zeit, wenn die Buchstaben aus einem Alphabet von ganzen Zahlen in einem Polynombereich stammen (insbesondere für Alphabete konstanter Größe).^[6] Für größere Alphabete wird die Laufzeit von zuerst dominiert Sortierung Die Buchstaben, die sie in eine Reihe von Größe bringen ${\ displayStyle o (n)}$; Im Allgemeinen dauert dies ${\ displayStyle o (n \ log n)}$ Zeit. Die folgenden Kosten werden unter der Annahme angegeben, dass das Alphabet konstant ist.

Angenommen, ein Suffixbaum wurde für die Schnur gebaut ${\ displayStyle S}$ von Länge ${\ displayStyle n}$oder das a Verallgemeinerter Suffixbaum wurde für die Saiten gebaut ${\ displayStyle d = \ {s_ {1}, s_ {2}, \ dots, s_ {k} \}}$ der Gesamtlänge ${\ displayStyle n = n_ {1}+n_ {2}+\ cdots+n_ {k}}$. Du kannst:

• Suche nach Saiten:
  • Überprüfen Sie, ob eine Zeichenfolge ${\ displayStyle p}$ von Länge ${\ displayStyle m}$ ist ein Substring in ${\ displayStyle o (m)}$ Zeit.^[7]
  • Finden Sie das erste Ereignis der Muster ${\ displayStyle p_ {1}, \ dots, p_ {q}}$ der Gesamtlänge ${\ displayStyle m}$ als Substrings in ${\ displayStyle o (m)}$ Zeit.
  • Finde alle ${\ displayStyle z}$ Vorkommen der Muster ${\ displayStyle p_ {1}, \ dots, p_ {q}}$ der Gesamtlänge ${\ displayStyle m}$ als Substrings in ${\ displayStyle o (m+z)}$ Zeit.^[8]
  • Suche nach einem regulären Ausdruck P mit der Zeit erwartet sublinear in ${\ displayStyle n}$.^[9]
  • Finden Sie für jedes Suffix eines Musters ${\ displayStyle p}$die Länge der längsten Übereinstimmung zwischen einem Präfix von ${\ displayStyle p [i \ dots m]}$ und ein Substring in ${\ displayStyle d}$ in ${\ displayStyle \ theta (m)}$ Zeit.^[10] Dies wird als als bezeichnet passende Statistiken zum ${\ displayStyle p}$.
• Eigenschaften der Saiten finden:
  • Finde die längste übliche Substrings der Saite ${\ displayStyle s_ {i}}$ und ${\ displayStyle s_ {j}}$ in ${\ displayStyle \ theta (n_ {i}+n_ {j})}$ Zeit.^[11]
  • Finde alle Maximale Paare, maximale Wiederholungen oder supermaximale Wiederholungen in ${\ displayStyle \ theta (n+z)}}$ Zeit.^[12]
  • Finde die Lempel -Ziv Zersetzung in ${\ displayStyle \ theta (n)}$ Zeit.^[13]
  • Finde die Längste wiederholte Substrings in ${\ displayStyle \ theta (n)}$ Zeit.
  • Finden Sie die am häufigsten vorkommenden Substrings einer minimalen Länge in ${\ displayStyle \ theta (n)}$ Zeit.
  • Finden Sie die kürzesten Saiten aus ${\ displayStyle \ sigma}$ das tritt nicht auf in ${\ displayStyle d}$, in ${\ displayStyle o (n+z)}$ Zeit, wenn es gibt ${\ displayStyle z}$ Solche Saiten.
  • Finden Sie die kürzesten Substrings, die nur einmal auftreten ${\ displayStyle \ theta (n)}$ Zeit.
  • Finden Sie für jeden ${\ displayStyle i}$, die kürzesten Substrings von ${\ displayStyle s_ {i}}$ nicht woanders auftreten ${\ displayStyle d}$ in ${\ displayStyle \ theta (n)}$ Zeit.

Der Suffixbaum kann für die konstante Zeit vorbereitet werden Niedrigster gemeinsamer Vorfahr Abrufen zwischen Knoten in ${\ displayStyle \ theta (n)}$ Zeit.^[14] Man kann dann auch:

• Finden Sie das längste gemeinsame Präfix zwischen den Suffixen ${\ displayStyle s_ {i} [p..n_ {i}]}$ und ${\ displayStyle s_ {j} [q..n_ {j}]}$ in ${\ displayStyle \ theta (1)}$.^[15]
• Suche nach einem Muster P von Länge m mit höchstens k Fehlanpassungen in ${\ displayStyle o (kN+z)}$ Zeit, wo z ist die Anzahl der Hits.^[16]
• Finde alle ${\ displayStyle z}$ maximal Palindrome in ${\ displayStyle \ theta (n)}$,^[17] oder ${\ displayStyle \ theta (gn)}$ Zeit, wenn Lücken der Länge ${\ displayStyle g}$ sind erlaubt oder ${\ displayStyle \ theta (kN)}$ wenn ${\ displayStyle K}$ Fehlanpassungen sind erlaubt.^[18]
• Finde alle ${\ displayStyle z}$ Tandem wiederholt sich in ${\ displayStyle o (n \ log n+z)}$, und k-Mismatch Tandem wiederholt sich in ${\ displayStyle o (kN \ log (n/k)+z)}$.^[19]
• Finde die längste übliche Substrings bis mindestens ${\ displayStyle K}$ strings in ${\ displayStyle d}$ zum ${\ displayStyle k = 2, \ dots, k}$ in ${\ displayStyle \ theta (n)}$ Zeit.^[20]
• Finde die längste palindromische Substring einer gegebenen Zeichenfolge (unter Verwendung des verallgemeinerten Suffixbaums der String und ihrer Rückseite) in der linearen Zeit.^[21]

Anwendungen

Suffix-Bäume können verwendet werden, um eine große Anzahl von Stringproblemen zu lösen, die bei textbearbeiteten, freien Textsuche auftreten. Computerbiologie und andere Anwendungsbereiche.^[22] Primäre Anwendungen umfassen:^[22]

• String -Suche, in O (m) Komplexität, wo m ist die Länge der Unterstring (aber mit Anfangs An) Zeit erforderlich, um den Suffixbaum für die Schnur zu bauen)
• Finden Sie das am längsten wiederholte Substring
• Das längste gemeinsame Substring finden
• Am längsten finden Palindrom in einer Saite

Suffixbäume werden oft in verwendet Bioinformatik Anwendungen, suchen nach Mustern in DNA oder Protein Sequenzen (die als lange Zeichenfolgen angesehen werden können). Die Fähigkeit, effizient mit Missverhältnissen zu suchen, kann als ihre größte Stärke angesehen werden. Suffixbäume werden auch in verwendet Datenkompression; Sie können verwendet werden, um wiederholte Daten zu finden, und können für die Sortierstufe der verwendet werden Burrows -Wheeler -Transformation. Varianten der LZW Kompressionsschemata verwenden Suffixbäume (LZSS). Ein Suffixbaum wird auch in verwendet Suffix -Baumclustering, a Datenclustering Algorithmus, das in einigen Suchmaschinen verwendet wird.^[23]

Implementierung

Wenn jeder Knoten und jede Kante in dargestellt werden können in ${\ displayStyle \ theta (1)}$ Raum, der gesamte Baum kann dargestellt werden ${\ displayStyle \ theta (n)}$ Platz. Die Gesamtlänge aller Saiten an allen Kanten im Baum ist ${\ displayStyle o (n^{2})}$, aber jede Kante kann als Position und Länge eines Substrings von gespeichert werden S, eine vollständige Raumnutzung von ${\ displayStyle \ theta (n)}$ Computerwörter. Die schlimmste Flächennutzung eines Suffixbaums ist mit a zu sehen Fibonacci Wortdie vollen geben ${\ displayStyle 2n}$ Knoten.

Eine wichtige Wahl bei der Implementierung einer Suffixbaum sind die Eltern-Kind-Beziehungen zwischen Knoten. Am häufigsten ist die Verwendung verlinkte Listen genannt Geschwisterlisten. Jeder Knoten hat einen Zeiger auf sein erstes Kind und auf den nächsten Knoten in der untergeordneten Liste ist er Teil. Andere Implementierungen mit effizienten Laufzeiteigenschaften verwenden Hash -Karten, sortiert oder ungeortiert Arrays (mit Array -Verdoppelung), oder ausgeglichene Suchbäume. Wir sind interessiert an:

• Die Kosten für die Suche nach dem Kind in einem bestimmten Charakter.
• Die Kosten für das Einsetzen eines Kindes.
• Die Kosten für die Einbeziehung aller Kinder eines Knotens (geteilt durch die Anzahl der Kinder in der folgenden Tabelle).

Lassen σ die Größe des Alphabets sein. Dann haben Sie die folgenden Kosten:

$oder Arrays}} & o (\ sigma) & \ theta (1) & \ theta (1) \\ {\ text {Bitwise -Geschwisterbäume}} & o (\ log \ sigma) & \ theta (1) & \ theta (1) \\ {\ text {Hash Maps}} & \ theta (1) & \ theta (1) & o (\ sigma) \\ {\ text {Balanced Search Tree}} & o (\ log \ sigma) & o (\ log \ \ Sigma) & o (1) \\ {\ text {sortierte Arrays}} & o (\ log \ sigma) & o (\ sigma) & o (1) \\ {\ text {Hash Maps + SIBLING LISTS}} & o (1) & o (1) & o (1) \ end {Array}}}$

Die Einfügungskosten werden abgeschrieben und die Kosten für Hashing für perfektes Hashing erhalten.

Die große Menge an Informationen in jedem Rand und Knoten macht den Suffixbaum sehr teuer und verbraucht das 10- bis 20 -fache der Speichergröße des Quelltextes in guten Implementierungen. Das Suffix -Array reduziert diese Anforderung auf den Faktor 8 (für Array einschließlich des Arrays LCP Werte, die innerhalb von 32-Bit-Adressraum und 8-Bit-Zeichen aufgebaut sind.) Dieser Faktor hängt von den Eigenschaften ab und kann 2 mit Verwendung von 4-Byte-breiten Zeichen erreichen (erforderlich, um ein beliebiges Symbol in einigen zu enthalten Unix-artig Systeme, siehe wchar_t) auf 32-Bit-Systemen. Die Forscher haben weiterhin kleinere Indexierungsstrukturen gefunden.

Parallelkonstruktion

Es wurden verschiedene parallele Algorithmen vorgeschlagen, um die Suffix -Baumkonstruktion zu beschleunigen.^{[24][25][26][27][28]} Kürzlich ein praktischer paralleler Algorithmus für die Suffix -Baumkonstruktion mit ${\ displayStyle o (n)}$ Arbeit (sequenzielle Zeit) und ${\ displayStyle o (\ log ^{2} n)}$ Spanne Es wurde entwickelt. Der Algorithmus erreicht eine gute parallele Skalierbarkeit von gemeinsamen Multicore-Maschinen und kann das indizieren Menschliches Genom - ungefähr 3Gb -In weniger als 3 Minuten mit einer 40-Kern-Maschine.^[29]

Externe Konstruktion

Obwohl linear, ist die Speicherverwendung eines Suffixbaums signifikant höher als die tatsächliche Größe der Sequenzsammlung. Für einen großen Text kann die Konstruktion externe Speicheransätze erfordern.

Es gibt theoretische Ergebnisse zum Konstruktion von Suffixbäumen im externen Gedächtnis. Der Algorithmus von Farach Colon, Ferragina & Muthukrishnan (2000) ist theoretisch optimal, mit einer E/A -Komplexität, die der Sortierung entspricht. Die allgemeine Kombination dieses Algorithmus hat jedoch bisher seine praktische Umsetzung verhindert.^[30]

Andererseits gab es praktische Arbeiten für den Bau von Suffixbäumen auf Diskbasis, die auf (wenige) GB/Stunden skalieren. Die hochmodernen Methoden sind TDD,^[31] GITTER,^[32] Verdauen,^[33] und B²St.^[34]

TDD und Gitter skalieren bis zum gesamten menschlichen Genom, was zu einem auf diskonten Suffixbaum einer Größe in den zehn Gigabyte basierten Suffixbaum führt.^[31][32] Diese Methoden können jedoch keine effizienten Sammlungen von Sequenzen überschreiten, die 3 GB überschreiten.^[33] Digest erzielt deutlich besser und kann in der Reihenfolge von 6 GB in etwa 6 Stunden Sammlungen von Sequenzen verarbeiten.^[33] . Alle diese Methoden können Suffixbäume für den Fall effizient erstellen, wenn der Baum nicht in den Hauptspeicher passt, die Eingabe jedoch tut. Die neueste Methode, b²St, st,^[34] Skalen, um Eingänge zu verarbeiten, die nicht in den Hauptspeicher passen. ERA ist eine aktuelle Methode für parallele Suffix -Baumkonstruktion, die wesentlich schneller ist. ERA kann das gesamte menschliche Genom in 19 Minuten auf einem 8-Core-Desktop-Computer mit 16 GB RAM indizieren. Bei einem einfachen Linux -Cluster mit 16 Knoten (4 GB RAM pro Knoten) kann ERA das gesamte menschliche Genom in weniger als 9 Minuten indexieren.^[35]

Siehe auch

• Suffix Automaton

Anmerkungen

Verweise

• Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), Das Design und die Analyse von Computeralgorithmen, Lesen/MA: Addison-Wesley, ISBN 0-201-00029-6.
• Apostolico, a.; Iliopoulos, C.; Landau, G. M.; Schieber, b.; Vishkin, U. (1988), "Parallele Konstruktion eines Suffixbaums mit Anwendungen", Algorithmus, 3 (1–4): 347–365, doi:10.1007/bf01762122, S2CID 5024136.
• Baeza-yates, Ricardo A.; Gonnet, Gaston H. (1996), "Schneller Text sucht nach regelmäßigen Ausdrücken oder Automatik, um nach Versuchen zu suchen.", Journal of the ACM, 43 (6): 915–936, doi:10.1145/235809.235810, S2CID 1420298.
• Barsky, Marina; Steg, ulrike; Thomo, Alex; Upton, Chris (2008), "Eine neue Methode zur Indexierung von Genomen unter Verwendung von Suffix-Bäumen auf dem Schleifen", CIKM '08: Verfahren der 17. ACM -Konferenz über Informations- und Wissensmanagement (PDF), New York, NY, USA: ACM, S. 649–658.
• Barsky, Marina; Steg, ulrike; Thomo, Alex; Upton, Chris (2009), "Suffix -Bäume für sehr große genomische Sequenzen", CIKM '09: Verfahren der 18. ACM -Konferenz über Informations- und Wissensmanagement (PDF), New York, NY, USA: ACM.
• Farach, Martin (1997),, "Optimale Suffixbaumkonstruktion mit großen Alphabeten" (PDF), 38. IEEE -Symposium für Fundamente der Informatik (FOCS '97), S. 137–143.
• Farach, Martin; Muthukrishnan, S. (1996), "Optimale logarithmische Zeit Randomisierte Suffixbaumkonstruktion", Internationales Kolloquium für Automatensprachen und Programmierung (PDF).
• Farach Colon, Martin; Ferragina, Paolo; Muthukrishnan, S. (2000), "Auf der Sortierkomplexität der Suffix-Baumkonstruktion.", Journal of the ACM, 47 (6): 987–1011, doi:10.1145/355541.355547, S2CID 8164822.
• Giegerich, R.; Kurtz, S. (1997), "Von Ukkonen bis McCreight und Weiner: Eine einheitliche Sichtweise der linearen Suffix-Baumkonstruktion" (PDF), Algorithmus, 19 (3): 331–353, doi:10.1007/pl00009177, S2CID 18039097, archiviert von das Original (PDF) Am 2016-03-03, abgerufen 2012-07-13.
• Gusfield, Dan (1999), Algorithmen für Zeichenfolgen, Bäume und Sequenzen: Informatik und Computerbiologie, Cambridge University Press, ISBN 0-521-58519-8.
• Hariharan, Ramesh (1994), "Optimales paralleles Suffix -Baumkonstruktion", ACM -Symposium über die Theorie des Computers (PDF).
• Iliopoulos, Costas; Rytter, Wojciech (2004), "über parallele Transformationen von Suffix -Arrays in Suffixbäume", 15. Australasian Workshop zu kombinatorischen Algorithmen, Citeseerx 10.1.1.62.6715.
• Mansour, Essam; Allam, Amin; Skiadopoulos, Spiros; Kalnis, Panos (2011), "ERA: Effiziente serielle und parallele Suffix -Baumkonstruktion für sehr lange Saiten" (PDF), Verfahren der VLDB -Stiftung, 5 (1): 49–60, Arxiv:1109.6884, Bibcode:2011ArXIV1109.6884m, doi:10.14778/2047485.2047490, S2CID 7582116.
• McCreight, Edward M. (1976), "Ein raumökonomischer Suffix-Baumkonstruktionsalgorithmus", Journal of the ACM, 23 (2): 262–272, Citeseerx 10.1.1.130.8022, doi:10.1145/321941.321946, S2CID 9250303.
• Phoophakdee, Benjarath; Zaki, Mohammed J. (2007), "Genom-Skale-Suffix-Baumindexierung", genoms Scale-basierte Suffixbaumindexierung ", Sigmod '07: Verfahren der ACM Sigmod International Conference zum Management von Daten, New York, NY, USA: ACM, S. 833–844, Citeseerx 10.1.1.81.6031.
• Sahinalp, Cenk; Vishkin, Uzi (1994), "Symmetrie Breaking for Suffix Tree Construction", ACM -Symposium über die Theorie des Computers, doi:10.1145/195058.195164, S2CID 5985171
• Smyth, William (2003), Computermuster in Saiten, Addison-Wesley.
• Shun, Julian; Blelloch, Guy E. (2014), "Ein einfacher paralleler kartesischer Baumalgorithmus und seine Anwendung auf parallele Suffix -Baumkonstruktion", ACM -Transaktionen auf dem parallelen Computing, 1: 1–20, doi:10.1145/2661653, S2CID 1912378.
• Tata, Sandeep; Hankins, Richard A.; Patel, Jignesh M. (2003), "Practical Suffix Tree Construction", VLDB '03: Verfahren der 30. Internationalen Konferenz über sehr große Datenbasis (PDF), Morgan Kaufmann, S. 36–47.
• Ukkonen, E. (1995), "Online-Konstruktion von Suffixbäumen" (PDF), Algorithmus, 14 (3): 249–260, doi:10.1007/bf01206331, S2CID 6027556.
• Weiner, P. (1973), "Lineare Muster -Matching -Algorithmen" (PDF), 14. jährliches IEEE -Symposium zum Umschalten und Automatentheorie, S. 1–11, doi:10.1109/Swat.1973.13.
• Zamir, Oren; Etzioni, Oren (1998), "Webdokumentclustering: Eine Machbarkeitsdemonstration", SIGIR '98: Proceedings der 21. jährlichen International ACM Sigir -Konferenz für Forschung und Entwicklung im Informationsabruf, New York, NY, USA: ACM, S. 46–54, Citeseerx 10.1.1.36.4719.

Externe Links

• Suffixbäume durch Sartaj Sahni
• Nists Wörterbuch über Algorithmen und Datenstrukturen: Suffixbaum
• Universelle Datenkomprimierung basierend auf der Transformation des Burrows-Rads: Theorie und Praxis, Anwendung von Suffixbäumen in der BWT
• Theorie und Praxis der prägnanten DatenstrukturenC ++ - Implementierung eines komprimierten Suffixbaums
• Ukkonens Suffix Tree -Implementierung in C. Teil 1 Teil 2 Teil 3 Teil 4 Teil 5 Teil 6
• Online -Demo: Ukkonens Suffix -Baumvisualisierung