Trie
Was ist ein Trie ? đ€
Trie ist eine Baumbasierte Datenstruktur, die in der Informatik verwendet wird, um das Suchen von Zeichenkette zu vereinfachen
Erfinder dieser Datenstruktur ist der Physiker Edward Fredkin. Dabei gibt es drei Trie Formen: Standard Trie, Komprimierter Trie und Suffix Trie. Ein Standard Trie lĂ€sst sich folgenderweise definieren: Sei $S={S_{1},\dots ,S_{k}}$ eine Menge von Zeichenketten ĂŒber dem Alphabet $â$, sodass kein String in PrĂ€fix eines anderen String. Dadurch eignen sich Tries hervorragend fĂŒrs Pattern Matching und fĂŒr die AutovervollstĂ€ndigung beim Schreiben von Texten oder von Quellcode. Es gibt jedoch einige wichtige Bemerkungen, die genannt werden sollten. Es sei eine Menge $S$ von $s$ Strings der GesamtlĂ€nge $n$ aus einem Alphabet der GröĂe $k$ und die LĂ€nge des Strings $w$ :
- Es mĂŒssen alle Regeln einer Baumstruktur beachten werden
- Die Höhe von $T$ ist gleich lang des LÀngsten Strings in $S$,
- Die Anzahl der Knoten von $T$ ist $O(n)$,
- Bei der Suche nach $S$ betrÀgt $O(w)$.
Folgende Abbildung zeigt die Zeichnketten "bla", "bar", "blubb" und "foo" in einem unkomprimierten Trie. Die tĂŒrkise FĂ€rbung an den Enden steht hier bei dafĂŒr, dass das gesuchte Wort identifiziert ist. In der Software wĂŒrde hier eine abstrakte Datenstruktur definiert werden, die eine Boolsche Variable besitzt und "isEndOfWord" heiĂen könnte.
Bei der Suche des Baumes wird immer bei der Wurzel angefangen, anschlieĂend wird das erste Zeichen, beispielsweise "b" bei der gesuchten Zeichenkette "bla" ab, mit den jeweils zwei unteren Kinderknoten. Wird bei einem der Kinderknoten eine Referenz bestĂ€tigt, wird dieser Kinderknoten besucht. Da das Zeichen b nun identifiziert ist wird mit dem Zeichen l fortgefahren. Dieser Vorgang wird solange wiederholt bis das Wort gefunden ist und alle Zeichen bis zum tĂŒrkisen Knoten identifiziert sind. Nach Zeichenkette "ba" zu suchen wĂ€re Aktuell nicht möglich, weil der Knoten A nicht tĂŒrkis gefĂ€rbt ist. Dieser Knoten könnte auf true gesetzt werden bei "isEndOfWord", dann hĂ€tten wir die Zeichenkette "ba" hinzugefĂŒgt.
Die Effizienzklasse bei der Suche kann dann in AbhÀngigkeit von n abgeschÀtzt werden, wenn allen (die Anzahl der gespeicherten Strings) und alle möglichen Strings aus den Buchstaben a-z einer bestimmten LÀnge m gespeichert wurden, weil von dem lÀngsten Fall ausgegangen werden kann. Eine höhere KomplexitÀt kann nicht erreicht werden.