1. Definition of Minimum Edit Distance
Edit Distance用于衡量两个strings之间的相似性。
两个strings之间的Minimum edit distance是指把其中一个string通过编辑（包括插入，删除，替换操作）转换为另一个string的最小操作数。
如上图所示，d（deletion）代表删除操作，s（substitution）代表替换操作，i（insertion）代表插入操作。
（为了简单起见，后面的Edit Distance 简写为ED）
如果每种操作的cost（成本）为1，那么ED = 5.
如果s操作的cost为2（即所谓的Levenshtein Distance），ED = 8.
2. Computing Minimum Edit Distance
那么如何找到两个strings的minimun edit distance呢？要知道把一个string转换为另一个string可以有很多种方法（或者说"路径"）。我们所知道起始状态（第一个string）、终止状态（另一个string）、基本操作（插入、删除、替换），要求的是最短路径。
对于如下两个strings：
X的长度为n
Y的长度为m
我们定义D（i，j）为 X 的前i个字符 X[1...i] 与 Y 的前j个字符 Y[1...j] 之间的距离，其中0<i<n, 0<j<m，因此X与Y的距离可以用D(n,m)来表示。
假如我们想要计算最终的D(n,m)，那么可以从头开始，先计算D(i, j) （i和j从1开始）的值，然后基于前面的结果计算更大的D(i, j)，直到最终求得D(n,m)。
算法过程如下图所示：
上图中使用的是"Levenshtein Distance"即替换的成本为2.
请读者深入理解一下上图中的循环体部分： D(i,j)可能的取值为:
1. D(i-1, j) +1 ；
2. D(i, j-1) +1 ；
3. D(i-1, j-1) + 2 (当X新增加的字符和Y新增加的字符不同时，需要替换）或者 + 0（即两个字符串新增加的字符相同）
下图即对字符串 INTENTION 和 EXECUTION 一步步求ED形成的表。左上角画红圈的8就是两个字符串间的最小ED。
Read full article from 算法之美――求解 字符串间最短距离（动态规划） - 小熊不去实验室 - 博客频道 - CSDN.NET
No comments:
Post a Comment