编辑距离：我和你到底有多远？（一）
编辑距离是很早之前看到的题目，觉得很好玩的样子，昨晚看完Hash的资料，趁着还有劲头就查了下资料。
先说一下问题描述，很简单。原始场景很多，例如，在我们搜索资料的时候，常常打错字，如想查询swim却输入成了swam。我们在使用搜索引擎的时候都会看到，搜索引擎一般会提示“你是不是想搜索XXX？”，纠正拼写错误。那么，搜索引擎是如何判断你想输入哪个单词呢？这就需要判断你所输入的swam与单词库中的哪个单词的编辑距离最小，之后再结合上下文（若有的话）即可推断出你输入的单词，从而给出拼写错误提示。
其次，我们再定义一下编辑距离，有了定义才有讨论的基础。两个单词之间的编辑距离，顾名思义，是使用最少的编辑操作使得第一个单词转换为第二个单词。那么，编辑操作又包括哪些？
百度百科上对编辑距离的定义和维基百科基本相同。
编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
例如将kitten一字转成sitting：
sitten （k→s）
sittin （e→i）
sitting （→g）
俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
这里L氏距离中，定义的编辑操作包括三种：替换、插入和删除。
但是，对于我刚开始接触这个题目的时候，困扰之一的就是如何定义编辑操作。因为除了这三种之外，还有一种：相邻字母交换操作。这在我看来是一个编辑操作，但却没有在Levenshtein距离中定义。
【注：另外，对于各操作的权值的定义，不同的版本有不同的说法。有认为三种操作权重相同，都为1；也有认为插入和删除操作为1，替换操作为2。对于相邻字母交换操作，没看到相关资料评价。不过本文不谈论此点，因为我认为权值的确定需要参考汇编的代码，由汇编语言中各操作的实现代码来决定，需要汇编操作多的，耗时多，自然权值就大。不过，本文略去，全部以权值为1讨论。如需更改，只需修改代码中对应加值即可。】
在维基百科Edit distance和String metric中有提到，在信息和计算机科学领域中，通常说的编辑距离就是指L氏距离，可以由 Hirschberg's algorithm 或 the Wagner–Fischer algorithms 算法实现【有空看下】。
The most widely known string metric is a rudimentary one called the Levenshtein Distance (also known as Edit Distance).
Levenshtein distance (the most common definition, calculated by Hirschberg's algorithm or the Wagner–Fischer algorithm)
而我所认为的应该包含交换操作的距离也有名称，叫Damerau–Levenshtein distance(named after Frederick J. Damerau and Vladimir I. Levenshtein)，包含了：替换、插入、删除和相邻字母交换四种编辑操作。
好，既然定义明白了，下面我们就来讨论一下这个问题该如何去解。网上的资料大部分计算的是L氏距离（毕竟影响最广），我修改了下，也可以用来计算D-L距离。
查阅了下网上的资料，基本都是用动态规划做的。
那动态规划到底是个什么东西？
百度百科里介绍说：
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。
总的来说，动态规划是“动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。”基本思想如下：
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
动态规划一般可解决的问题很多，具体可以参看百度百科链接，但这次我们就只看编辑距离，以后有兴趣再研究动态规划这一类的问题。
归根到底，动态规划是要求最优解。而这个问题不是独立的，是可以分解成若干个子问题，而这些子问题往往不是互相独立的。因此，我们需要保存已解决的子问题的答案，填入表中，将原问题一步步分解得到的子问题逐步求解，从而得到整个问题的最优解。
OK，万事俱备。
根据动态规划思想，我们可以得到这样的一个操作方法：
对于字符串A和B，我们构建一个m*n的二维数组D。其中，m=len(A)+1, n=len(B)+1。这样，二维数组的范围就是D[0...m-1][0...n-1]（即：D[0...len(A)][0...len(B)]）。
对二维数组初始化。令D[0][0...n-1]=0...n-1, matrix[0...m-1][0]=0...m-1，（其实第0行和第0列就相当于id，真正最后有用的是D[1...m-1][1...n-1]这个len(A)*len(B)的矩阵）。
遍历D[1...m-1][1...n-1]这个矩阵。对于其中的任意元素D[i][j]，有：D[i][j]=min{D[i-1][j]+1, D[i][j-1]+1, D[i-1][j-1]+f(i,j)}。
此处，我们将插入、删除的操作权值都简化为1。而定义替换操作权值f(i,j)： 若A[i]==B[j]，则为0；若A[i]!=B[j]，则为1。
【注：完整版为：D[i][j]=min{D[i-1][j]+insertCost(i), D[i][j-1]+deleteCost(j), D[i-1][j-1]+substitudeCost(i,j)}，参考北大中文系詹卫东的最小编辑距离算法】
遍历完毕，得到最终结果矩阵，D[m-1][n-1]（即D[len(A)][len(B)]）就是字符串A和B的编辑距离。
我们使用詹卫东中的例子sot和stop来演示一下（与原文结果不同，是因为此处操作权值全部按1计算）。
1.构建二维数组D[4][5]，并初始化D[0][0...4]和D[0...3][0]。如图1.
2.遍历矩阵，计算并得到最终结果。对于每个元素，都要比较{左元素+1，下元素+1，左下元素+f(i,j)}的最小值，其中若f(i,j) = (A[i] == B[j] ? 0 :1)。得到结果，如图2。其中，右上角的2即是最终编辑距离。
完毕。
这一篇就到这里，下一篇编辑距离：我和你到底有多远？（二）我们给出Java实现代码，并进一步修改，增加交换编辑操作，实现D-L距离。
