方案一：

    1. #!/usr/bin python3
    2. # -*- encoding: utf-8 -*-
    3. '''
    4. @File    :   charcorrect.py
    5. @Time    :   2020/07/28 11:27:03
    6. @Author  :   陈培杞
    7. @Version :   1.0
    8. @docs    :  
    9.         原始数据集样本格式
    10.             * wp_2gram.txt:
    11.                 1 the git
    12.                 2 in the
    14.             * eml.txt
    15.                 Héllo I'm a programmér who crackéd your émail account and dévicé about
    17.         过程：
    18.             1. 将原始数据结构化为dict —— 按字符串长度进行分桶处理。{2:['aa','bb'], 8:['isthethe','aboutyou']}
    19.             2. 将字符转为ASCII码
    20.             3. 处理成 faiss 模块的输入形式，分桶搜索
    21. '''
    23. from pathlib import Path
    24. project_path = Path(__file__).parent.resolve()
    26. import re
    27. import ast
    28. import json
    29. import numpy as np
    30. from collections import defaultdict
    32. class TrieTree(object):
    33.     """
    34.         用于模糊搜索
    35.     """
    37.     def __init__(self):
    38.         self.root={}
    39.         self.word_end = -1
    41.     def add(self,word):
    42.         nownode=self.root
    43.         for char in word:
    44.             if char not in nownode:
    45.                 nownode[char] = {}
    46.             nownode = nownode[char]
    47.         nownode[self.word_end] = True
    49.     def search(self, word):
    50.         nownode = self.root
    51.         for char in word:
    52.             if  char not in nownode:
    53.                 return False
    54.             nownode = nownode[char]
    56.         if self.word_end not in nownode:
    57.             return False
    59.         return True 
    61.     def fuzzyMatch(self, tree, word):
    62.         nowNode = tree
    63.         matchWord = ''
    64.         matchWordList=[]
    65.         for i,char in enumerate(word):
    66.             if char  in nowNode:
    67.                 matchWord += char
    68.                 nowNode = nowNode[char]
    69.             else:
    70.                 if ord(char) <= 122 :  # 既不在树中，也不是通配符，返回空串
    71.                     return ['']
    72.                 else: # 通配符处理
    73.                     for key in nowNode.keys():
    74.                         nextNodes = nowNode[key]
    75.                         if key == self.word_end:
    76.                             return ['']
    77.                         NextMatchWordList = self.fuzzyMatch(nextNodes, word[i+1:])                        
    78.                         matchWordList += [ matchWord + key + chars for chars in NextMatchWordList]
    81.         if matchWordList :
    82.             return matchWordList
    83.         else:
    84.             return [matchWord]
    87.     def getTree(self):
    88.         return self.root
    95. def calculateSimilarity( searchDict:dict, charlength=5):
    96.     key = charlength
    97.     dict_eml  = getProcessedData(f"{EmlSaveFile}_{charlength}")
    98.     dict_wiki = getProcessedData(f"{WikiSaveFile}_{charlength}")
    100.     # trie tree 检索
    101.     mytree = TrieTree()
    102.     for word in dict_wiki[key]:
    103.         mytree.add(word)
    105.     for word in dict_eml[key]:
    106.         matchResult = mytree.fuzzyMatch(mytree.getTree(), word)
    107.         matchResult = [ i for i in matchResult if len(i)==len(word) ]
    108.         searchDict[word] = list(set(matchResult))
    112. if __name__=='__main__':
    113.         searchDict = dict()
    114.         calculateSimilarity(searchDict)

    方案二：

    1. import collections
    2. class TrieNode:
    3.     # Initialize your data structure here.
    4.     def __init__(self):
    5.         self.children = collections.defaultdict(TrieNode)
    6.         self.is_word = False
    8. class Trie:
    9.     def __init__(self):
    10.         self.root = TrieNode()
    12.     def insert(self, word):
    14.         current = self.root
    15.         for letter in word:
    16.             current = current.children[letter]
    17.         current.is_word = True
    19.     def search(self, word):
    20.         current = self.root
    21.         for letter in word:
    22.             current = current.children.get(letter)
    24.             if current is None:
    25.                 return False
    26.         return current.is_word
    28.     def startsWith(self, prefix):
    29.         current = self.root
    30.         for letter in prefix:
    31.             current = current.children.get(letter)
    32.             if current is None:
    33.                 return False
    34.         return True
    37.     def enumerateMatch(self, word, space="_", backward=False):
    38.         matched = []
    39.         ## while len(word) > 1 does not keep character itself, while word keed character itself
    40.         while len(word) > 1:
    41.             if self.search(word):
    42.                 matched.append(space.join(word[:]))
    43.             del word[-1]
    44.         return matched