拼写纠正方法——编辑距离

编辑距离是针对二个字符串的差异程度的量化量测,量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。

这种处理一般可以简化为三种:

  • 将一个字符插入字符串;
  • 从字符串中删除一个字符;
  • 将字符串中的一个字符替换成另一个字符。

思考:cat和dod的编辑距离是3,你知道是怎么处理的吗?

Christopher D. Manning一书中,提供了一种动态规划求编辑距离的方式,他将dp抽象为以下形式,

copy/replace  | delete
——————————————————————————
insert | dp[i][j]

也就是计算dp[i][j]时,如果从左上角来,那就看成是copy或者replace;如果从上面来,就视为delete;否则左边来,就是insert。

举个例子。cats如何转化为fast呢?

  1. 将c替换为f;——得到fats
  2. 将t替换为s;——得到fass
  3. 将s替换为t。

推导出动态规划公式,

\[dp[i][j] = min( dp[i-1, j-1] + if (s_1[i] == s_2[j])\ then\ 0\ else\ 1\ if, \\ dp[i-1, j]+1, dp[i,j-1]+1)\]

cats和fast例子,对应的动态规划表格应该是这样,

  |   f a s t
——————————————
| 0 1 2 3 4
c | 1 1 2 3 4
a | 2 2 1 2 3
t | 3 3 2 2 2
s | 4 4 3 2 [3] is the edit distance

算法实现,[https://github.com/qingdujun/algorithm/blob/master/edit-distance.cpp]

  • 先初始化,dp的第一行、第一列为0~n。
int edit_distance(const string& a, const string& b) {
if (a.empty() || b.empty()) {
return a.size() ^ b.size();
}

vector<vector<int>> dp(a.size()+1, vector<int>(b.size()+1, 0));

for (int i = 0; i <= b.size(); ++i) {
dp[0][i] = i;
}

for (int i = 0; i <= a.size(); ++i) {
dp[i][0] = i;
}

for (int i = 1; i <= a.size(); ++i) {
for (int j = 1; j <= b.size(); ++j) {
dp[i][j] = std::min(dp[i-1][j-1] + (a[i-1] == b[j-1] ? 0 : 1),
std::min(dp[i-1][j]+1, dp[i][j-1]+1));
}
}

return dp.back().back();
}

References:

[1] 维基百科, 编辑距离

[2] 王斌译,《信息检索导论》2016第10次印刷