文本比較算法Ⅰ—LD算法

 

在日常應用中，文本比較是一個比較常見的問題。文本比較算法也是一個老生常談的話題。

　　文本比較的核心就是比較兩個給定的文本（可以是字節流等）之間的差異。目前，主流的比較文本之間的差異主要有兩大類。一類是基於編輯距離（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算法矩陣     G A A T T C A G T T A   0 1 2 3 4 5 6 7 8 9 10 11 G 1                       G 2                       A 3                       T 4                       C 5                       G 6                       A 7                      

 

 

　　第二步：利用上述的公式一，計算第一行

 

LD算法矩陣     G A A T T C A G T T A   0 1 2 3 4 5 6 7 8 9 10 11 G 1 0 1 2 3 4 5 6 7 8 9 10 G 2                       A 3                       T 4                       C 5                       G 6                       A 7                      

 

 

　　第三步，利用上述的公示一，計算其余各行

LD算法矩陣     G A A T T C A G T T A   0 1 2 3 4 5 6 7 8 9 10 11 G 1 0 1 2 3 4 5 6 7 8 9 10 G 2 1 1 2 3 4 5 6 6 7 8 9 A 3 2 1 1 2 3 4 5 6 7 8 8 T 4 3 2 2 1 2 3 4 5 6 7 8 C 5 4 3 3 2 2 2 3 4 5 6 7 G 6 5 4 4 3 3 3 3 3 4 5 6 A 7 6 5 4 4 4 4 3 4 4 5 5

 

 

　　則LD(A,B)=LD(7,11)=5

 

　　下面是LD算法的代碼，用的是VB2005。代碼格式修正於2012年1月6日。

Public Class clsLD
　　Private Shared mA() As Char
　　Private Shared mB() As Char

　　Public Shared Function LD(ByVal A As String, ByVal B As String) As Integer

　　　　mA = A.ToCharArray
　　　　mB = B.ToCharArray

　　　　Dim L(A.Length, B.Length) As Integer
　　　　Dim i As Integer, j As Integer

　　　　For i = 1 To A.Length
　　　　　　L(i, 0) = i
　　　　Next
　　　　For j = 1 To B.Length
　　　　　　L(0, j) = j
　　　　Next

　　　　For i = 1 To A.Length
　　　　　　For j = 1 To B.Length
　　　　　　　　If mA(i - 1) = mB(j - 1) Then
　　　　　　　　　　L(i, j) = L(i - 1, j - 1)
　　　　　　　　Else
　　　　　　　　　　L(i, j) = Min(L(i - 1, j - 1), L(i - 1, j), L(i, j - 1)) + 1
　　　　　　　　End If
　　　　　　Next
　　　　Next

　　　　Return L(A.Length, B.Length)
　　End Function

　　Public Shared Function Min(ByVal A As Integer, ByVal B As Integer, ByVal C As Integer) As Integer
　　　　Dim I As Integer = A
　　　　If I > B Then I = B
　　　　If I > C Then I = C
　　　　Return I
　　End Function
End Class