Levenshtein Distance（LD Algorithm）的编辑距离算法原理

另一种说法是将莱文斯坦距离视为一种编辑距离的表现形式。它衡量的是将一个字符串转换成另一个字符串所需的最小编辑操作数量。可采用的方式包括字符替换、字符插入以及字符删除三种基本操作步骤数即为此处所指的距离值。

LD算法原理：

算法目标：求解两个字符序列之间的海莱距离，并不仅能够获得匹配序列还能够得到匹配路径。

假设：
比对的俩序列为：

则两序列的长度分别为len(A)等于n, Len(B)等于m。定义LD(A,B)为字符串A与B之间的编辑距离, 即将A转换为B所需的最少字符操作数。当LD(A,B)等于零时, 表示两个字符串完全相同。同时, LD(i,j)等同于比较a1a2...ai与b1b2...bj这两个子串之间的编辑距离, 其中i和j分别满足0 ≤ i ≤ N以及0 ≤ j ≤ M。

算法步骤：

初始化算法分数矩阵H并令其行i对应字符 ai 、列j对应字符 bj ；
计算矩阵中各位置的LD值：
当 ai = bj 时，则当前单元格之LD值等于其左上角单元格之值；
反之则令当前单元格之LD值等于左边、上边及左上方