Python容錯的前綴樹實現(xiàn)中文糾錯
介紹
本文使用 Python 實現(xiàn)了前綴樹,并且支持編輯距離容錯的查詢。文中的前綴樹只存儲了三個分詞,格式為 (分詞字符串,頻率) ,如:('中海晉西園', 2)、('中海西園', 24)、('中南海', 4),可以換成自己的文件進(jìn)行數(shù)據(jù)的替換。在查詢的時候要指定一個字符串和最大的容錯編輯距離。
實現(xiàn)
class Word: def __init__(self, word, freq): self.word = word self.freq = freq class 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 suggestions def buildTrieFromFile(): trie = Trie() rows = [('中海晉西園', 2),('中海西園', 24),('中南海', 4)] for row in rows: trie.insert(row[0], int(row[1])) return trie def 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)
分析
結(jié)果打?。?br /> ['中海晉西園', '中海西園']
可以看出“中海晉西園”是和輸入完全相同的字符串,編輯距離為 0 ,所以符合最大編輯距離為 1 的要求,直接返回。
“中海西園”是“中海晉西園”去掉“晉”字之后的結(jié)果,編輯距離為 1, 所以符合最大編輯距離為 1 的要求,直接返回。
另外,“中南?!焙汀爸泻x西園”的編輯距離為 4 ,不符合最大編輯距離為 1 的要求,所以結(jié)果中沒有出現(xiàn)。
參考
https://github.com/leoRoss/AutoCorrectTrie
到此這篇關(guān)于Python容錯的前綴樹實現(xiàn)中文糾錯的文章就介紹到這了,更多相關(guān)Python 中文糾錯內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Python庫學(xué)習(xí)Tkinter制作GUI個性簽名設(shè)計軟件
Tkinter 是 Python 中的標(biāo)準(zhǔn) GUI 庫,使用 Tkinter 可以快速地創(chuàng)建 GUI 應(yīng)用程序。今天我們打算再用一個小案例,帶大家加深對Tkinter的理解2021-09-09matplotlib設(shè)置顏色、標(biāo)記、線條,讓你的圖像更加豐富(推薦)
這篇文章主要介紹了matplotlib設(shè)置顏色、標(biāo)記、線條,讓你的圖像更加豐富,本文通過實例圖文相結(jié)合給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-09-09python多進(jìn)程日志以及分布式日志的實現(xiàn)方式
這篇文章主要介紹了python多進(jìn)程日志以及分布式日志的實現(xiàn)方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-06-06