引言
拼写纠错（Spelling Correction），又称拼写检查（Spelling Checker），往往被用于字处理软件、输入法和搜索引擎中：
| 用户输入（input） | 用户输入（correction） |
|---|---|
| 天起 | 天气 |
| theris | theirs |
| 机器学系 | 机器学习 |
最小编辑距离算法
介绍
拼写纠错中最常用的方法就是最小编辑距离算法，字符串的编辑距离，又称为Levenshtein距离，由俄罗斯的数学家Vladimir Levenshtein在1965年提出。是指利用字符操作，把字符串A转换成字符串B所需要的最少操作数。其中，字符操作包括：
主要分为三个操作
- insert a character
- delete a character
- replace a character
假设上述三种操作的代价为1，一般来说，两个字符串的编辑距离越小，则它们越相似。如果两个字符串相等，则它们的编辑距离为0，例如：用户输入therr
| 候选（candidates） | 编辑距离（edit distance） |
|---|---|
| there | 1 |
| their | 1 |
| thesis | 3 |
| theirs | 2 |
| the | 2 |
问题描述
给定两个字符串A和B，求字符串A至少经过多少步字符操作变成字符串B。
问题分析
- 首先考虑A串的第一个字符
假设存在两个字符串A和B，他们的长度分别是lenA和lenB。首先考虑第一个字符，由于他们是一样的，所以只需要计算A[2…lenA]和B[2…lenB]之间的距离即可。那么如果两个字符串的第一个字符不一样怎么办？可以考虑把第一个字符变成一样的（这里假设从A串变成B串）：- 修改A串的第一个字符成B串的第一个字符，之后仅需要计算A[2…lenA]和B[2…lenB]的距离即可
- 删除A串的第一个字符，之后仅需要计算A[2…lenA]和B[1…lenB]的距离即可
- 把B串的第一个字符插入到A串的第一个字符之前，之后仅需要计算A[1…lenA]和B[2…lenB]的距离即可
- 接下来考虑A串的第i个字符和B串的第j个字符
我们这个时候不考虑A的前i-1字符和B串的第j-1个字符。如果A串的第i个字符和B串的第j个字符相等，即A[i]=B[j]，则只需要计算A[i…lenA]和B[j…lenB]之间的距离即可。如果不想等，则：- 修改A串的第一个字符成B串的第一个字符，之后仅需要计算A[2…lenA]和B[2…lenB]的距离即可
- 删除A串的第一个字符，之后仅需要计算A[2…lenA]和B[1…lenB]的距离即可
- 把B串的第一个字符插入到A串的第一个字符之前，之后仅需要计算A[1…lenA]和B[2…lenB]的距离即可
动态规划处理
用edit[i][j]表示A串和B串的编辑距离。edit[i][j]表示A串从第0个字符开始到第i个字符和B串从第0个字符开始到第j个字符，这两个字串的编辑距离。字符串的下标从1开始。dis[0][0]表示word1和word2都为空的时候，此时他们的Edit Distance为0。很明显可以得出的，dis[0][j]就是word1为空，word2长度为j的情况，此时他们的Edit Distance为j，也就是从空，添加j个字符转换成word2的最小Edit Distance为j；同理dis[i][0]就是，word1长度为i，word2为空时，word1需要删除i个字符才能转换成空，所以转换成word2的最小Edit Distance为i。
使用表格来理解最小编辑算法
比如要计算cafe和coffee的编辑距离。cafe→caffe→coffe→coffee
取以下三个值的最小值：
- 如果最上方的字符等于最左方的字符，则为左上方的数字。否则为左上方的数字+1。
- 左方数字+1
- 上方数字+1
表格如下：
| c | o | f | f | e | e | ||
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| c | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| a | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
| f | 3 | 2 | 2 | 1 | 2 | 3 | 4 |
| e | 4 | 3 | 3 | 2 | 2 | 2 | 3 |
取最下角，即最小编辑距离为3
算法python实现
# 基于动态规划的解法
def editDistDP(str1, str2):
# m，n分别字符串str1和str2的长度
m, n = len(str1), len(str2)
# 构建二位数组来存储子问题（sub-problem)的答案
dp = [[0 for x in range(n+1)] for x in range(m+1)]
print(dp)
# 利用动态规划算法，填充数组
for i in range(m+1):
for j in range(n+1):
# 假设第一个字符串为空，则转换的代价为j (j次的插入)
if i == 0:
dp[i][j] = j
# 同样的，假设第二个字符串为空，则转换的代价为i (i次的插入)
elif j == 0:
dp[i][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
dp[i-1][j-1]) # Replace
return dp[m][n]
运行：
str1 = "cafe"
str2 = "caffee"
print(editDistDP(str1, str2))
> 3
