Python容錯的前綴樹實現中文糾錯
更新時間：2021年07月07日 15:31:27 作者：王大呀呀
本文使用 Python 實現了前綴樹，并且支持編輯距離容錯的查詢。文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
介紹
本文使用 Python 實現了前綴樹，并且支持編輯距離容錯的查詢。文中的前綴樹只存儲了三個分詞，格式為 (分詞字符串,頻率) ，如：('中海晉西園', 2)、('中海西園', 24)、('中南海', 4)，可以換成自己的文件進行數據的替換。在查詢的時候要指定一個字符串和最大的容錯編輯距離。
實現
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)
分析
結果打?。?br /> ['中海晉西園', '中海西園']
可以看出“中海晉西園”是和輸入完全相同的字符串，編輯距離為 0 ，所以符合最大編輯距離為 1 的要求，直接返回。
“中海西園”是“中海晉西園”去掉“晉”字之后的結果，編輯距離為 1， 所以符合最大編輯距離為 1 的要求，直接返回。
另外，“中南?！焙汀爸泻x西園”的編輯距離為 4 ，不符合最大編輯距離為 1 的要求，所以結果中沒有出現。
參考
https://github.com/leoRoss/AutoCorrectTrie
到此這篇關于Python容錯的前綴樹實現中文糾錯的文章就介紹到這了,更多相關Python 中文糾錯內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
相關文章
中秋節(jié)是中國傳統(tǒng)的重要節(jié)日之一,起源于嫦娥奔月的神話故事,在中秋節(jié)這個特殊的日子里,人們不僅會欣賞明亮的月亮和嫦娥奔月的美麗故事,還會舉行一些慶?；顒?接下來,我們使用Pygame制作“嫦娥奔月”小游戲,感興趣的朋友可以自己動手試一試2023-09-09
這篇文章主要介紹了序列化Python對象的方法，文中講解非常細致，代碼幫助大家更好的理解和學習，感興趣的朋友可以了解下2020-08-08
這篇文章主要介紹了Python實現繪制雙柱狀圖并顯示數值功能,涉及Python數值運算及基于matplotlib的圖形繪制相關操作技巧,需要的朋友可以參考下2018-06-06
這篇文章主要介紹了python用10行代碼實現對黃色圖片的檢測功能,涉及Python基于圖片庫PIL對圖片的檢測技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-08-08
這篇文章主要為大家詳細介紹了OpenCV中直方圖、掩膜、直方圖均衡化詳細介紹及代碼的實現，文中的示例代碼講解詳細，需要的可以參考一下2022-11-11
這篇文章主要介紹了一種Python工具的License授權機制，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-06-06
Python Pygame實戰(zhàn)之憤怒的小鳥游戲實現
《憤怒的小鳥》其實活得還不錯，盡管我們一直在嘲笑它的IP帝國夢做得太大。但要知道，把休閑益智游戲的生意做到這個份上的，恐怕也就獨此一家了。本文將利用Pygame實現這一游戲，需要的可以參考一下2022-04-04
在本篇文章中我們給大家整理了關于python實現文件的備份的詳細流程步驟，有興趣的朋友們學習下。2019-06-06
這篇文章主要介紹了python生成指定尺寸縮略圖的示例,需要的朋友可以參考下2014-05-05
這篇文章主要為大家詳細介紹了python實現電子詞典，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2014-01-01