一、 Levenshtein 距离
许多基因算法（如Wagner-Fischer 算法）基于以下观察计算编辑距离：如果我们构造一个矩阵来保存第一个字符串和第二个字符串的所有前缀，以及所有前缀之间的编辑距离（局部最优距离），那么我们可以通过填充填充来计算矩阵中的值，从而找到两个完整字符串之间的距离作为计算的最后一个值。
下面用简单的伪代码实现，描述编辑距离的法则。它接受两个字符串a和b，之间的 Levenshtein 距离（长度分别为 和 ）由 其中
其中某个字符串的是除了 的第一个字符之外的所有字符的字符串，并且 是字符串的第 个字符，从 0 开始计数。
请注意，最小值中的第一个元素对应于删除（从 到 ），第二个对应于插入，第三个对应于替换。这个定义直接对应于朴素的递归实现。
例如，“kitten”和“sitting”之间的 Levenshtein 距离为 3，因为以下 3 次编辑将一个更改为另一个，并且少于 3 次编辑没有办法做到这一点：
kitten → sitten（用“s”代替“k”），sitten → sittin（用“i”代替“e”），sitten→sitting（在末尾插入“g”）。
二、上限和下限
Levenshtein 距离有几个简单的上限和下限。这些包括：
至少是两个字符串大小的差异。它最多是较长字符串的长度。当且仅当字符串相等时它才为零。如果字符串具有相同的大小，则汉明距离是 Levenshtein 距离的上限。汉明距离是两个字符串中对应符号不同的位置数。两个字符串之间的 Levenshtein 距离不大于它们与第三个字符串的 Levenshtein 距离之和（三角不等式）。
两个相同长度的弦之间的 Levenshtein 距离严格小于 Hamming 距离的示例由“flaw”和“lawn”对给出。这里 Levenshtein 距离等于 2（从前面删除“f”；在末尾插入“n”）。汉明距离为 4。
三、Levenshtein 距离应用
在近似字符串匹配中，目标是在预期会有少量差异的情况下，在许多较长文本中找到短字符串的匹配项。例如，短字符串可能来自字典。在这里，一根弦通常很短，而另一根则任意长。这具有广泛的应用，例如拼写检查器、光学字符识别的校正系统以及基于翻译记忆库辅助自然语言翻译的软件。
Levenshtein 距离也可以在两个较长的字符串之间计算，但是计算它的成本大致与两个字符串长度的乘积成正比，这使得这不切实际。因此，当用于在记录链接等应用程序中帮助模糊字符串搜索时，比较字符串通常很短，以帮助提高比较速度。[需要引用]
在语言学中，Levenshtein 距离被用作量化语言距离或两种语言彼此之间差异程度的度量。 [3]它与互懂度有关：语言距离越大，互懂度越低，语言距离越小，互懂度越高。
四、与其他编辑距离指标的关系
还有其他流行的编辑距离度量，它们是使用一组不同的允许编辑操作来计算的。例如，
Damerau-Levenshtein 距离允许两个相邻字符的换位以及插入、删除、替换；最长公共子序列（LCS）距离只允许插入和删除，不允许替换；汉明距离只允许替换，因此，它只适用于相同长度的字符串。Jaro 距离只允许换位。
编辑距离通常定义为使用一组特定的允许编辑操作计算的可参数化度量，并且为每个操作分配一个成本（可能是无限的）。这通过 DNA 序列比对算法（例如 Smith-Waterman 算法）进一步推广，该算法使操作的成本取决于其应用的位置。
五、全矩阵迭代
（注意：本节使用从 1 开始的字符串，而不是从 0 开始的字符串。）计算 Levenshtein 距离是基于以下观察：如果我们保留一个矩阵来保存第一个字符串的所有前缀和第二个字符串的所有前缀之间的 Levenshtein 距离，那么我们可以以动态编程方式计算矩阵中的值，并且因此找到两个完整字符串之间的距离作为计算的最后一个值。该算法是自下而上动态规划的一个示例，在 1974 年由 Robert A. Wagner 和 Michael J. Fischer 撰写的文章 The String-to-string correction problem 中讨论了变体。 [4]这是函数 LevenshteinDistance 的简单伪代码实现，它接受两个字符串，长度为 m 的 s 和长度为 n 的 t，并返回它们之间的 Levenshtein 距离：
function LevenshteinDistance(char s[1..m], char t[1..n]):// for all i and j, d[i,j] will hold the Levenshtein distance between// the first i characters of s and the first j characters of tdeclare int d[0..m, 0..n]set each element in d to zero// source prefixes can be transformed into empty string by// dropping all charactersfor i from 1 to m:d[i, 0] := i// target prefixes can be reached from empty source prefix// by inserting every characterfor j from 1 to n:d[0, j] := jfor j from 1 to n:for i from 1 to m:if s[i] = t[j]:substitutionCost := 0else:substitutionCost := 1d[i, j] := minimum(d[i-1, j] + 1, // deletiond[i, j-1] + 1, // insertiond[i-1, j-1] + substitutionCost) // substitutionreturn d[m, n]
六、LD算法
6.1 LD算法原理
算法目的：计算出两字符序列的编辑距离，同时也能求出两序列的匹配序列
假设：
比对的俩序列为：
则两序列的长度分别为len(A) = n，Len(B)=m；
LD(A,B)：字符串A和字符串B的编辑距离，即将字符串A转换为字符串B所用的最少字符操作数。
LD(A,B)=0表示两个字符串完全一样。
LD(i,j)=LD(a1a2……ai,b1b2……bj)，其中0≤i≤N，0≤j≤M
算法步骤：
1 初始化算法分数矩阵H，使行i表示字符ai，列j表示字符bj；
2 计算矩阵中每一项的LD(i, j)：
若ai = bj，则LD(i, j) = LD(i-1, j-1) 取左上角的值
若ai ≠ bj，则LD(i, j) = Min( LD(i-1, j-1), LD(i-1, j), LD(i, j-1) ) +1
3 回溯，从矩阵右下角开始：
若ai=bj，则回溯到左上角单元格；
若ai≠bj，回溯到左上角、上边、左边中值最小的单元格，若有相同最小值的单元格，优先级按照左上角、上边、左边的顺序。
4 根据回溯路径，写出匹配字符串：
若回溯到左上角单元格，将ai添加到匹配字串A‘，将bj添加到匹配字串B’；
若回溯到上边单元格，将ai添加到匹配字串A’，将_添加到匹配字串B’；
若回溯到左边单元格，将_添加到匹配字串A’，将bj添加到匹配字串B’。
5 矩阵右下角的值即为俩序列的编辑距离，回溯结果为全部匹配序列。
6.2 示例
给定字符串：A=GGATCGA，B=GAATTCAGTTA，评分矩阵：
在分数表中表示空字符串；比如第二行，与串GAATTCAGTTA距离从1到11随位置而递增。
第二列，表示串A=GGATCGA与之间的位置距离递增。
如果X的位置为【i，j】那么X的值将为：
if i ==j :if text(i,0) == text(0,j):fit(i,j) = 0elseiftext(i,0) != text(0,j):fit(i,j) = 1elsefit(i,j) = 1
因此上例中：X = 0 + 0 = 0
将全部矩阵填满后，如下图。红线代表回溯，找出匹配路径。
LD算法的流程和needleman wunsch算法是很类似的，区别在于LD算法使用的是最小值，NW算法使用的是最大值。
