Explication détaillée des techniques structurelles d'implémentation de l'arbre de dictionnaire Trie à l'aide du code Python

L'arbre de dictionnaire (Trie) peut enregistrer certaines correspondances chaîne->valeur. Fondamentalement, il a la même fonction que le HashMap de Java, qui est un mappage clé-valeur, sauf que la clé de Trie ne peut être qu'une chaîne.

La puissance de Trie réside dans sa complexité temporelle. Sa complexité en matière de temps d'insertion et de requête est toutes deux O(k), où k est la longueur de la clé, quel que soit le nombre d'éléments enregistrés dans Trie. La table de hachage est censée être O(1), mais lors du calcul du hachage, elle sera certainement O(k), et il y a aussi des problèmes tels que les collisions. L'inconvénient de Trie est qu'il consomme très beaucoup d'espace.
En ce qui concerne l'implémentation de l'arbre Trie, vous pouvez utiliser des tableaux ou allouer dynamiquement des pointeurs. Lorsque j'ai posé la question, j'ai utilisé des tableaux pour plus de commodité et un espace alloué statiquement.
L'arbre de Trie, également connu sous le nom d'arbre de recherche de mots ou d'arbre de clés, est une structure arborescente et une variante de l'arbre de hachage. Les applications typiques sont le comptage et le tri d'un grand nombre de chaînes (mais sans s'y limiter), elles sont donc souvent utilisées par les systèmes de moteurs de recherche pour les statistiques de fréquence des mots de texte. Ses avantages sont les suivants : il minimise les comparaisons de chaînes inutiles et offre une efficacité de requête plus élevée que les tables de hachage.
L'idée centrale de Trie est d'échanger de l'espace contre du temps. Utilisez le préfixe commun des chaînes pour réduire le temps de requête et améliorer l'efficacité.
Chaque mot de l'arbre Trie est stocké via la méthode caractère par caractère, et les mots avec le même préfixe partagent des nœuds de préfixe
Vous pouvez voir que chaque chemin forme un mot. /ten/inn ces mots.

Les propriétés de base de l'arbre de Trie peuvent être résumées comme suit :
(1) Le nœud racine ne contient pas de caractères, à l'exception du nœud racine. chaque nœud ne contient qu'un seul caractère.
(2) Du nœud racine à un certain nœud, les caractères passant sur le chemin sont connectés pour former la chaîne correspondant au nœud.
(3) Tous les nœuds enfants de chaque nœud contiennent des chaînes différentes.

Propriétés
(1) Le nœud racine ne contient pas de caractères, et chaque nœud à l'exception du nœud racine ne contient qu'un seul caractère.
(2) Du nœud racine à un certain nœud, les caractères passant sur le chemin sont connectés pour former la chaîne correspondant au nœud.
(3) Tous les nœuds enfants de chaque nœud contiennent des chaînes différentes.

Idée de base (en prenant l'arbre des lettres comme exemple) :
1. Processus d'insertion
Pour un mot, partez de la racine et suivez l'arbre correspondant à chaque lettre de le mot Le nœud se ramifie vers le bas jusqu'à ce que le mot soit parcouru, et le dernier nœud est marqué en rouge, indiquant que le mot a été inséré dans l'arbre de Trie.
2. Processus de requête
De même, parcourez l'arbre de tri vers le bas dans l'ordre alphabétique des mots en commençant par la racine une fois qu'il est constaté qu'une marque de nœud n'existe pas ou que la traversée des mots est terminée. mais le dernier nœud ne l'est pas. S'il est marqué en rouge, cela signifie que le mot n'existe pas. Si le dernier nœud est marqué en rouge, cela signifie que le mot existe.

Application
(1) Statistiques de fréquence des mots
Économisez de l'espace en utilisant directement le hachage
(2) Invite de recherche
Entrez le préfixe Lorsque vous y êtes invité, les mots qui peuvent être formés
(3) sont implémentés en tant que structures auxiliaires
telles que des arbres de suffixes, des automates AC, etc.

> Bien que Python n'a pas de pointeurs, des dictionnaires imbriqués peuvent être utilisés pour implémenter des structures arborescentes. Pour les mots non-ascii, le codage Unicode est utilisé pour l'insertion et la recherche

Plus de détails Pour les articles connexes. sur les techniques structurelles d'implémentation d'un arbre de dictionnaire Trie en utilisant du code Python, veuillez faire attention au site Web PHP chinois !

#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