data-structures
Trie (Präfixbaum / Radixbaum)

Einführung in Trie

Haben Sie sich jemals gefragt, wie die Suchmaschinen funktionieren? Wie stellt Google in nur wenigen Millisekunden Millionen von Ergebnissen vor Ihnen zusammen? Wie findet eine riesige Datenbank, die Tausende von Kilometern von Ihnen entfernt ist, die gesuchten Informationen heraus und sendet sie Ihnen zurück? Der Grund dafür ist nicht nur durch den Einsatz von schnellerem Internet und Supercomputern möglich. Einige faszinierende Suchalgorithmen und Datenstrukturen arbeiten dahinter. Einer von ihnen ist Trie .

Trie , auch Digital Tree und manchmal Radix Tree oder Prefix Tree (wie durch Präfixe gesucht werden kann), ist eine Art Suchbaum - eine geordnete Baumdatenstruktur, in der ein dynamisches Set oder ein assoziatives Array gespeichert wird, in dem sich die Schlüssel befinden normalerweise saiten. Es ist eine dieser Datenstrukturen, die leicht implementiert werden kann. Nehmen wir an, Sie haben eine riesige Datenbank mit Millionen von Wörtern. Sie können trie verwenden, um diese Informationen zu speichern. Die Komplexität der Suche nach diesen Wörtern hängt nur von der Länge des gesuchten Wortes ab. Das heißt, es kommt nicht darauf an, wie groß unsere Datenbank ist. Ist das nicht erstaunlich?

Nehmen wir an, wir haben ein Wörterbuch mit diesen Wörtern:

algo
algea
also
tom
to

Wir möchten dieses Wörterbuch so speichern, dass wir das gesuchte Wort leicht herausfinden können. Eine der Methoden würde darin bestehen, die Wörter lexikographisch zu sortieren, wie Wörterbücher aus dem echten Leben Wörter speichern. Dann können wir das Wort durch eine binäre Suche finden . Eine andere Möglichkeit ist die Verwendung von Prefix Tree oder Trie . Das Wort 'Trie' kommt vom Wort Re trie val. Präfix bezeichnet hier das Präfix des Strings, das folgendermaßen definiert werden kann: Alle Teilstrings, die ab dem Anfang eines Strings erstellt werden können, werden als Präfix bezeichnet. Zum Beispiel: 'c', 'ca', 'cat' sind das Präfix der Zeichenfolge 'cat'.

Nun zurück zu Trie . Wie der Name schon sagt, erstellen wir einen Baum. Zuerst haben wir einen leeren Baum mit nur der Wurzel:

Wir werden das Wort "algo" einfügen. Wir erstellen einen neuen Knoten und benennen die Kante zwischen diesen beiden Knoten mit 'a' . Aus dem neuen Knoten erstellen wir eine weitere Kante mit dem Namen 'l' und verbinden diese mit einem anderen Knoten. Auf diese Weise erstellen wir zwei neue Kanten für 'g' und 'o' . Beachten Sie, dass wir keine Informationen in den Knoten speichern. Im Moment ziehen wir nur in Betracht, aus diesen Knoten neue Kanten zu erstellen. Nennen wir von nun an eine Kante namens 'x' - edge-x

Nun wollen wir das Wort 'algea' hinzufügen. Wir brauchen eine Kante von Wurzel, die wir bereits haben. Wir müssen also keinen neuen Rand hinzufügen. Ähnlich haben wir eine Kante von 'a' nach 'l' und 'l' nach 'g' . Das bedeutet, dass 'alg' bereits im Trie ist . Wir fügen nur Edge-E und Edge-A hinzu .

Wir werden das Wort "auch" hinzufügen. Wir haben das Präfix 'al' von root. Wir werden nur hinzufügen ‚so‘ mit ihm.

Fügen wir 'tom' hinzu . Diesmal erstellen wir eine neue Kante von root, da noch kein Präfix von tom erstellt wurde.

Wie sollen wir nun "to" hinzufügen? 'to' ist vollständig ein Präfix von 'tom' , wir müssen also keine Kante hinzufügen. Was wir tun können, ist, dass wir in einigen Knoten Endmarken setzen können. In den Knoten, an denen mindestens ein Wort abgeschlossen ist, werden Endmarken gesetzt. Grüner Kreis kennzeichnet die Endmarke. Der Trie sieht so aus:

Sie können leicht verstehen, warum wir die Endmarken hinzugefügt haben. Wir können die in trie gespeicherten Wörter bestimmen. Die Zeichen befinden sich an den Kanten und Knoten enthalten die Endmarken.

Nun fragen Sie vielleicht, wozu solche Wörter gespeichert werden sollen. Nehmen wir an, Sie werden aufgefordert, das Wort 'alice' im Wörterbuch zu finden. Sie werden den Trie durchqueren. Sie prüfen, ob es einen root-a gibt. Dann prüfe von 'a' , ob es einen Rand-l gibt . Danach werden Sie kein Edge-i finden , sodass Sie zu dem Schluss gelangen können, dass das Wort Alice nicht im Wörterbuch vorhanden ist.

