Versuchen Sie die Implementierung in Python

1. Versuchen Sie die Datenstruktur in Python
2. Fügen Sie in Python einen String in einen Trie ein
3. Suchen Sie ein Element in einem Trie in Python
4. Versuchen Sie die Implementierung in Python

Versuche sind die Datenstrukturen, die wir zum Speichern von Zeichenfolgen verwenden. Sie ermöglichen es uns, Textzeichenfolgen so effizient wie möglich zu durchsuchen.

In diesem Artikel wird erläutert, wie wir einen Trie in Python implementieren können.

Versuchen Sie die Datenstruktur in Python

Sie können einen Trie als einen Baum betrachten, bei dem jeder Knoten aus einem Zeichen besteht. Jeder Knoten hat ein oder mehrere Kinder, je nachdem, ob es sich um ein internes Zeichen einer Zeichenfolge oder um das letzte Zeichen handelt.

Der Knoten, der das letzte Zeichen einer Zeichenfolge darstellt, hat kein Kind und markiert das Ende der Zeichenfolge. Wir werden eine Flag-Variable in die Klassendefinition aufnehmen, um das Ende einer Zeichenfolge zu markieren.

Jeder Knoten im Trie kann maximal 26 Kinder haben, wenn wir Strings speichern, die nur aus englischen Kleinbuchstaben bestehen. Wenn die Zeichenfolgen andere Zeichen als die Alphabete enthalten, ist die maximale Anzahl von Kindern eines bestimmten Knotens gleich der Gesamtzahl von unterschiedlichen Zeichen.

Sie können eine Node-Klasse in Python definieren, um einen Knoten eines Trie zu implementieren, wie im folgenden Beispiel gezeigt.

class Node:
    def __init__(self):
        self.children = []
        for i in range(26):
            self.children.append(None)
        self.isLeafNode = False

Hier haben wir eine Liste mit dem Namen Kinder erstellt, die verwendet wird, um zu definieren, ob ein Charakter ein Kind des aktuellen Knotens ist oder nicht. Da wir 26 Zeichen berücksichtigt haben, haben wir die Liste mit 26 None-Werten initialisiert.

Wenn ein Zeichen kein Kind des aktuellen Knotens ist, enthält seine Position den Wert None. Andernfalls speichert die diesem Zeichen entsprechende Position den Knoten für dieses Zeichen.

Beim Einfügen von Zeichen in die Liste Kinder speichern wir die Kinderknoten in der alphabetischen Reihenfolge der Zeichen. Mit anderen Worten, der untergeordnete Knoten des Buchstabens a wird bei Index 0 gespeichert, der untergeordnete Knoten des Buchstabens b wird bei Index 1 gespeichert usw.

Nach dem Erstellen eines Knotens müssen wir eine Klasse erstellen, um einen Trie zu definieren. In der Klasse definieren wir einen leeren Knoten mit einer Liste, die 26 None-Werte enthält, um die 26 Zeichen des englischen Alphabets darzustellen.

Wir nennen den leeren Knoten den Wurzel-Knoten.

class Trie:
    def __init__(self):
        self.root = Node()

Immer wenn eine Zeichenfolge in den Trie eingefügt wird, wird der Knoten, der das erste Zeichen der Zeichenfolge darstellt, zum untergeordneten Knoten des Wurzel-Knotens. Beachten Sie, dass wir die Knoten, die die nächsten Zeichen der Zeichenfolgen enthalten, entsprechend ihrer Position als Listenelemente speichern.

Nach dem Erstellen des root-Knotens werden wir in den folgenden Abschnitten die Methoden implementieren, um ein Wort in den Trie einzufügen und nach einem Wort im Trie zu suchen.

Fügen Sie in Python einen String in einen Trie ein

Um ein Zeichen in den Trie einzufügen, ermitteln wir zunächst die Länge der einzufügenden Zeichenkette. Danach beginnen wir mit dem Crawlen des Trie vom root-Knoten des Trie.

Das Folgende ist der Algorithmus zum Einfügen einer Zeichenfolge in den Trie:

