第一种方法

规定词典，如果词不在词典中判定为错词，遍历词典所有词，编辑距离方法纠正

时间复杂度 —- $O(V) * edit(nums)$ —- 词典大小 * 编辑距离计算次数

第二种方法

基于生成的方法，找到错词后，利用编辑距离生成 成本为1，2的所有词，进行过滤（怎么过滤？）返回结果

时间复杂度 —- $O(10^5)$左右

过滤方法 利用bayes

​ $p(x,y) = p(x|y)·p(y) = p(y|x)·p(x) = p(x|y) = p(y|x)·p(x)/p(y)$

​ apple —- appl applr app app appl …

​ app = 2/5 appl = 2/5 applr = 1/5

​ 取argmax

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 基于动态规划的编辑距离
def edit_dist(str1, str2):
  
  # m, n 分别字符串str1，str2的长度
  m, n = len(str1), len(str2)
  
  # 构建二维数组来储存子问题
  dp = [[0 for x in range(n+1)] for x in range(m+1)]
  
  # 利用动态规划算法，填充数据
  for i in range(m+1):
    for j in range(n+1):
      # 假设第一个字符串为空，则转换的代价为1（j次的插入）
      if i == 0:
        dp[i][j] = j
      elif j == 0:
        dp[j][j] = i
       # 如果最后一个字符相等，就不会产生代价
      elif	str1[i-1] == str2[j-1]:
        dp[i][j] = dp[i-1][j-1]
      else:
        dp[i][j] = 1 + min(dp[i][j-1],		# insert
                           dp[i-1][j], 		# remove
                           do[i-1][j-1])	# replace
	return dp[m][n]