基于編輯距離的字符串相似度算法研究

張勝楠

（湖北輕工職業技術學院信息工程學院，武漢 430000）

0 引言

求字符串相似度的算法在自然語言處理、抄襲檢測、網頁搜索等領域應用廣泛，如編輯距離算法、最長公共子串算法、貪心字符串匹配算法、Heckel 算法等非常經典。當比較兩字符串相似度時，編輯距離算法基于字面相似的方法計算，針對不同的需求對編輯距離算法改進的方法層出不窮，有作者考慮了非相鄰字符間的交換操作，使編輯操作次數最小化；有作者從多公共字符串的熵出發來計算文本相似度等。這些方法往往只考慮他們的編輯次數而忽略了最長公共子序列（longest common subsequence，LCS）對字符串間相似度的影響，或者考慮了LCS但忽略了最長公共子串（longest common substirng，LCCS）的影響，使用傳統的基于編輯距離求相似度的公式無法得到合理的結果。如情況一，字符串S=“abcd”與T1=“dcba”和T2=“cdab”比較相似性時，計算的編輯距離LD都是4，若不考慮LCS，就無法判斷出T2與S更相似；再比如情況二，字符串S=“abcdef”與T1=“amcnf”和T2=“abcmng”比較相似性時，計算的編輯距離（levenshtein distance，LD）和最長公共子序列LCS都是3，所以即使考慮了LCS，也無法判斷出T2與S更相似。

LCS是在字符相對位置不變的情況下并不要求必須連續，它反映了字符串的雷同性，常用于相似性檢查。LCCS則必須是連續的最長的公共子串，對相似度計算具有一定的影響，本文提出一種基于LD綜合考慮LCS和LCCS的字符串相似度算法，以改善準確性和適用性。

1 基于編輯距離的字符串相似度算法

1.1 基于編輯距離的字符串相似度計算

編輯距離由俄國科學家Vladimir Levenshtein于1965 年提出，以字符為編輯單位，計算由一個字符串到另一個字符串的最少操作（刪除、插入、替換）次數，常被用于字符串的相似度計算。設兩個字符串S=S1S2S3…Sm和T=T1T2T3…Tn，構造矩陣LD［m+1，n+1］，使用動態規劃的思想循環計算矩陣中每個單元格LD(i,j)的值，最右下角的LD(m,n)即為所求編輯距離大小，計算公式如下［1］：

Min = min{LD(i- 1,j) + 1,LD(i,j- 1) + 1,}LD(i- 1,j- 1) +f(i,j) ，其中，當S的第i個詞不等于T的第j個詞時，f(i，j)=1；否則，f(i，j)=0。LD本身就能表示兩個字符串的相似程度，直觀上LD越大，相似性越小。表示相似度Sim(S，T)的計算公式如下：

但其并不具備好的普遍適用性，例如設字符串S：abcdef，T：mefngh 則LD（S,T）=6，Sim（S,T）=1-6/6=0，兩字符串的相似度卻是0，顯然不符合實際情況。

1.2 結合LCS和LD的字符串相似度算法

求解LCS長度的方法很多［2］，如窮舉法：對T串的所有子序列檢查是否為S的子序列，從而確定是否為公共子序列，再選出最長的，但是對于兩個長度分別為m、n的字符串，時間復雜度為指數級別的O（2n*2m）；還有遞歸法：編程簡單、易于理解，但由于有大量重復遞歸調用，效率不高。經典的動態規劃的方法：將復雜問題簡單化，引入數組來存放所有子問題的解，從而省去重復求解相同子問題的麻煩，當求LCS時，用L［i,j］記錄序列Si和Tj的最長公共子序列的長度，最后，S和T的LCS的長度記錄于L［m,n］中，建立遞歸關系如下：

當比較兩個字符串S和T的相似度大小時，除了編輯距離LD的直觀影響外，兩字符串最長公共子序列LCS的大小也很重要，那么結合LD和LCS給出另一個相似度計算公式如下：

重新計算引言的情況一得：S（S,T1）=1/5 小于S（S,T2）=2/6，能正確地表示合理的相似度。經實驗證明此公式有良好的適用性且拓展了傳統公式的普遍適用性，但引言中提到的情況二仍未得到解決，下面結合最長公共子串繼續對相似度計算公式進行改進。

