使用特里树的 Python 拼写检查器 [英] Python spell checker using a trie

问题描述

我正在尝试使用 trie 数据结构实现拼写检查器.我目前对 Node 有以下大纲:

I am trying to implement a spell checker using a trie data structure. I currently have the following outline for a Node:

class Node:
    def __init__(self):
        self.next = {}
        self.word_marker = False

    def add_item(self, string):
        #if the length of the string is 0 then return. When the end of the word 
        #comes set the word_marker to true
        if len(string) == 0:
            self.word_marker = True
            return
        #set the key to the first letter of the string and reformat the string to reflect the first letter taken out
        #ultimately going to store the letters for each node as the key
        key = string[0]
        string = string[1:]

        #if there is a key in the dictionary, then recursively call add_item with new string
        if key in self.next:
            self.next[key].add_item(string)

        else:
            node = Node()
            self.next[key] = node
            node.add_item(string)

我接下来要做的是编写函数来搜索 string，然后返回建议的拼写.(def正确(self, string)).我将如何通过这个尝试来实现搜索?假设我已经通过定义一个根节点 root，然后对列表中的每个单词使用 add_item 来将单词列表添加到树中.

The next thing that I want to do is write the function to search for a string and then return a suggested spelling. (def correct(self, string)). How would I go through this trie to implement the search? Assume that I already added a list of words to the trie by defining a root node root, then using add_item for each of the words in the list.

推荐答案

如果您还没有，您可能想查看 Norvig 的 '如何编写拼写校正器'

If you haven't already, you might want to check out Norvig's 'How to Write a Spelling Corrector'

这篇关于使用特里树的 Python 拼写检查器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！