Detaillierte Erläuterung der Strukturtechniken zur Implementierung des Wörterbuchbaum-Trie mithilfe von Python-Code

Der Wörterbuchbaum (Trie) kann einige String->Wert-Korrespondenzen speichern. Im Grunde hat es die gleiche Funktion wie Javas HashMap, bei der es sich um eine Schlüssel-Wert-Zuordnung handelt, mit der Ausnahme, dass der Schlüssel von Trie nur eine Zeichenfolge sein kann.

Die Kraft von Trie liegt in seiner zeitlichen Komplexität. Die Einfügungs- und Abfragezeitkomplexität beträgt jeweils O(k), wobei k die Länge des Schlüssels ist, unabhängig davon, wie viele Elemente in Trie gespeichert sind. Es wird behauptet, dass die Hash-Tabelle O (1) ist, aber bei der Berechnung des Hashs wird sie definitiv O (k) sein, und es gibt auch Probleme wie Kollisionen. Der Nachteil von Trie besteht darin, dass es sehr viel Speicherplatz verbraucht.
Was die Implementierung des Trie-Baums betrifft, können Sie Arrays verwenden oder Zeiger dynamisch zuweisen. Als ich die Frage beantwortete, habe ich der Einfachheit halber Arrays verwendet und den Speicherplatz statisch zugewiesen.
Der Trie-Baum, auch Wortsuchbaum oder Schlüsselbaum genannt, ist eine Baumstruktur und eine Variante des Hash-Baums. Typische Anwendungen sind das Zählen und Sortieren einer großen Anzahl von Zeichenfolgen (aber nicht auf Zeichenfolgen beschränkt), daher werden sie häufig von Suchmaschinensystemen für Statistiken zur Worthäufigkeit von Texten verwendet. Seine Vorteile sind: Es minimiert unnötige Zeichenfolgenvergleiche und bietet eine höhere Abfrageeffizienz als Hash-Tabellen.
Die Kernidee von Trie besteht darin, Raum gegen Zeit zu tauschen. Nutzen Sie das gemeinsame Präfix von Zeichenfolgen, um den Zeitaufwand für Abfragen zu reduzieren und die Effizienz zu verbessern.
Jedes Wort im Trie-Baum wird zeichenweise gespeichert, und Wörter mit demselben Präfix teilen sich Präfixknoten.
Sie können sehen, dass jeder Pfad ein Wort im Baum speichert /ten/inn diese Wörter.

Die Grundeigenschaften des Trie-Baums können wie folgt zusammengefasst werden:
(1) Der Wurzelknoten enthält keine Zeichen, außer dem Wurzelknoten. Jeder Knoten enthält nur ein Zeichen.
(2) Vom Wurzelknoten bis zu einem bestimmten Knoten werden die auf dem Pfad übergebenen Zeichen verbunden, um die dem Knoten entsprechende Zeichenfolge zu bilden.
(3) Alle untergeordneten Knoten jedes Knotens enthalten unterschiedliche Zeichenfolgen.

Eigenschaften
(1) Der Wurzelknoten enthält keine Zeichen, und jeder Knoten außer dem Wurzelknoten enthält nur ein Zeichen.
(2) Vom Wurzelknoten bis zu einem bestimmten Knoten werden die auf dem Pfad übergebenen Zeichen verbunden, um die dem Knoten entsprechende Zeichenfolge zu bilden.
(3) Alle untergeordneten Knoten jedes Knotens enthalten unterschiedliche Zeichenfolgen.

Grundidee (am Beispiel des Buchstabenbaums):
1. Einfügungsprozess
Beginnen Sie für ein Wort an der Wurzel und folgen Sie dem Baum, der jedem Buchstaben von entspricht Das Wort Der Knoten verzweigt sich nach unten, bis das Wort durchlaufen wird, und der letzte Knoten ist rot markiert, was darauf hinweist, dass das Wort in den Trie-Baum eingefügt wurde.
2. Abfrageprozess
Durchlaufen Sie auf ähnliche Weise den Trie-Baum in alphabetischer Reihenfolge der Wörter, beginnend mit der Wurzel. Sobald festgestellt wird, dass keine Knotenmarkierung vorhanden ist, oder die Wortdurchquerung abgeschlossen ist aber der letzte Knoten ist nicht vorhanden. Wenn er rot markiert ist, bedeutet dies, dass das Wort nicht existiert. Wenn der letzte Knoten rot markiert ist, bedeutet dies, dass das Wort existiert.

Anwendung
(1) Worthäufigkeitsstatistik
Platz sparen als Hash direkt verwenden
(2) Suchaufforderung
Präfix eingeben Bei Aufforderung werden Wörter, die
(3) gebildet werden können, als Hilfsstrukturen
wie Suffixbäume, AC-Automaten usw. implementiert.

>Obwohl Python Da es keine Zeiger gibt, können verschachtelte Wörterbücher zum Implementieren von Baumstrukturen verwendet werden. Für Nicht-ASCII-Wörter wird die Unicode-Kodierung zum Einfügen und Suchen verwendet Informationen zu den Strukturtechniken zur Implementierung eines Wörterbuchbaum-Trie mithilfe von Python-Code finden Sie auf der chinesischen PHP-Website!

#coding=utf-8 
class Trie: 
  root = {} 
  END = '/' 
  def add(self, word): 
    #从根节点遍历单词,char by char,如果不存在则新增,最后加上一个单词结束标志 
    node = self.root 
    for c in word: 
      node=node.setdefault(c,{}) 
    node[self.END] = None 
 
  def find(self, word): 
    node = self.root 
    for c in word: 
      if c not in node: 
        return False 
      node = node[c] 
    return self.END in node