Implementierung der Datenstruktur

Einführung

Das Wort trie ist ein Inflix des Wortes "re trie val", da der Trie ein einzelnes Wort in einem Wörterbuch mit nur einem Präfix des Wortes finden kann.

Trie ist eine effiziente Datenabrufdatenstruktur. Mit trie können Suchkomplexitäten an eine optimale Grenze gebracht werden, dh an die Länge der Zeichenfolge.

Es ist eine Mehrweg-Baumstruktur, die zum Speichern von Zeichenfolgen über einem Alphabet nützlich ist, wenn wir sie speichern. Es wurde verwendet, um große Wörterbücher des Englischen zu speichern, beispielsweise Wörter in Rechtschreibprüfungsprogrammen. Die Strafe für Versuche sind jedoch die Speicheranforderungen.

Was ist ein Versuch?

Ein Trie ist eine baumähnliche Datenstruktur, in der Zeichenfolgen gespeichert werden, und die Ihnen hilft, die mit dieser Zeichenfolge verknüpften Daten mithilfe des Präfixes der Zeichenfolge zu finden.

Angenommen, Sie möchten ein Wörterbuch erstellen, in dem Zeichenfolgen mit ihren Bedeutungen gespeichert werden. Sie müssen sich fragen, warum ich nicht einfach eine Hash-Tabelle verwenden kann, um die Informationen zu erhalten.

Ja, Sie können Informationen mithilfe einer Hash-Tabelle abrufen, aber die Hash-Tabellen können nur Daten finden, bei denen die Zeichenfolge genau mit der von uns hinzugefügten übereinstimmt. Aber der Versuch gibt uns die Möglichkeit, Zeichenfolgen mit gemeinsamen Präfixen, einem fehlenden Zeichen usw. im Vergleich zu einer Hash-Tabelle in kürzerer Zeit zu finden.

Ein Trie sieht normalerweise so aus,

Trie

Dies ist ein Bild eines Trie, in dem die Wörter {assoc, algo, all, also, tree, trie} gespeichert sind.

So implementieren Sie einen Versuch

Lassen Sie uns einen Versuch in Python implementieren, um Wörter mit ihren Bedeutungen aus einem englischen Wörterbuch zu speichern.

ALPHABET_SIZE = 26 # For English class TrieNode: def __init__(self): self.edges = [None]*(ALPHABET_SIZE) # Each index respective to each character. self.meaning = None # Meaning of the word. self.ends_here = False # Tells us if the word ends here.

Wie Sie sehen können, sind die Kanten 26 lang, wobei sich jeder Index auf jedes Zeichen im Alphabet bezieht. 'A' entspricht 0, 'B' 1, 'C' 2 ... 'Z' dem 25. Index. Wenn der gesuchte Charakter auf zeigt, bedeutet dies None, dass das Wort nicht im Versuch enthalten ist.

Ein typischer Trie sollte mindestens diese beiden Funktionen implementieren:

  • add_word(word,meaning)
  • search_word(word)
  • delete_word(word)

Zusätzlich kann man auch so etwas hinzufügen

  • get_all_words()
  • get_all_words_with_prefix(prefix)

Hinzufügen von Word zum Trie

 def add_word(self,word,meaning): if len(word)==0: self.ends_here = True # Because we have reached the end of the word self.meaning = meaning # Adding the meaning to that node return ch = word[0] # First character # ASCII value of the first character (minus) the ASCII value of 'a'-> the first character of our ALPHABET gives us the index of the edge we have to look up. index = ord(ch) - ord('a') if self.edges[index] == None: # This implies that there's no prefix with this character yet. new_node = TrieNode() self.edges[index] = new_node self.edges[index].add(word[1:],meaning) #Adding the remaining word

Daten abrufen

 def search_word(self,word): if len(word)==0: if self.ends_here: return True else: return "Word doesn't exist in the Trie" ch = word[0] index = ord(ch)-ord('a') if self.edge[index]== None: return False else: return self.edge[index].search_word(word[1:])

Die search_wordFunktion sagt uns, ob das Wort im Trie existiert oder nicht. Da es sich bei unserem Wörterbuch um ein Wörterbuch handelt, müssen wir auch die Bedeutung abrufen. Lassen Sie uns nun eine Funktion dafür deklarieren.

 def get_meaning(self,word): if len(word)==0 : if self.ends_here: return self.meaning else: return "Word doesn't exist in the Trie" ch = word[0] index = ord(ch) - ord('a') if self.edges[index] == None: return "Word doesn't exist in the Trie" else: return self.edges[index].get_meaning(word[1:])

Daten löschen

Wenn Sie Daten löschen, müssen Sie nur die Variable ends_herein ändern False. Dadurch werden die Präfixe nicht geändert, aber dennoch werden die Bedeutung und die Existenz des Wortes aus dem Versuch gelöscht.

 def delete_word(self,word): if len(word)==0: if self.ends_here: self.ends_here = False self.meaning = None return "Deleted" else: return "Word doesn't exist in the Trie" ch = word[0] index = ord(ch) - ord('a') if self.edges[index] == None: return "Word doesn't exist in the Trie" else: return self.edges[index].delete_word(word[1:])
:Rakete:

Code ausführen