10.05.2025Auf anderen Unterseiten hier haben wir Bäume als Sammlungen von Zahlen gezeigt, so wie Heaps und Suchbäume. Auf dieser Seite führen wir den Trie oder Präfixbaum ein, als Baum von Buchstaben in Zeichenketten. Abstrakt betrachtet, ist ein Trie eine Vorrichtung um Zeichenketten als Schlüssel effizient zu speichern und sie mit Werten zu assoziieren, in diesem Fall mit Zahlen.
Auf dem obigen Diagramm sehen wir einen kleinen Trie, abgeleitet von den Worten im Satz “das weinfass das frau weber leerte verheerte ihre leberwerte.” Es wird gebildet indem jedes Wort einzeln eingefügt wird und mit seiner Position im Satz assoziiert wird. Kleine Knoten enthalten Buchstaben in Zeichenfolgen, wohingegen große Knoten zusätzlich einen Wert enthalten, dessen Vorhandensein einen Schlüssel terminiert.
Auf diesem obigen Diagramm haben wir den Satz “die katze tritt die treppe krumm der kater tritt sie gerade” verwendet. Hier zeigen wir was passiert, wenn der Trie auf der Suche nach vorhandenen Schlüsseln (grün) und abwesenden (rot) durchsucht wird. Wenn die Buchstaben des Schlüssels auf einem Knoten mit Wert (große Knoten) enden, war das nachschlagen erfolgreich. Andere Fälle, so wie kein Wert vorhanden oder nicht alle Buchstaben gefunden, zeigen an dass der Schlüssel nicht im Präfixbaum vorhanden ist.
Auf dem obigen Diagramm starten wir mit einem leeren Trie und fügen nach und nach die Wort aus dem Satz “der mond schien schon schön” ein. Der Algorithmus wechselt dazu Schritte zwischen dem Suchen einer Position im Trie und dem Einfügen einer Kette von Zeichen ab.
Tries erlauben erweiterte Operationen als blos einen Schlüssel nachzuschlagen. Hier schlagen wir alle Schlüssel nach, die mit einem gegebenem Präfix beginnen. Zuerst muss der Präfix im Baum gefunden werden, und danach müssen alle Knoten unter dem Präfixknoten durchsucht werden. Falls keine solchen Schlüssel vorhanden sind, gibt dies der Algorithmus gegenbenfalls aus.
Eine Anwendung der Präfixsuche ist die Vervollständigung von Befehlen. Nachdem ein paar Buchstaben eines Befehls eingegeben sind, schlägt ein Algorithmus mögliche Vervollständigungen aus dem Trie vor.
Eine weitere erweiterte Operation auf einem Trie ist die Suche mit Joker, bei der manche Stellen in der Zeichenkette mit einem beliebigen Buchstaben übereinstimmen. Wir zeigen diese Operation auf diesem Diagramm, wobei die nachzuschlagenden Zeichenketten einen oder mehrere Punkte (•) enthalten können, als Joker. Beim durchlaufen des Präfixbaumes wird ein Knoten in gelb markiert, wenn der Joker eingesetzt wurde. Wie zuvor kann das Resultat auch mehrere Schlüssel sein, die alle mit der Anfrage übereinstimmen.
Ein Trie mit einer ordentlichen Menge an Text aus dem lateinischen Alphabet ist auf einem Bildschirm schwer darzustellen, weil jeder Knoten bis zu 26 Kindknoten haben kann, der Anzahl an Buchstaben im Alphabet. Stattdessen begnügen wir uns an dieser Stelle mit einem kleineren Alphabet, dem genetischen Code, der nur vier Buchstaben hat: A, C, G und T. Trotzdem verbraucht der Trie, wie man oben sehen kann, den horizontalen Platz ziemlich schnell. Hier haben wir drei Buchstaben lange Sequenzen in ein Trie eingefügt.
Eine echte Trie Datenstruktur würde möglicherweise Millionen von Gensequenzen enthalten, jede tausende Buchstaben lang, und könnte trotzdem Schlüssel effizient auslesen.
Hier haben wir den Text aus den Knoten entfernt, und diese kleiner gemacht, um eine weitere Ebene aufzunehmen. Diesmal haben wir wie oben Gencodes, aber vier Buchstaben lang eingefügt.
Es gibt mehr zu Algorithmen und Datenstrukturen auf unserer Hauptseite zu entdecken.