SymSpell：对称删除拼写纠错

<img src="http://network.jancsitech.net:9000/pageflex-ai/images/general/202509/1758380307122154036.svg" alt="包含 "bid" 和 "buy" 的前缀树" />

1from typing import Tuple
2
3
4class Trie(object):
5    """
6    Trie节点的实现
7    """
8    
9    def __init__(self, char: str):
10        self.char = char
11        self.children = []
12        # 是否为单词的最后一个字符
13        self.word_finished = False
14        # 该字符在插入过程中出现的次数
15        self.counter = 1
16    
17
18def add(root, word: str):
19    """
20    向Trie结构中添加一个单词
21    """
22    node = root
23    for char in word:
24        found_in_child = False
25        # 在当前节点的子节点中搜索该字符
26        for child in node.children:
27            if child.char == char:
28                # 找到了该字符，将计数器加1
29                ### 此处实现
30                # 将节点指向包含该字符的子节点
31                node = child
32                found_in_child = True
33                break
34        # 未找到该字符，则创建一个新的子节点
35        if not found_in_child:
36            ### 此处实现
37            # 然后将节点指向新创建的子节点
38            node = new_node
39    # 所有字符处理完毕，标记为单词结尾
40    node.word_finished = True
41
42
43def find_prefix(root, prefix: str) -> Tuple[bool, int]:
44    """
45    检查并返回：
46      1. 给定前缀是否存在于已添加的任何单词中
47      2. 如果存在，有多少个单词具有该前缀
48    """
49    node = root
50    # 如果根节点没有子节点，说明Trie为空，直接返回False
51    if not root.children:
52        return False, 0
53    for char in prefix:
54        char_not_found = True
55        # 遍历当前节点的所有子节点
56        for child in node.children:
57            if child.char == char:
58                # 找到对应字符
59                char_not_found = False
60                # 将node更新为对应的子节点并跳出循环
61                ### 此处实现
62        # 如果该字符未找到，直接返回False
63        if char_not_found:
64            return False, 0
65    # 成功匹配前缀，返回True以及最后一个节点的计数器值
66    # 计数器表示有多少个单词共享此前缀
67    return # 此处实现
68
69if __name__ == "__main__":
70    # 创建一个简单的树结构
71    # 字典中包含两个单词
72    root = Trie('*')
73    add(root, "hackathon")
74    add(root, 'hack')

查看解答

解答

以下是上述功能的完整实现：

Trie 实现

1from typing import Tuple
2
3
4class Trie(object):
5    """
6    Trie节点的实现
7    """
8    
9    def __init__(self, char: str):
10        self.char = char
11        self.children = []
12        # 是否为单词的最后一个字符
13        self.word_finished = False
14        # 该字符在插入过程中出现的次数
15        self.counter = 1
16    
17
18def add(root, word: str):
19    """
20    向Trie结构中添加一个单词
21    """
22    node = root
23    for char in word:
24        found_in_child = False
25        # 在当前节点的子节点中搜索该字符
26        for child in node.children:
27            if child.char == char:
28                # 找到了该字符，将计数器加1，表示又有一个单词包含该字符
29                child.counter += 1
30                # 将当前节点指向该子节点
31                node = child
32                found_in_child = True
33                break
34        # 未找到该字符，则新建一个节点
35        if not found_in_child:
36            new_node = Trie(char)
37            node.children.append(new_node)
38            # 将当前节点指向新创建的子节点
39            node = new_node
40    # 单词添加完成，标记最后一个字符节点为单词结尾
41    node.word_finished = True
42
43
44def find_prefix(root, prefix: str) -> Tuple[bool, int]:
45    """
46    检查并返回：
47      1. 给定前缀是否存在于已添加的任何单词中
48      2. 如果存在，有多少个单词具有该前缀
49    """
50    node = root
51    # 如果根节点没有子节点，说明Trie为空
52    if not root.children:
53        return False, 0
54    for char in prefix:
55        char_not_found = True
56        # 遍历当前节点的所有子节点
57        for child in node.children:
58            if child.char == char:
59                # 找到对应字符
60                char_not_found = False
61                # 更新当前节点为该子节点，并跳出循环
62                node = child
63                break
64        # 若未找到该字符，返回False
65        if char_not_found:
66            return False, 0
67    # 成功匹配前缀，返回True和最后一个节点的counter值
68    # counter表示有多少个单词共享此前缀
69    return True, node.counter
70
71if __name__ == "__main__":
72    # 创建一个简单的Trie
73    # 包含两个单词："hackathon" 和 "hack"
74    root = Trie('*')
75    add(root, "hackathon")
76    add(root, 'hack')

让我们理解上述代码的实现细节：

• 第30行：我们将child.counter加1，用于记录又有另一个单词包含了相同的字符。这同时也表明当前节点的子节点中存在一个具有相同字符的子节点。

• 第37–38行：如果在当前节点的子节点中未找到该字符，则为该字符创建一个new_node，并将其添加到当前节点的子节点列表中。

• 第64–65行：当找到匹配字符时，将node更新为对应的child节点，并跳出循环。

• 第72行：最后返回True和node的counter值，表示输入的前缀存在，并且有counter个单词共享该前缀。