2 基于LD、LCS和LCCS的字符串相似度優化算法

2.1 基于列向量的編輯距離求解優化算法

傳統編輯距離算法的空間、時間復雜度都是O（m*n），考慮到每次計算LD（i,j）時只需用到LD（i,j-1）、LD（i-1,j）和LD（i-1,j-1），即只需要當前列和前一列參加計算即可，因此本文利用兩個列向量代替矩陣，每次只保存當前的狀態和上次運算的狀態，實驗表明在基本不影響結果和時間復雜度的情況下，空間復雜度減少為O（min（m,n））。

算法描述如下：輸入：字符串S、T；輸出：LD長度。

1.設n是S的長度，m是T的長度（設n

2.初始化v0［m+1］的值為0…m；

3.檢查S（ifrom 1 ton）中的每個字符；

4.檢查T（jfrom 1 tom）中的每個字符；

5.設cost 為編輯代價，ifs［i］==t［j］，則cost=0；ifs［i］!=t［j］，則cost=1；

6.設置單元v1［j］為下面的最小值之一：

7. 緊鄰該單元上方+1：v1［j-1］+1

8. 緊鄰該單元左側+1：v0［j］+1

9. 該單元對角線左上角+cost：v0［j-1］+cost

10.在完成迭代（3,4,5,6）之后，v1［m］便是編輯距離的值。

2.2 基于降維的最長公共子序列算法優化

考慮到當計算L［i,j］時只和L［i-1,j-1］，L［i,j-1］，L［i-1,j］三個元素直接相關，即在計算L［i］這一行的子問題時，只需要知道L［i-1］一行的值和當前L［i,j］的前一個元素L［i,j-1］的值即可，此時，在時間復雜度不變的情況下，空間復雜度由O（m*n）降低為O（n）。定義一個長為m+1 的數組base［］并初始化為0，一個遞推前導front=0，一個當前計算元素pre（意義上的L［i,j］），每次計算完L［i,j］后，把front的值更新到base［j-1］上，然后把pre更新到front上，然后繼續向后掃描，注意最后一個元素的更新。這樣迭代n次，最后base［m］的值即LCS的值。

算法描述如下：輸入：字符串S、T，輸出：LCS長度。

1.輸入兩個字符串S，T；

2.定義數組base［］大小為T.length（）+1，定義遞推前導front=0，當前元素pre=0；

3.初始化base［］為0，base［i］=0；

4.檢查S（ifrom 1 toS.length（））的每個字符；

5.檢查T（ifrom 1 toT.length（））的每個字符；

6.循環檢查若S［i-1］=T［j-1］則pre=base［j-1］+1；否則pre=max（front,base［j］）；

7. 循環更新base和front，base［j-1］=front，front=pre；

8.更新base［T.length（）］=front，檢查base［j］（jfrom 1 toT.length（））并輸出base［］值；

9. 循環（4,5,6,7,8）最后base［T.length（）］就是LCS的值。

求解LCCS時，首先構造二維矩陣L［m+1］［n+1］并初始化，若Si=Tj，則L［i］［j］=1；最后找到矩陣中最長的斜對角線上為1 的字串就是LCCS，考慮到查找的麻煩，直接在矩陣需要填1時讓他等于左上角值加1，這樣矩陣中的最大元素就是LCCS的長度，LCCS的首字符位置就是第一個發生改變的單元格的坐標輸出。

2.3 基于LD、LCS和LCCS的字符串相似度優化計算方法

