TST-Symboltabelle (Algorithmus 5.5)

So geht’s: Beim Öffnen läuft der Testclient mit den 16 Wörtern, aus denen der TST in Abbildung 5.29 entsteht. Zuerst kommt put für „she sells sea shells by the sea shore the shells she sells are surely sea shells“, spätere Wörter überschreiben dabei die Werte früherer. Danach folgt get("sea") wie in der Abbildung, dann get für shells, surely und are, und für „shell“ und „shelter“, die es nicht gibt. Jeder Knoten zeigt sein Zeichen c. Durchgezogene Linien sind mid-Verweise, dort geht es zum nächsten Zeichen. Gestrichelte Linien sind left und right, dort bleibt das Zeichen dasselbe. Die rote Zahl ist val. Rechts steht der Vergleich am aktuellen Knoten und nach jedem get die Zahl der Zeichenvergleiche. Darunter steht der Speicher, verglichen mit dem R-Wege-Trie für dieselben Schlüssel. „sortiert eingefügt“ zeigt den schlimmsten Fall: a bis h nacheinander ergeben eine Kette nach rechts. Über die zweite Zeile führst du eigene put- und get-Aufrufe aus. „Zufallsschlüssel“ erzeugt kurze Strings aus a, e, h, s und t, „↺ Neu starten“ springt zurück zum Beispiel.

Erklärung

TST-Symboltabelle (Algorithmus 5.5), Klasse TST, ternärer Suchtrie. Löst das Speicherproblem des R-Wege-Tries [46]: pro Knoten drei Verweise statt R.

Aufbau eines Knotens:

• c: ein Zeichen, ausdrücklich gespeichert (im R-Wege-Trie war das Zeichen nur durch die Position im Array gegeben).
• left: Teiltrie für Schlüssel, deren aktuelles Zeichen kleiner als c ist.
• mid: Teiltrie für Schlüssel, deren aktuelles Zeichen gleich c ist. Hier geht es zum nächsten Zeichen.
• right: Teiltrie für größere Zeichen.
• val: Wert, falls hier ein Schlüssel endet. Diesmal direkt als Value, kein Object-Cast nötig, weil kein generisches Array im Spiel ist.

Bildlich: Jede Ebene eines R-Wege-Tries mit ihren bis zu R Verzweigungen wird durch einen kleinen binären Suchbaum über die Zeichen ersetzt. Nur über mid kommt man zum nächsten Zeichen.

Die Operationen, wieder im BST-Rekursionsmuster [24]:

• get: Zeichen an Position d mit x.c vergleichen.
  • kleiner → nach links, gleiches d,
  • größer → nach rechts, gleiches d,
  • gleich und noch nicht letztes Zeichen → nach mid, d + 1,
  • gleich und letztes Zeichen → dieser Knoten, val zurückgeben.
• put: genauso absteigen. Fehlt ein Knoten, neuen mit dem aktuellen Zeichen anlegen. Am letzten Zeichen val setzen.

Die schöne Parallele:

• Quicksort [11] verhält sich zum binären Suchbaum [24]
• wie 3-Wege-Quicksort für Strings [45] zum TST.
• In beiden Fällen entspricht die Rekursionsstruktur des Sortierverfahrens genau der Baumstruktur: kleiner links, gleich in der Mitte mit nächstem Zeichen, größer rechts.

Kosten:

• Speicher: 3 Verweise pro Knoten, also etwa 3N bis 3NL insgesamt. Bei R = 256 ein Bruchteil des R-Wege-Tries, bei Unicode der Unterschied zwischen machbar und unmöglich.
• Suchtreffer bei zufälligen Schlüsseln: etwa L + ln N Knoten (L Schritte über mid plus die Wege nach links und rechts).
• Erfolglose Suche: meist nur etwa ln N.
• Schlimmster Fall: Wie ein unbalancierter BST kann der TST entarten, etwa bei sortierter Einfügereihenfolge. Abhilfe im Buch: an der Wurzel R- oder R²-Wege-Verzweigung (Hybrid), oder balancieren.
• Unabhängig vom Alphabet: Die Kosten hängen nicht von R ab.

Gleiche Stringoperationen wie beim Trie: keysWithPrefix, longestPrefixOf, keysThatMatch, sortiertes keys(). Alles funktioniert analog.

Trie vs. TST:

Kapitel 5 bisher:

• Algorithmus 5.1: LSD-Sortierverfahren [43]
• Algorithmus 5.2: MSD-Sortierverfahren [44]
• Algorithmus 5.3: 3-Wege-Quicksort für Strings [45]
• Algorithmus 5.4: Trie-Symboltabelle [46]
• Algorithmus 5.5: TST-Symboltabelle [47]