Python容错的前缀树怎么实现中文纠错
Python容错的前缀树怎么实现中文纠错
这篇文章主要介绍了Python容错的前缀树怎么实现中文纠错的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇Python容错的前缀树怎么实现中文纠错文章都会有所收获，下面我们一起来看看吧。
介绍
本文使用 Python 实现了前缀树，并且支持编辑距离容错的查询。文中的前缀树只存储了三个分词，格式为 (分词字符串,频率) ，如：("中海晋西园", 2)、("中海西园", 24)、("中南海", 4)，可以换成自己的文件进行数据的替换。在查询的时候要指定一个字符串和最大的容错编辑距离。
实现
classWord:def__init__(self,word,freq):self.word=wordself.freq=freqclassTrie:def__init__(self):self.root=LetterNode("")self.START=3definsert(self,word,freq):self.root.insert(word,freq,0)deffindAll(self,query,maxDistance):suggestions=self.root.recommend(query,maxDistance,self.START)returnsorted(set(suggestions),key=lambdax:x.freq)classLetterNode:def__init__(self,char):self.REMOVE=-1self.ADD=1self.SAME=0self.CHANGE=2self.START=3self.pointers=[]self.char=charself.word=NonedefcharIs(self,c):returnself.char==cdefinsert(self,word,freq,depth):if""inword:word=[iforiinword.split("")]ifdepth<len(word):c=word[depth].lower()fornextinself.pointers:ifnext.charIs(c):returnnext.insert(word,freq,depth+1)nextNode=LetterNode(c)self.pointers.append(nextNode)returnnextNode.insert(word,freq,depth+1)else:self.word=Word(word,freq)defrecommend(self,query,movesLeft,lastAction):suggestions=[]length=len(query)iflength>=0andmovesLeft-length>=0andself.word:suggestions.append(self.word)ifmovesLeft==0andlength>0:fornextinself.pointers:ifnext.charIs(query[0]):suggestions+=next.recommend(query[1:],movesLeft,self.SAME)breakelifmovesLeft>0:fornextinself.pointers:iflength>0:ifnext.charIs(query[0]):suggestions+=next.recommend(query[1:],movesLeft,self.SAME)else:suggestions+=next.recommend(query[1:],movesLeft-1,self.CHANGE)iflastAction!=self.CHANGEandlastAction!=self.REMOVE:suggestions+=next.recommend(query,movesLeft-1,self.ADD)iflastAction!=self.ADDandlastAction!=self.CHANGE:iflength>1andnext.charIs(query[1]):suggestions+=next.recommend(query[2:],movesLeft-1,self.REMOVE)eliflength>2andnext.charIs(query[2])andmovesLeft==2:suggestions+=next.recommend(query[3:],movesLeft-2,self.REMOVE)else:iflastAction!=self.CHANGEandlastAction!=self.REMOVE:suggestions+=next.recommend(query,movesLeft-1,self.ADD)returnsuggestionsdefbuildTrieFromFile():trie=Trie()rows=[("中海晋西园",2),("中海西园",24),("中南海",4)]forrowinrows:trie.insert(row[0],int(row[1]))returntriedefsuggestor(trie,s,maxDistance):if""ins:s=[xforxins.split("")]suggestions=trie.findAll(s,maxDistance)return[str(x.word)forxinsuggestions]if__name__=="__main__":trie=buildTrieFromFile()r=suggestor(trie,"中海晋西园",1)print(r)
分析
结果打印：
["中海晋西园", "中海西园"]
可以看出“中海晋西园”是和输入完全相同的字符串，编辑距离为 0 ，所以符合最大编辑距离为 1 的要求，直接返回。
“中海西园”是“中海晋西园”去掉“晋”字之后的结果，编辑距离为 1， 所以符合最大编辑距离为 1 的要求，直接返回。
另外，“中南海”和“中海晋西园”的编辑距离为 4 ，不符合最大编辑距离为 1 的要求，所以结果中没有出现。
关于“Python容错的前缀树怎么实现中文纠错”这篇文章的内容就介绍到这里，感谢各位的阅读！相信大家对“Python容错的前缀树怎么实现中文纠错”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注恰卡编程网行业资讯频道。
