编辑距离

应用场景

• Elastic中项目要用的真实例子: https://www.elastic.co/blog/found-fuzzy-search 模糊（Fuzzy）搜索以及拼写错误（Spell checker）
• OJ例子: https://leetcode.com/problems/edit-distance/
• 更难的例子: https://leetcode.com/problems/regular-expression-matching/
• Java业务: 通过EditDistance反射找到Bean（使用Common库实现）

理论教程

详见这个胶片 https://web.stanford.edu/class/cs124/lec/med.pdf

实现

本处实现是参考算法书中最通用的动态规划实现(其中replace复杂度为1)，与Elastic/Lucene等专业实现肯定还是有很大性能区别。还有值得注意的是，编辑距离不要求枚举所有的路线图，而只要求计算结果。如果需要保存路线，那么就相当于实现了一份Diff了

// https://leetcode.com/problems/edit-distance/

相比Fibonacci中使用Map作为缓存，由于EditDistance有两个入参，因此需要一个二维数组(cost array)来实现记忆化

cost[m][n]表示缓存了字符串word1前m个字符串与word2前n个字符串，从word1到word2的编辑距离

// 前N个含有0，因此需要加一
int[][] cost = new int[word1.length+1][word2.length+1];

比如现在有两个字符串，分别是 abcd 与 ccd，通过大脑计算显然可以看出需要删1换1，最终是2，我们现在用记忆化实现一下，我们将数组维护为一个Table，

首先完成边界起始迭代，由于是纯ADD/DEL操作，比如cost[3][0]表示将abc删成""，操作数当然是3

这一部分可以用如下Java代码实现

// for word1 delete to word2
for (int i = 0; i< word1.length+1;i++){
  cost[i][0] = i;
}
// for word1 add to word2
for (int i = 0; i< word2.length+1;i++){
  cost[0][i] = i;
}

然后我们就可以基于预知条件，做一套从它的上面，左边与左对角线的迁移状态机，在上面的预制条件找最优解了

比如求值

• cost[1][1]=distance('a','c')
  • REPLACE: 由于a不等于c，因此成本是1
  • delete_first: 先计算distance('','c') ，再计算 distance('','c') -> distance('a','c')，转换成本是1
  • delele_second: 先计算distance('a','') ，再计算 distance('a','') -> distance('a','c')，转换成本是1
• cost[1][2]=distance('a','cc')
  • REPLACE: 由于a不等于c，因此成本是1
  • delete_first: 先计算distance('','cc')，再计算 distance('','cc') -> distance('a','cc')，转换成本是1
  • delele_second: 先计算distance('a','c') ，再计算 distance('a','c') -> distance('a','cc')，转换成本是1

这里代码如下

// calculate every transformation cost
for (int i = 1; i < len1 + 1; i++) {
  char c1 = word1.charAt(i - 1);
  for (int j = 1; j < len2 + 1; j++) {
    int swapCost = (c1 == word2.charAt(j - 1) ? 0 : 1);
    int delete_both_to_normal = cost[i - 1][j - 1] + swapCost;
    // 网上有很多用add作为命名，但是正如上文所写，状态转移最好命名长一点，避免歧义
    int delete_first_to_normal = cost[i][j - 1] + 1;
    int delele_second_to_normal = cost[i - 1][j] + 1;
    cost[i][j] = Math.min(
      Math.min(delete_first_to_normal, delele_second_to_normal), 
      delete_both_to_normal
    );
  }
}
return [i][j];

白板注意事项

• 不要写过长代码(eg: Math.min)，防止括号中加一位置计算错误，难以定位
• 二维数组尽量直接操作index，不要用arr.length
• string的length方法有括号