介绍
本文使用 Python 实现了前缀树，并且支持编辑距离容错的查询。文中的前缀树只存储了三个分词，格式为 (分词字符串,频率) ，如：('中海晋西园', 2)、('中海西园', 24)、('中南海', 4)，可以换成自己的文件进行数据的替换。在查询的时候要指定一个字符串和最大的容错编辑距离。
实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
class Word: def __init__(self, word, freq): self.word = word self.freq = freqclass Trie: def __init__(self): self.root = LetterNode('') self.START = 3 def insert(self, word, freq): self.root.insert(word, freq, 0) def findAll(self, query, maxDistance): suggestions = self.root.recommend(query, maxDistance, self.START) return sorted(set(suggestions), key=lambda x: x.freq)class LetterNode: def __init__(self, char): self.REMOVE = -1 self.ADD = 1 self.SAME = 0 self.CHANGE = 2 self.START = 3 self.pointers = [] self.char = char self.word = None def charIs(self, c): return self.char == c def insert(self, word, freq, depth): if ' ' in word: word = [i for i in word.split(' ')] if depth < len(word): c = word[depth].lower() for next in self.pointers: if next.charIs(c): return next.insert(word, freq, depth + 1) nextNode = LetterNode(c) self.pointers.append(nextNode) return nextNode.insert(word, freq, depth + 1) else: self.word = Word(word, freq) def recommend(self, query, movesLeft, lastAction): suggestions = [] length = len(query) if length >= 0 and movesLeft - length >= 0 and self.word: suggestions.append(self.word) if movesLeft == 0 and length > 0: for next in self.pointers: if next.charIs(query[0]): suggestions += next.recommend(query[1:], movesLeft, self.SAME) break elif movesLeft > 0: for next in self.pointers: if length > 0: if next.charIs(query[0]): suggestions += next.recommend(query[1:], movesLeft, self.SAME) else: suggestions += next.recommend(query[1:], movesLeft - 1, self.CHANGE) if lastAction != self.CHANGE and lastAction != self.REMOVE: suggestions += next.recommend(query, movesLeft - 1, self.ADD) if lastAction != self.ADD and lastAction != self.CHANGE: if length > 1 and next.charIs(query[1]): suggestions += next.recommend(query[2:], movesLeft - 1, self.REMOVE) elif length > 2 and next.charIs(query[2]) and movesLeft == 2: suggestions += next.recommend(query[3:], movesLeft - 2, self.REMOVE) else: if lastAction != self.CHANGE and lastAction != self.REMOVE: suggestions += next.recommend(query, movesLeft - 1, self.ADD) return suggestionsdef buildTrieFromFile(): trie = Trie() rows = [('中海晋西园', 2),('中海西园', 24),('中南海', 4)] for row in rows: trie.insert(row[0], int(row[1])) return triedef suggestor(trie, s, maxDistance): if ' ' in s: s = [x for x in s.split(' ')] suggestions = trie.findAll(s, maxDistance) return [str(x.word) for x in suggestions]if __name__ == "__main__": trie = buildTrieFromFile() r = suggestor(trie, '中海晋西园', 1) print(r) |
分析
结果打印：
['中海晋西园', '中海西园']
可以看出“中海晋西园”是和输入完全相同的字符串，编辑距离为 0 ，所以符合最大编辑距离为 1 的要求，直接返回。
“中海西园”是“中海晋西园”去掉“晋”字之后的结果，编辑距离为 1， 所以符合最大编辑距离为 1 的要求，直接返回。
另外，“中南海”和“中海晋西园”的编辑距离为 4 ，不符合最大编辑距离为 1 的要求，所以结果中没有出现。
参考
https://github.com/leoRoss/AutoCorrectTrie
到此这篇关于Python容错的前缀树实现中文纠错的文章就介绍到这了,更多相关Python 中文纠错内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://juejin.cn/post/6981730849070776328
