How to use dictionary tree for text matching in Python?

1. What is a dictionary tree

Dictionary tree (Trie), also called prefix tree (Prefix Tree), is a tree data structure. Dictionary trees can perform efficient search, insertion, and deletion operations on strings. The core idea is to use the common prefix of strings to reduce query time complexity.

In the dictionary tree, each node represents the prefix of a string. The path from the root node to the leaf node represents a complete string. Each node on the path has a flag indicating whether the string represented by the node exists in the dictionary tree.

2. Implementation of dictionary tree

In Python, you can use a dictionary (dict) to implement a dictionary tree. In the dictionary tree, each node is a dictionary used to store the next character and its corresponding node. When you need to traverse the dictionary tree, you only need to find the corresponding node based on the current character, and then enter the node corresponding to the next character, and so on until the string ends or cannot be matched.

The following is a simple dictionary tree implementation:

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 of dictionary tree

Dictionary tree can be used for text matching, such as word spelling check, word matching, etc. . The following is a simple example of using a dictionary tree to implement word spell checking:

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')

In the above code, we can check whether a word exists in the word list through a dictionary tree. If the word exists, output "Correct spelling!"; otherwise, output a similar word.

4. Summary

The dictionary tree is a very practical data structure that can be used for efficient text matching. You can use dictionaries to implement dictionary trees in Python, which is very simple and easy to understand. In practical applications, it can be adjusted and expanded according to actual needs to achieve better results.

The above is the detailed content of How to use dictionary tree for text matching in Python?. For more information, please follow other related articles on the PHP Chinese website!