简要
各位一定体验到过搜索引擎的纠错功能，当你在无意识的情况下将你搜索的内容输入错误时，搜索引擎会自动帮你纠错。如你本来想搜索happy，却不小心按到了y旁边的u，这时我们依然达到了我们想要的目的
那么这个是怎么实现的呢，先不考虑这个功能整体使用到的技术，先解决一个问题，它是怎么知道从happu到happy的，这就是我们今天要讲的编辑距离
概念
编辑距离（Edit Distance）
又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。一般来说，编辑距离越小，两个串的相似度越大。
从happu到happy只是把u替换成了y，操作次数为一次，所以编辑距离为1
运用
因此，有了这个概念，当我们知道一个词是错误的时候（怎么知道它错了，后面讨论），就只需从正确的词中找出和它编辑距离最小的一个或多个，就可以帮助用户纠错了
如何计算编辑距离
比如要计算cafe到coffee的编辑距离
先创建一个6x8的表（cafe长度为4，coffee长度为6，各加2）,先在表中如下位置填入相应数字
| 0 | 0 | c | o | f | f | e | e |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| c | 1 | ||||||
| o | 2 | ||||||
| f | 3 | ||||||
| e | 4 |
再从c到c对应的表格，也就是表格的（3，3）位置开始，按照以下规则填充数字
- 如果最上方的字符等于最左方的字符，则为左上方的数字。否则为左上方的数字+1。（对于3,3来说为0）
- 左方数字+1（对于3,3格来说为2）
- 上方数字+1（对于3,3格来说为2）
取上面得出的三个数字中最小数字填入（3，3）位置，根据上面得出的，最小为0，所以在（3，3）位置填入0，以此类推，完成所有空格的填充，如下
| 0 | 0 | c | o | f | f | e | e |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| c | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| o | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
| f | 3 | 2 | 2 | 1 | 2 | 3 | 4 |
| e | 4 | 3 | 3 | 2 | 2 | 2 | 3 |
取得表中右下角数字，既为cafe和coffee的最小编辑距离，为3
Java代码
public static double ld(String s, String t) {
int d[][];
int sLen = s.length();
int tLen = t.length();
int si;
int ti;
char ch1;
char ch2;
int cost;
if(sLen == 0) {
return tLen;
}
if(tLen == 0) {
return sLen;
}
d = new int[sLen+1][tLen+1];
for(si=0; si<=sLen; si++) {
d[si][0] = si;
}
for(ti=0; ti<=tLen; ti++) {
d[0][ti] = ti;
}
for(si=1; si<=sLen; si++) {
ch1 = s.charAt(si-1);
for(ti=1; ti<=tLen; ti++) {
ch2 = t.charAt(ti-1);
if(ch1 == ch2) {
cost = 0;
} else {
cost = 1;
}
d[si][ti] = Math.min(Math.min(d[si-1][ti]+1, d[si][ti-1]+1),d[si-1][ti-1]+cost);
}
}
return 1 - (double) d[sLen][tLen] / Math.max(src.length(), tar.length());
}