Wenn Sie nach dem Wort "alg" im Wörterbuch gesucht werden, durchqueren Sie root-> a , a-> l , l-> g , aber am Ende finden Sie keinen grünen Knoten. Das Wort existiert also nicht im Wörterbuch. Wenn Sie nach "Tom" suchen, landen Sie in einem grünen Knoten, dh das Wort ist im Wörterbuch vorhanden.

Komplexität:

Die maximale Anzahl an Schritten, die erforderlich sind, um nach einem Wort in einem Trie zu suchen, ist die Länge des gesuchten Wortes. Die Komplexität beträgt O (Länge) . Die Komplexität beim Einfügen ist gleich. Der zur Implementierung von trie erforderliche Speicherplatz hängt von der Implementierung ab. In einem anderen Beispiel sehen Sie eine Implementierung, in der wir 10 ⁶ Zeichen (keine Wörter, Buchstaben) in einem Trie speichern können.

Verwendung von Trie:

• Einfügen, Löschen und Suchen nach einem Wort im Wörterbuch.
• Um herauszufinden, ob eine Zeichenfolge ein Präfix einer anderen Zeichenfolge ist.
• Um herauszufinden, wie viele Zeichenfolgen ein gemeinsames Präfix haben.
• Vorschlag der Kontaktnamen in unseren Telefonen abhängig vom Präfix, das wir eingeben.
• Ermittlung des längsten gemeinsamen Unterstrings von zwei Zeichenketten.
• Ermittlung der Länge von 'Common Prefix' für zwei Wörter mit 'Longest Common Ancestor'

Implementierung von Trie

Bevor Sie dieses Beispiel lesen, wird dringend empfohlen, die Einführung in Trie zu lesen.

Eine der einfachsten Möglichkeiten, Trie zu implementieren, ist die Verwendung der verknüpften Liste.

Knoten:

Die Knoten bestehen aus:

1. Variable für Endmarke.
2. Zeiger-Array auf den nächsten Knoten.

Die End-Mark-Variable gibt einfach an, ob es sich um einen Endpunkt handelt oder nicht. Das Zeigerarray kennzeichnet alle möglichen Kanten, die erstellt werden können. Für englische Alphabete beträgt die Größe des Arrays 26, da maximal 26 Kanten von einem einzigen Knoten erstellt werden können. Ganz am Anfang ist jeder Wert des Zeigerarrays NULL und die Endmarkenvariable ist falsch.

Node:
Boolean Endmark
Node *next[26]
Node()
    endmark = false
    for i from 0 to 25
        next[i] := NULL
    endfor
endNode

Jedes Element im Feld next [] verweist auf einen anderen Knoten. next [0] zeigt auf die Knotenfreigabekante a , next [1] zeigt auf die Knotenfreigabekante b und so weiter. Wir haben den Konstruktor von Node definiert, um Endmark als false zu initialisieren und NULL in alle Werte des next [] - Zeigerarrays einzufügen.

Um Trie zu erstellen, müssen wir root zuerst instanziieren. Dann erstellen wir vom Stammverzeichnis aus weitere Knoten, um Informationen zu speichern.

Einfügung:

Procedure Insert(S, root):    // s is the string that needs to be inserted in our dictionary
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        curr -> next[id] = Node()
    curr := curr -> next[id]
endfor
curr -> endmark = true

Hier arbeiten wir mit az . Um ihre ASCII-Werte in 0-25 zu konvertieren, subtrahieren wir den ASCII-Wert von 'a' von ihnen. Wir prüfen, ob der aktuelle Knoten (curr) eine Kante für das vorliegende Zeichen hat. Wenn dies der Fall ist, bewegen wir uns mit dieser Kante zum nächsten Knoten. Andernfalls erstellen wir einen neuen Knoten. Am Ende ändern wir die Endmarke in true.

Suchen:

Procedure Search(S, root)      // S is the string we are searching
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        Return false
    curr := curr -> id
Return curr -> endmark

Der Vorgang ist dem Einfügen ähnlich. Am Ende geben wir die Endmarke zurück . Wenn das Endzeichen wahr ist, bedeutet dies, dass das Wort im Wörterbuch vorhanden ist. Wenn es falsch ist, existiert das Wort nicht im Wörterbuch.

Dies war unsere Hauptimplementierung. Jetzt können wir ein beliebiges Wort in trie einfügen und danach suchen.

Streichung:

Manchmal müssen wir die Wörter löschen, die nicht mehr zum Speichern von Speicher verwendet werden. Zu diesem Zweck müssen wir die nicht verwendeten Wörter löschen:

Procedure Delete(curr):       //curr represents the current node to be deleted
for i from 0 to 25
    if curr -> next[i] is not equal to NULL
        delete(curr -> next[i])
    delete(curr)               //free the memory the pointer is pointing to

Diese Funktion geht an alle untergeordneten Knoten von curr , löscht sie und dann wird curr gelöscht, um den Speicher freizugeben . Wenn wir delete (root) aufrufen, wird der gesamte Trie gelöscht.

Trie kann auch mit Arrays implementiert werden.