Comment utiliser l'arborescence du dictionnaire pour la correspondance de texte en Python ?

1. Qu'est-ce qu'un arbre de dictionnaire ?

L'arbre de dictionnaire (Trie), également appelé arbre de préfixes (Prefix Tree), est une structure de données en forme d'arbre. Les arborescences de dictionnaires peuvent effectuer des opérations efficaces de recherche, d'insertion et de suppression sur des chaînes. L'idée principale est d'utiliser le préfixe commun des chaînes pour réduire la complexité du temps de requête.

Dans l'arborescence du dictionnaire, chaque nœud représente le préfixe d'une chaîne. Le chemin du nœud racine au nœud feuille représente une chaîne complète. Chaque nœud sur le chemin possède un indicateur indiquant si la chaîne représentée par le nœud existe dans l'arborescence du dictionnaire.

2. Implémentation de l'arborescence du dictionnaire

En Python, vous pouvez utiliser un dictionnaire (dict) pour implémenter une arborescence de dictionnaire. Dans l'arborescence du dictionnaire, chaque nœud est un dictionnaire utilisé pour stocker le caractère suivant et son nœud correspondant. Lorsque vous devez parcourir l'arborescence du dictionnaire, il vous suffit de trouver le nœud correspondant en fonction du caractère actuel, puis d'entrer le nœud correspondant au caractère suivant, et ainsi de suite jusqu'à ce que la chaîne se termine ou ne puisse pas correspondre.

Ce qui suit est une implémentation simple d'un arbre de dictionnaire :

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

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

    def insert(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.is_word = True

    def search(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return curr.is_word

    def starts_with(self, prefix):
        curr = self.root
        for ch in prefix:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return True

3. Application de l'arbre de dictionnaire

L'arbre de dictionnaire peut être utilisé pour la correspondance de texte, comme la vérification de l'orthographe des mots, la correspondance de mots, etc. Voici un exemple simple d'utilisation d'un arbre de dictionnaire pour implémenter la vérification orthographique d'un mot :

import re

word_list = ['hello', 'world', 'python', 'teacher', 'student']

def sanitize_word(word):
    return re.sub(r'[^a-z]', '', word.lower())

def spell_check(word):
    trie = Trie()
    for w in word_list:
        trie.insert(sanitize_word(w))

    if trie.search(sanitize_word(word)):
        print('Correct spelling!')
    else:
        print('Did you mean one of the following words?')
        similar_words = get_similar_words(trie, sanitize_word(word))
        for w in similar_words:
            print(w)

def get_similar_words(trie, word, distance=1):
    similar_words = []
    for i in range(len(word)):
        for ch in range(ord('a'), ord('z')+1):
            new_word = word[:i] + chr(ch) + word[i+1:]
            if trie.search(new_word):
                similar_words.append(new_word)
    return similar_words

spell_check('helo')

Dans le code ci-dessus, nous pouvons vérifier si un mot existe dans la liste de mots via un arbre de dictionnaire. Si le mot existe, affichez « Orthographe correcte ! » ; sinon, affichez un mot similaire.

4. Résumé

L'arbre de dictionnaire est une structure de données très pratique qui peut être utilisée pour une correspondance de texte efficace. Vous pouvez utiliser des dictionnaires pour implémenter des arborescences de dictionnaires en Python, ce qui est très simple et facile à comprendre. Dans les applications pratiques, il peut être ajusté et étendu en fonction des besoins réels pour obtenir de meilleurs résultats.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!