TOC
在我们的日常生活中，必然使用过搜索引擎提供的联想查询功能
可以看到，尽管我们打错了单词，但是他仍然为我们提供了搜索建议，那么这是如何实现的呢。
编辑距离(莱文斯坦距离)
编辑距离是针对二个字符串（例如英文字）的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。编辑距离可以用在自然语言处理中，例如拼写检查可以根据一个拼错的字和其他正确的字的编辑距离，判断哪一个（或哪几个）是比较可能的字。DNA也可以视为用A、C、G和T组成的字符串，因此编辑距离也用在生物信息学中，判断二个DNA的类似程度。Unix 下的 diff 及 patch 即是利用编辑距离来进行文本编辑对比的例子。
解释
编辑距离的核心概念非常简单，想象一下我们能够对字符串进行编辑，并且有三种可选操作，分别是
- 替换 将一个字符替换成另一个字符
- 插入 在字符串的某处插入一个新字符
- 删除 删除某个位置的字符
所以，编辑距离的概念就是， 把字符串A经过X次编辑变成字符串B ， 这里的X就是A与B之间的编辑距离，编辑距离是拉丁文单词之间衡量相似度非常有效的手段。
状态转移
借用一下网上的图片
我们把最初的状态设置为 AB两个空字符串，不断引入新的子串，你可以认为大致的计算模型是从空字符串到完整子串不断叠加的过程。比如 字符串 linux 可以分为 a0(空) a1(l) a2(li) a3(lin) a4(linu) a5(linux)
首先最初的状态，a0 对比 b0 两者都是空串，所以编辑距离初始值为0。
接下来我们考虑不断插入的情况 串A也就是行保持不变 b开始前进， 到达b1，很显然想要从空字符串到达b1(m),使用插入操作，编辑距离+1 ，后面的b2 ~ b5 自然也可以通过不断的读取前一个最短编辑距离不断+1计算出来。计算a1到a5当然也是相同的。
替换的情况，a1 b1都是空串 如果a2 b2字符相同 那么编辑距离保持不变，如果不相同，自然可以使用替换操作变更 所以编辑距离需要+1
接下来自然就是不断的进行填表格计算，每个项都需要计算以上三种情况(第一行和第一列自然除外)，并且取最小值。
完整填写后 表格应该就变成了这样
上面的三种操作从方向和具体的编码上，可以转化为三种操作
- 访问Top 也就是[i,j-1] 用插入操作 编辑距离必定+1
- 访问 left 也就是[i-1,j] 用插入操作 编辑距离必定+1
- 访问 lefttop [i-1][j-1] 尝试用替换操作，如果这时候的子串相等 编辑距离+0 否则 +1
所以其实本质就是不断尝试leftTop的基础上判断子串是否相同，如果相等那就完全不需要增加我们的编辑距离。
计算完成后，表格的最右下角就是两个串的最短编辑距离。
实现
最后一步当然是给出实现了。
class Index {
public static int minEditLength(String str1, String str2) {
int str1Len = str1.length();
int str2Len = str2.length();
int[][] table = new int[str1Len + 1][];
//初始化 Table col = str1 row = str2
for (int i = 0; i <= str1Len; i++) {
int[] col = new int[str2Len + 1];
for (int j = 0; j <= str2Len; j++) {
if (i == 0) {
col[j] = j;
} else if (j == 0) {
col[j] = i;
} else {
col[j] = 0;
}
}
table[i] = col;
}
// 启动 开始计算
for (int i = 1; i <= str1Len; i++) {
for (int j = 1; j <= str2Len; j++) {
String str1Cur = str1.substring(i - 1, i);
String str2Cur = str2.substring(j - 1, j);
// 列出三种编辑距离增加 lDis & rDis = 在串 A的基础上增加一个字符 编辑距离+1
// lrDis = 字符相同表示不需要任何增加|替换操作 编辑距离+0 否则等于替换操作 编辑距离+1
int lDis = table[i][j - 1] + 1;
int rDis = table[i - 1][j] + 1;
int lrDis = table[i - 1][j - 1] + (str1Cur.equals(str2Cur) ? 0 : 1);
// 三者找最小
table[i][j] = Math.min(lrDis, Math.min(rDis, lDis));
}
}
return table[str1Len - 1][str2Len - 1];
}
public static void main(String[] args) throws Exception {
println(minEditLength("MOUUSE", "MOUSEA"));
}
}
应该来说还是很简单易懂了，唯一需要说明的就是你需要提前先把第一行和第一列计算一下，剩下的格子才能依赖进行计算