當考慮連續的最長公共子串LCCS的影響力之后，引言中的情況二就有了解決辦法，在LD和LCS都相同時，可以通過比較LCCS來判斷相似度，計算得LCCS（S,T1）=1小于LCCS（S,T2）=3，可以判斷出T2和S的相似度更高，這也和人的主觀判斷方式相一致。設字符串S=“abcmg”，T1=“abcnp”，T2=“ebcmf”，現在發現這三個關鍵的影響因子大小都一樣，但更接近人工主觀判斷的結果是S和T1更相似，本文的解決方法是綜合考慮LCCS的長度和出現位置，引入一個變量p表示目標串S中最長連續公共子串的首位置，當LCS長度和LD大小都一樣時，LCCS值越大則相似度越大；當LCCS長度也一樣時，考慮到前驅字符（當前處理字符前一個字符）比后繼字符（當前處理字符后一個字符）對相似度的影響更大，則p越小說明LCCS首字符位置越靠前相似度越大，μ是一個平衡此因子的變量，可以根據對LCCS需求的嚴格程度人為設定。定義新的相似度計算公式如下：

重新計算上面例子，設μ= 1，使用公式（5）計算Sim(S,T1)= 0.6，Sim(S,T2)= 0.563，得S和T1的相似度大于S和T2 的相似度，較之前結果更符合實際情況、區分性更好。

設字符串S和T長度分別是m和n，按照前文介紹的優化算法步驟求得編輯距離大小LD（S,T）和最長公共子序列長度LCS（S,T），按照LCCS算法步驟求得最長公共子串長度LCCS（S,T）和子串首字符位置p，其中過濾掉了無意義的全符號比較，按照提出的相似度公式計算相似度，Java語言實現，算法流程如圖1所示。

圖1 優化算法的計算流程

3 實驗分析及結論

實驗用兩組數據分析算法的準確度、適用性和區分性。數據一選取源串S=“expect”，目標串集合W={w1,w2,w3,w4,w5,w6,w7}={“spectator”，“exercise”，“pecuniary”，“accept”，“excerpt”，“exempt”，“aspect”｝。數據二源文本S=“abcde01234”，在英文詞典中選出與word 接近的一組單詞構成目標串T=｛t0，t1，t2，t3，t4，t5，t6，t7，t8，t9，t10，t11，t12，t13｝=｛“wqefghlm56234”，“e01abcd”，“fbcdm56789”，“fghlm51234”，“mgcde05678”，“w01234abc”，“mghln01234”，“abcde56789”，“fghde01234"，“abcde01567”，“fgcde01234”，“abcde012fg”，“fbcde01234”，“abcde01235”｝。

3.1 相似度結果分析

分別采用公式（2）、公式（4）和公式（5）三個相似度計算公式求解相似度，對兩組數據的字符串相似度計算結果進行對比分析，另外為了更詳細地描述實驗結論，便于比較說明，給出第一組的對比數據如圖2所示。

圖2 數據集W的相似度比較

3.2 實驗結論

可以看出，在對目標串集合w1～w8，t1～t13的考察中，公式（4）、公式（5）的結果較公式（2）更加合理精確，避免了由字符順序變化導致的相似度極度不合理的情況，公式（5）求解的相似度和公式（4）走勢大致一樣，基本介于公式（2）和公式（4）的結果之間，說明了公式（5）的適用性和穩定性，當公式（2）、公式（4）兩條線有重合持平時，即這兩種方法無法區分相似度時，公式（5）的線條有上升或下降的變化，可以得到區分性更好的結果。

由表1 的第3、5 組數據可以看出，當LD相同時公式（4）、公式（5）較公式（2）有更合理、更具區分性的結果，由表第6、7、8組數據看出當LCS和LD都相同時，公式（5）較公式（2）和（4）得出了更合理且有區分性的相似度數據，數據因LCCS的長度和位置不同而變化，公式（5）相對于公式（2）、公式（4）有更適中的標準差和極差，使相似度結果更合理。

表1 數據對比

綜上，可以看出公式（5）具有良好的普遍適應性，且比公式（2）和公式（4）結果更精確合理，結果具有更好的區分性。

4 結語

按照提出問題、分析問題和解決問題的思路對字符串相似度的計算進一步改善。考慮到LCS和LCCS對計算字符串相似度的重要影響，基于編輯距離的相似度算法進行改進，改進的字符串相似度算法提高了算法的普遍適用性和結果精確性，對于差異性很小的字符串也可以得到較好區分性的相似度。另外，對LD和LCS的傳統計算過程在數據結構方面進行了優化，在時間復雜度基本不受影響的情況下進一步降低了算法的空間復雜度。