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

張勝楠

（湖北輕工職業(yè)技術(shù)學(xué)院信息工程學(xué)院，武漢 430000）

0 引言

求字符串相似度的算法在自然語言處理、抄襲檢測、網(wǎng)頁搜索等領(lǐng)域應(yīng)用廣泛，如編輯距離算法、最長公共子串算法、貪心字符串匹配算法、Heckel 算法等非常經(jīng)典。當(dāng)比較兩字符串相似度時，編輯距離算法基于字面相似的方法計算，針對不同的需求對編輯距離算法改進的方法層出不窮，有作者考慮了非相鄰字符間的交換操作，使編輯操作次數(shù)最小化；有作者從多公共字符串的熵出發(fā)來計算文本相似度等。這些方法往往只考慮他們的編輯次數(shù)而忽略了最長公共子序列（longest common subsequence，LCS）對字符串間相似度的影響，或者考慮了LCS但忽略了最長公共子串（longest common substirng，LCCS）的影響，使用傳統(tǒng)的基于編輯距離求相似度的公式無法得到合理的結(jié)果。如情況一，字符串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是在字符相對位置不變的情況下并不要求必須連續(xù)，它反映了字符串的雷同性，常用于相似性檢查。LCCS則必須是連續(xù)的最長的公共子串，對相似度計算具有一定的影響，本文提出一種基于LD綜合考慮LCS和LCCS的字符串相似度算法，以改善準(zhǔn)確性和適用性。

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

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

編輯距離由俄國科學(xué)家Vladimir Levenshtein于1965 年提出，以字符為編輯單位，計算由一個字符串到另一個字符串的最少操作（刪除、插入、替換）次數(shù)，常被用于字符串的相似度計算。設(shè)兩個字符串S=S1S2S3…Sm和T=T1T2T3…Tn，構(gòu)造矩陣LD［m+1，n+1］，使用動態(tài)規(guī)劃的思想循環(huán)計算矩陣中每個單元格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) ，其中，當(dāng)S的第i個詞不等于T的第j個詞時，f(i，j)=1；否則，f(i，j)=0。LD本身就能表示兩個字符串的相似程度，直觀上LD越大，相似性越小。表示相似度Sim(S，T)的計算公式如下：

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

1.2 結(jié)合LCS和LD的字符串相似度算法

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

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

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

2 基于LD、LCS和LCCS的字符串相似度優(yōu)化算法

2.1 基于列向量的編輯距離求解優(yōu)化算法

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

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

1.設(shè)n是S的長度，m是T的長度（設(shè)n

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

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

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

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

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

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

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

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

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

2.2 基于降維的最長公共子序列算法優(yōu)化

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

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

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

2.定義數(shù)組base［］大小為T.length（）+1，定義遞推前導(dǎo)front=0，當(dāng)前元素pre=0；

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

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

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

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

7. 循環(huán)更新base和front，base［j-1］=front，front=pre；

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

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

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

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

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

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

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

圖1 優(yōu)化算法的計算流程

3 實驗分析及結(jié)論

實驗用兩組數(shù)據(jù)分析算法的準(zhǔn)確度、適用性和區(qū)分性。數(shù)據(jù)一選取源串S=“expect”，目標(biāo)串集合W={w1,w2,w3,w4,w5,w6,w7}={“spectator”，“exercise”，“pecuniary”，“accept”，“excerpt”，“exempt”，“aspect”｝。數(shù)據(jù)二源文本S=“abcde01234”，在英文詞典中選出與word 接近的一組單詞構(gòu)成目標(biāo)串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 相似度結(jié)果分析

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

圖2 數(shù)據(jù)集W的相似度比較

3.2 實驗結(jié)論

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

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

表1 數(shù)據(jù)對比

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

4 結(jié)語

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