Lektion
Die Theorie — Trie: Der Präfixbaum Schritt für Schritt
Ein Trie, auch Präfixbaum genannt, speichert eine Menge von Wörtern in einem Baum. Für jedes unterschiedliche Präfix gibt es einen Knoten. Die Wurzel steht für das leere Präfix; jede Kante trägt einen Buchstaben. Der Pfad von der Wurzel zu einem Knoten ergibt somit dessen Präfix. Ein Knoten ist markiert, wenn sein Präfix ein vollständiges gespeichertes Wort ist. Wörter mit gleichem Anfang teilen sich den Pfad für diesen Anfang. Bei einer Wortsuche folgst du den Buchstaben des Wortes von der Wurzel aus. Bei einer Präfixsuche gehst du zum Knoten des Präfixes und sammelst alle markierten Knoten darunter. Edward Fredkin gab der Struktur 1960 ihren Namen, abgeleitet von retrieval. Er sah die Aussprache wie beim englischen Wort tree vor.
Was die einzelnen Symbole bedeuten
W- Anzahl der Wörter in der Liste
L- Gesamtzahl der Buchstaben aller Wörter
N- Anzahl der Knoten, einer pro unterschiedlichem Präfix, ohne die Wurzel
- Setzt voraus
- Wir verwenden Kleinbuchstaben von a bis z, ein Byte pro Buchstabe und 64-Bit-Zeiger. In beiden Strukturen zählen wir weder Füllbytes zur Speicherausrichtung noch Verwaltungsaufwand der Speicherverwaltung mit. Bei der binären Suche zählt jedes verglichene Buchstabenpaar. Der Vergleich endet beim ersten Unterschied; das Erreichen eines Wortendes verursacht keine zusätzlichen Kosten. Für die Hashtabelle nehmen wir den günstigsten Fall an: keine Kollisionen. Im 18-Byte-Knoten sind die Kindknoten alphabetisch geordnet. Die Suche unter ihnen endet daher, sobald sie den gesuchten Buchstaben überschritten hat.
Aufgabe vollständig gelöst
-
Wie viele gemeinsame Präfixe braucht der Trie, um weniger Speicher zu belegen? 4 Schritte
Klick auf Lange Wörter: 85 Buchstaben in 21 Knoten, drei Viertel davon gemeinsam genutzt. Trotzdem braucht der Trie mit 18-Byte-Knoten 396 Byte, die Liste nur 157. Wenn alle Wörter einer Liste k Buchstaben lang sind, ist der Trie gegenüber der Liste am günstigsten, wenn sie jedes mögliche Wort enthält. Für welche kleinste Wortlänge k braucht dieser Trie bei den hier verwendeten Bytezahlen weniger Speicher als die einfache Liste?
-
Hier sind es 21 Knoten und die Wurzel: 22 × 18 = 396 Byte. Die Liste speichert 85 Buchstaben und für jedes ihrer 8 Wörter ein Abschlussbyte sowie einen Zeiger von 8 Byte: 85 + 9 × 8 = 157.
-
Alle Zeichenfolgen der Länge k ergeben 26k Wörter mit je k Buchstaben. Die Liste braucht daher (k + 9) × 26k Byte.
-
Der Trie braucht für jede Zeichenfolge mit 1 bis k Buchstaben einen Knoten: 26 + 26² + … + 26k, etwas weniger als 26/25 × 26k. Mit der Wurzel und 18 Byte pro Knoten ergibt das knapp 18,72 × 26k Byte.
-
Die Liste braucht also mehr Speicher, sobald k + 9 größer als 18,72 ist. Das gilt erstmals für k = 10. Bei k = 9 braucht der Trie 4,0 % mehr Speicher als die Liste, bei k = 10 braucht er 1,5 % weniger.
Antwort
10 Buchstaben, wenn die Liste alle 2610 möglichen Wörter enthält, also etwa 1,4 × 1014 Wörter. Bei 209-Byte-Knoten muss k + 9 nach derselben Rechnung größer als etwa 217 sein. Dafür braucht es Wörter mit 209 Buchstaben.
-
Lernpfad
Was eine Datenstruktur mit wenig Aufwand leistet
Quellen (3)
- The name, its origin in "retrieval", and Fredkin's intended pronunciation, quoted in the definition: Paul E. Black, "trie", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., NIST, entry modified 12 February 2019.
- The paper that named the structure: Edward Fredkin, "Trie memory," Communications of the ACM 3(9), September 1960, pp. 490–499.
- The earlier description of searching on letter-by-letter keys: René de la Briandais, "File searching using variable length keys," Papers presented at the Western Joint Computer Conference, San Francisco, 3–5 March 1959, pp. 295–298.