1. Berechnen Sie die Länge der Zeichenfolge, die in den Trie eingefügt werden soll. Speichern Sie es in einer Variablen strLen.
2. Nehmen Sie eine Variable crawler und weisen Sie der Variable den root-Knoten des Trie zu.
3. Wenn Sie sich auf Ebene n befinden, überprüfen Sie, ob das n-te Zeichen der Zeichenfolge auf dieser Ebene im Trie vorhanden ist. Wenn ja, speichere seine Position in der Liste Kinder in einer Variablen position; gehen Sie dann zu 5 - andernfalls gehen Sie zu 4.
4. Erstelle einen neuen Knoten für den Trie und weise ihm den Index position des Crawlers zu.
5. Bewegen Sie den crawler auf die nächste Ebene.
6. Überprüfen Sie, ob wir das Ende der Zeichenfolge erreicht haben; wenn ja, gehen Sie zu 7 - andernfalls gehen Sie zu 3.
7. Markieren Sie den aktuellen Knoten als Ende der Zeichenfolge.

Nachdem wir den Algorithmus besprochen haben, lassen Sie uns nun diesen Algorithmus implementieren, um eine Zeichenfolge in einen Trie in Python einzufügen.

def insert(self, input_str):
    strLen = len(input_str)
    crawler = self.root
    for level in range(strLen):
        character = input_str[level]
        position = ord(character) - ord("a")
        if crawler.children[position] is None:
            crawler.children[position] = Node()
        crawler = crawler.children[position]
    crawler.isLeafNode = True

Suchen Sie ein Element in einem Trie in Python

Um zu suchen, ob eine Zeichenfolge in einem Trie vorhanden ist oder nicht, verwenden wir den folgenden Algorithmus.

1. Initialisieren Sie eine Variable crawler und weisen Sie der Variablen den root-Knoten des Trie zu.
2. Berechnen Sie die Länge des zu suchenden Strings im Trie. Speichern Sie es in einer Variablen strLen.
3. Finden Sie auf einer Ebene n heraus, ob das n-te Zeichen der Zeichenfolge in der Liste Kinder vorhanden ist. Wenn ja, gehen Sie zu 4; Andernfalls geben Sie False zurück.
4. Überprüfen Sie, ob der aktuelle Knoten ein Blattknoten ist. Wenn ja, gebe True zurück; andernfalls erhöhen Sie n und gehen Sie zu 3.

Wir haben den Algorithmus zum Suchen einer Zeichenfolge in einem Trie definiert. Lassen Sie uns es in Python implementieren.

def search(self, input_str):
    crawler = self.root
    strLen = len(input_str)
    for level in range(strLen):
        character = input_str[level]
        position = ord(character) - ord("a")
        if crawler.children[position] is None:
            return False
        crawler = crawler.children[position]
    return crawler.isLeafNode

Versuchen Sie die Implementierung in Python

Da wir die Methoden für Such- und Einfügeoperationen in einem Trie in Python implementiert haben, lassen Sie uns den Code anhand einiger Beispieloperationen ausführen.

class Node:
    def __init__(self):
        self.children = []
        for i in range(26):
            self.children.append(None)
        self.isLeafNode = False


class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, input_str):
        strLen = len(input_str)
        crawler = self.roothave
        for level in range(strLen):
            character = input_str[level]
            position = ord(character) - ord("a")
            if crawler.children[position] is None:
                crawler.children[position] = Node()
            crawler = crawler.children[position]
        crawler.isLeafNode = True

    def search(self, input_str):
        crawler = self.root
        strLen = len(input_str)
        for level in range(strLen):
            character = input_str[level]
            position = ord(character) - ord("a")
            if crawler.children[position] is None:
                return False
            crawler = crawler.children[position]
        return crawler.isLeafNode


x = Trie()
myStr = "aditya"
print("Inserting the string:", myStr)
x.insert(myStr)
myStr = "delftstack"
print("Inserting the string:", myStr)
x.insert(myStr)
myStr = "aaditya"
print("Inserting the string:", myStr)
x.insert(myStr)
print("aditya is present in the trie:", x.search("aditya"))
print("delftstack is present in the trie:", x.search("delftstack"))
print("python is present in the trie:", x.search("python"))

Ausgang:

Inserting the string: aditya
Inserting the string: delftstack
Inserting the string: aaditya
aditya is present in the trie: True
delftstack is present in the trie: True
python is present in the trie: False

Wir haben zuerst einen Trie in Python implementiert, indem wir die oben in diesem Beispiel besprochenen Algorithmen verwendet haben. Danach fügten wir drei Saiten, aditya, delftstack und aaditya in den Trie ein.

Dann führten wir Suchoperationen auf dem Trie durch, um zu überprüfen, ob die Zeichenfolgen aditya, delftstack und python im Trie vorhanden waren oder nicht. Sie können die Ausgabe im Beispiel beobachten.