SuffixTree, SuffixTrie, linear time Algo von Esko Ukkonen, 1995

• meine php Implementierung und Demo
• Wikipedia
• Original Paper

SuffixTrie

• Prefix Baum mit 1 Buchstaben pro Node ==> quadratische Kosten

Suffix Tree

• Ukkonen's algorithm. In computer science, Ukkonen's algorithm is a linear-time, online algorithm for constructing suffix trees, proposed by Esko Ukkonen in 1995.[1], in linear time
• im folgenden bezeichnet src den Source string für den ein Suffixtree zu erstellen ist. Character Positionen sind 0-relative. substrings werden mit s[b, e] bezeichnet für den Substring von character index b bis e-1, also mit der Länge e-b.

Prinzipien

• statt Trie, Tree mit Suffix aus mehreren Buchstaben pro Node. Jeder innere Node hat mindestens zwei Kinder - alle Kinder haben verschiedene Anfangsbuchstaben, da wir n leafs haben (src[i, e]) also maximal 2n nodes
• die delta substrings werden durch Indexes cFi (Anfang) und cEn (1 + Index letztes Zeichen) im src codiert, in meiner Implementation zusätzlich ein Index cRo für den Anfang des Gesamtstrings von Root bis zum aktuellen Node (das ist für den Algorithms nicht notwending, hilft aber für visualisierung und dem Testen von Pre- und Post Conditions).
• neben den Links um Parent und Children zu finden ein Link auf den node suf(nd)[1], also den Suffix der beim nächsten Zeichen anfängt
• Der Algorithmus berechnte den Tree schrittweise auf über die zwischen Trees T₁, T₂, ... T_e mit
  • T_k ist ein temporärer suffixTree für src[0,k] mit folgenden Abweichungen
  • alle non-leaf nodes sind vorhanden und zeigen auf src[i, k-1] mit i < k-1
  • es müssen nicht alle Leaf Nodes vorhanden sein, die vorhandenen zeigen auf src[i,e] statt src[i, k], d.h. die Gesamtlänge nicht die aktuelle Länge k von T_k. Damit entfällt der (nichtlineare) Aufwand, in jedem Schritt die Längen aller Leafs nachzuführen. Zudem werden nur leafs erstellt, die einfach weiterwerwendet werden können. Z.B. hat T₃ von aaaa hat nur 2 nodes: [0 => root, 1 => [par => 0, delta => 'aaaa', suf => 1]]
  • um den vollstanding Tree zu bekommen, braucht man lediglich an den String eine Terminator Character, der sonst nicht vorkommt anzuhängen. Alternativ kann man auch mit T_e arbeiten, man braucht lediglich beim walk durch den Baum, die (restliche) Länge zu berücksichtigen

Algorithmus erweitert T_k auf T_k+1

• wandert durch die Blätter vom ersten (für src[0,e]) via den suf link
• ein Node für src[i,j] bleibt ein Node für src[i,j], es kann aber ein neuer parent erzeugt werden, um eine vorangehende Verästelung einzufügen.
• gemäss Voraussetzung ist T_k_ korrekt für src[0, k], es muss also lediglich überprüft werden, ob für src[k] Anpassungen nötig sind
  • in diesem Fall muss an einen parent ein neues Child angehängt werden, oder eine neue Verästelung erstellt werden. Im zweiten Fall müssen rekursiv auch der suf Link des neuen Parents korrigiert werden

Kosten

• es werden maximal 2n Nodes erstellt
• das durchsuchen der Blätter / nodes muss aber optimiert werden
  • es muss nicht bei jedem Schritt von vorne begonnen werden, leafs die auf den korrekten suffix src[i, e] müssen in keinem folgenden Schritt mehr überprüft werden
  • nach diesen endgültigen Leafs muss in einem Schritt nur solange weitergewandert werden, bis der erste Node mit bereits korrektem Suffix angetroffen wird
  • d.h. die Kosten sind linear zum erstellen von 2n Nodes - da ein Node Pointer auf andere Nodes und Characters in src enthält, brauchen die Pointer log(n) Bits sind die Totalkosten aber n log(n) und nicht linear wie überall geschrieben