在日常应用中，文本比较是一个比较常见的问题。文本比较算法也是一个老生常谈的话题。

文本比较的核心就是比较两个给定的文本（可以是字节流等）之间的差异。目前，主流的比较文本之间的差异主要有两大类。一类是基于编辑距离（Edit Distance）的，例如LD算法。一类是基于最长公共子串的（Longest Common Subsequence），例如Needleman/Wunsch算法等。

LD算法（Levenshtein Distance）又成为编辑距离算法（Edit Distance）。他是以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B，那么操作的过程的次数表示两个字符串的差异。

例如：字符串A：kitten如何变成字符串B：sitting。

第一步：kitten——》sitten。k替换成s

第二步：sitten——》sittin。e替换成i

第三步：sittin——》sitting。在末尾插入g

故kitten和sitting的编辑距离为3

定义说明：

LD(A,B)表示字符串A和字符串B的编辑距离。很显然，若LD(A,B)=0表示字符串A和字符串B完全相同

Rev(A)表示反转字符串A

Len(A)表示字符串A的长度

A+B表示连接字符串A和字符串B

有下面几个性质：

LD(A,A)=0

LD(A,"")=Len(A)

LD(A,B)=LD(B,A)

0≤LD(A,B)≤Max(Len(A),Len(B))

LD(A,B)=LD(Rev(A),Rev(B))

LD(A+C,B+C)=LD(A,B)

LD(A+B,A+C)=LD(B,C)

LD(A,B)≤LD(A,C)+LD(B,C)（注：像不像“三角形，两边之和大于第三边”）

LD(A+C,B)≤LD(A,B)+LD(B,C)

为了讲解计算LD(A,B)，特给予以下几个定义

A=a ₁ a ₂ ……a _N ，表示A是由a ₁ a ₂ ……a _N 这N个字符组成，Len(A)=N

B=b ₁ b ₂ ……b _M ，表示B是由b ₁ b ₂ ……b _M 这M个字符组成，Len(B)=M

定义LD(i,j)=LD(a ₁ a ₂ ……a _i ,b ₁ b ₂ ……b _j )，其中0≤i≤N，0≤j≤M

故：　　LD(N,M)=LD(A,B)

LD(0,0)=0

LD(0,j)=j

LD(i,0)=i

对于1≤i≤N，1≤j≤M，有公式一

若a _i =b _j ，则LD(i,j)=LD(i-1,j-1)

若a _i ≠b _j ，则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1

举例说明：A=GGATCGA，B=GAATTCAGTTA，计算LD(A,B)

第一步：初始化LD矩阵

这个LD算法时间复杂度为O(MN)，空间复杂度为O(MN)，如果进行优化的话，空间复杂度可以为O(M)，优化的代码这里不再详述了。参看“ 计算字符串的相似度（VB2005） ”

我们往往不仅仅是计算出字符串A和字符串B的编辑距离，还要能得出他们的匹配结果。

以上面为例A=GGATCGA，B=GAATTCAGTTA，LD(A,B)=5

他们的匹配为：

A： G G A _ T C _ G __ A

B： G A A T T C A G TT A

如上面所示，蓝色表示完全匹配，黑色表示编辑操作，_表示插入字符或者是删除字符操作。如上面所示，黑色字符有5个，表示编辑距离为5。

利用上面的LD矩阵，通过回溯，能找到匹配字串

第一步：定位在矩阵的右下角