在給定的字符串A和字符串B，LD(A,B)表示編輯距離，LCS(A,B)表示最長公共子串的長度。
如何來度量它們之間的相似度呢？
不妨設S(A,B)來表示字符串A和字符串B的相似度。那麼，比較合理的相似度應該滿足下列性質。
性質一：0≤S(A,B)≤100%，0表示完全不相似，100%表示完全相等
性質二：S(A,B)=S(B,A)
目前，網上介紹的各種相似度的計算，都有各自的不盡合理的地方。
計算公式一：S(A,B)=1/(LD(A,B)+1)
能完美的滿足性質二。
當LD(A,B)=0時，S(A,B)=100%，不過無論LD(A,B)取任何值，S(A,B)＞0，不能滿足性質一。
計算公式二：S(A,B)=1－LD(A,B)/Len(A)
當Len(B)＞Len(A)時，S(A,B)＜0。不滿足性質一。
有人會說，當S(A,B)<0時，強制指定S(A,B)=0就解決問題了。
問題是，S(A,B)=1－LD(A,B)/Len(A)，而S(B,A)=1－LD(B,A)/Len(B)。當Len(A)≠Len(B)時，S(A,B)≠S(B,A)。不滿足性質二
還有一個例子可以說明問題
A="BC"，B="CD"，C="EF"
S(A,B)=1－LD(A,B)/Len(A)=1－2/2=0
S(A,C)=1－LD(A,C)/Len(A)=1－2/2=0
A和B的相似度與A和C的相似度是一樣的。不過很明顯的是B比C更接近A
計算公式三：S(A,B)=LCS(A,B)/Len(A)
這個公式能完美的滿足的性質一
不過當Len(A)≠Len(B)時，S(A,B)≠S(B,A)。不滿足性質二
用一個例子說明問題
A="BC"，B="BCD"，C="BCEF"
S(A,B)=LCS(A,B)/Len(A)=2/2=100%
S(A,C)=LCS(A,C)/Len(A)=2/2=100%
A和B的相似度與A和C的相似度是一樣的。不過很明顯的是B比C更接近A
上面是網上能找到的三個計算公式，從上面的分析來看都有各自的局限性。
我們看一個例子：
A=GGATCGA，B=GAATTCAGTTA，LD(A,B)=5，LCS(A,B)=6
他們的匹配為：
A：GGA_TC_G__A
B：GAATTCAGTTA
可以看出上面藍色的部分表示的是LCS部分，黑色表示的是LD部分。
因此，給出一個新的公式
S(A,B)=LCS(A,B)/(LD(A,B)+LCS(A,B))
這個公式能解決上述三個公式的種種不足。
而LD(A,B)+LCS(A,B)表示兩個字符串A、B的最佳匹配字串的長度。這個是唯一的。
還有注意的是LD(A,B)+LCS(A,B)和Max(Len(A),Len(B))這兩個並不完全相等。
