Python容錯的前綴樹怎么實現中文糾錯

這篇文章主要介紹了Python容錯的前綴樹怎么實現中文糾錯的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇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)

分析

結果打印：
["中海晉西園", "中海西園"]

可以看出“中海晉西園”是和輸入完全相同的字符串，編輯距離為 0 ，所以符合最大編輯距離為 1 的要求，直接返回。

“中海西園”是“中海晉西園”去掉“晉”字之后的結果，編輯距離為 1， 所以符合最大編輯距離為 1 的要求，直接返回。

另外，“中南海”和“中海晉西園”的編輯距離為 4 ，不符合最大編輯距離為 1 的要求，所以結果中沒有出現。

關于“Python容錯的前綴樹怎么實現中文糾錯”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“Python容錯的前綴樹怎么實現中文糾錯”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。