王遠(yuǎn)超，安俊秀，程芃森，王 鵬

(成都信息工程學(xué)院軟件工程學(xué)院，四川成都610225)

0 引言

在信息理論和計算機科學(xué)領(lǐng)域里，字符串之間的相似度研究獲得了廣泛地應(yīng)用，而字符串與字符串之間的相似問題可轉(zhuǎn)化成一個字符串變成另一個字符串所需的編輯操作次數(shù)的問題。Levenshtein[1]提出基于獨立符號的插入、刪除和替換操作的最小編輯距離算法，即編輯距離算法的源模型，因此編輯距離也被稱為Levenshtein距離。Wagner R A和Lowrance R[2]在Levenshtein的基礎(chǔ)上提出增加相鄰位置字符之間地交換操作，對于相鄰位置順序顛倒的兩個字符采用正序糾正操作，使兩個字符串的相似度比較結(jié)果達(dá)到最小化。Sten Hjelmqvist[3]在Levenshtein的基礎(chǔ)上提出采用兩個一維數(shù)組分別保存求解過程中的前一步求解結(jié)果和當(dāng)前的求解結(jié)果，逐步迭代并交換前一步結(jié)果和當(dāng)前結(jié)果，最終求解出兩個字符串之間的編輯距離值。趙作鵬等[4]提出增加非相鄰位置字符的交換操作，是對文獻(xiàn)[2]地擴展，針對順序顛倒的不相鄰的多個連續(xù)或非連續(xù)字符在合理的范圍內(nèi)實現(xiàn)最小化的編輯操作。吳玲等[5]提出分段處理的1/p概率字符串匹配方法實現(xiàn)求解兩字符串的編輯距離。

基于編輯距離模型的近似字符串匹配被廣泛應(yīng)用于數(shù)據(jù)庫重復(fù)記錄消除、數(shù)據(jù)庫元數(shù)據(jù)語義標(biāo)注、語音辨識、拼寫檢查、DNA分析等領(lǐng)域。Monge A E和Elkan C P[6]基于啟發(fā)式方法結(jié)合編輯距離模型快速識別數(shù)據(jù)庫中損壞或重復(fù)的記錄，該方法采用類似聚類算法的思想能夠快速識別領(lǐng)域無關(guān)的重復(fù)記錄。Hernández M A和Stolfo S J[7]基于信息相關(guān)性理論結(jié)合編輯距離模型，實現(xiàn)對不同的大型數(shù)據(jù)庫所產(chǎn)生的重復(fù)記錄信息進(jìn)行合并處理。邱越峰和田增平等[8]提出編輯距離的一種改進(jìn)方法，消除數(shù)據(jù)庫中的重復(fù)記錄信息，提高了數(shù)據(jù)庫中數(shù)據(jù)信息的質(zhì)量。董國卿和童維勤[9]結(jié)合編輯距離算法計算元數(shù)據(jù)與本體實體間的語義相似度對元數(shù)據(jù)進(jìn)行自動語義標(biāo)注，實現(xiàn)異構(gòu)數(shù)據(jù)庫的信息集成。Cohen[10]使用編輯距離模型以及基于標(biāo)記的TF-IDF字符串相似值來計算導(dǎo)出的網(wǎng)頁在數(shù)據(jù)庫表中的相似性連接排名。Bakker等[11]和Holman等[12]提出歸一化劃分編輯距離方法(LDND)評價各種不同語言之間的距離。Petroni和Serva[13]提出不同源語言具有相同語義的Levenshtein距離思想，提出歸一化編輯距離(LDN)評價各種不同語言之間的距離。Wichmann等[14]通過實踐證明LDND方法相對于LDN方法在評價不同語言的相關(guān)度問題上更好。Gooskens C和Heeringa W[15]及Beijering K等[16]使用編輯距離算法針對相同文本在不同方言里的發(fā)音相似度進(jìn)行了研究，用于預(yù)測不同方言的語言可知度和語言感知距離。Brill和Moore[17]基于編輯距離思想通過期望最大化(EM)算法訓(xùn)練得到的拼寫糾正模型提高了拼寫糾正系統(tǒng)的檢查糾正能力和結(jié)果識別準(zhǔn)確率。在生物信息學(xué)領(lǐng)域，R Durbin[18]利用編輯距離算法對基因序列排列方式進(jìn)行研究，在進(jìn)化論以及生物化學(xué)評估方面獲得廣泛的應(yīng)用。Patil N等[19]提出基于編輯距離模型的模糊匹配算法對基因數(shù)據(jù)進(jìn)行分類，簡化了基因序列分類過程并提高了分類速度。

上述對編輯距離模型的應(yīng)用都是使用一個二維矩陣對兩個字符串的距離值進(jìn)行動態(tài)迭代求解，時間復(fù)雜度和空間復(fù)雜度均為O(M×N)(M為源字符串的長度，N為目標(biāo)字符串的長度，下同)，限制了編輯距離算法在長字符串處理領(lǐng)域的應(yīng)用。另外，Sten Hjelmqvist[3]算法在空間復(fù)雜度上性能有所提高，即O(2×min(M，N))，但時間復(fù)雜度依然為O(M×N)，算法總體性能并沒有獲得很大提高。

通過研究編輯距離算法的求解過程，發(fā)現(xiàn)存在一條最優(yōu)路徑可以直接求解出兩字符串之間的編輯距離值。通過確定該路徑所在的關(guān)鍵區(qū)域，求解出關(guān)鍵區(qū)域內(nèi)的值，即可沿著最優(yōu)路徑方向求解出最小編輯距離值，除去存在于傳統(tǒng)方法中無需進(jìn)行計算的區(qū)域，縮小問題的求解規(guī)模。從理論上分析以及對實驗結(jié)果進(jìn)行觀察發(fā)現(xiàn)，該方法優(yōu)于傳統(tǒng)的處理方式。

1 編輯距離算法基本思想

編輯距離算法最初由Levenshtein提出，是指把一個字符串轉(zhuǎn)換成另一個字符串所需的最小編輯操作次數(shù)，假設(shè)字符串Sour的長度為m，字符串Dest的長度為n，編輯距離edit(Sour，Dest)是指把Sour字符串變?yōu)镈est字符串所需的最小轉(zhuǎn)化操作次數(shù)，轉(zhuǎn)化操作包括3類:

(1)替換一個字符，如:kitten → sitten，字符“k”替換成“s”;

(2)插入一個字符，如:sittin→ sitting，在字符串的末尾插入“g”;

(3)刪除一個字符，如:sittin→ sitin，在字符串中刪除一個“t”。

編輯距離算法的一般求解策略為采用動態(tài)規(guī)劃方法逐步迭代計算，每一步迭代計算的結(jié)果保存在一個二維數(shù)組。如字符串Sour前i個連續(xù)字符所形成的子字符串同字符串Dest前j個連續(xù)字符所形成的子字符串之間的最小編輯距計算公式如式(1)所示，其中LD[m][n]值即為所求的兩字符串之間的最小編輯距離值。

其中單字符a、b之間的最小編輯距離值為:

由式(1)和(2)可得計算字符串Sour前i個連續(xù)字符同字符串Dest前j個連續(xù)字符之間的最小編輯距離值的遞推關(guān)系式為:

其中j=0表示字符串Sour通過刪除所有字符變?yōu)榭盏哪繕?biāo)字符串Dest，i=0表示字符串Dest可以通過在Sour中插入每一個字符形成;LD[i][j]與LD[i－1][j]相比字符串Sour多了一個字符，因此計算LD[i][j]時字符串Sour需要執(zhí)行一次刪除操作;LD[i][j]與LD[i][j－1]相比字符串Dest多了一個字符，因此計算LD[i][j]時字符串Sour需要執(zhí)行一次添加操作;LD[i][j]與LD[i－1][j－1]相比根據(jù)字符串Sour的第i個字符和字符串Dest的第j個字符是否相同確定是否執(zhí)行一次替換操作。

2 確定最優(yōu)路徑的方法

編輯距離計算方式為迭代遍歷并標(biāo)記二維數(shù)組LD中的每一個位置，基于式(3)若把二維數(shù)組LD展開形成一個二維矩陣，根據(jù)矩陣的描述功能并結(jié)合圖論知識的相關(guān)應(yīng)用，矩陣中每一個位置上的元素表示圖中的一個節(jié)點，則矩陣LD中存在若干條路徑可以從節(jié)點LD[0][0]到達(dá)節(jié)點LD[m][n]，經(jīng)研究發(fā)現(xiàn)存在一條以LD[0][0]為起點、LD[m][n]為終點的最優(yōu)路徑，最優(yōu)路徑由一系列關(guān)鍵節(jié)點組成，關(guān)鍵節(jié)點滿足以下計算規(guī)則:若節(jié)點值r，p，q∈LD時，min(r，p，q)=min(min(r，p)，q);若r=p，則 min(r，p)=r;相鄰兩關(guān)鍵節(jié)點中后一關(guān)鍵節(jié)點的值由前一個關(guān)鍵節(jié)點值求得;最優(yōu)路徑中所有關(guān)鍵節(jié)點之間的鄰接關(guān)系滿足式(3)且關(guān)鍵節(jié)點上的值小于等于與其相鄰的非關(guān)鍵節(jié)點上的值;最優(yōu)路徑中一系列關(guān)鍵節(jié)點所構(gòu)成的序列即可確定最優(yōu)路徑的前進(jìn)方向。如圖1所示計算字符串“sikitting”和“kitten”之間的編輯距離值，包含數(shù)字的每一個單元格表示圖論中的每一個節(jié)點，包含箭頭的單元格為關(guān)鍵節(jié)點。

結(jié)合式(3)和編輯圖[20]的思想，假設(shè)若相鄰兩關(guān)鍵節(jié)點中后一個關(guān)鍵節(jié)點與前一個關(guān)鍵節(jié)點滿足表達(dá)式LD[i][j]=LD[i－1][j]+1時，稱關(guān)鍵節(jié)點KN(i－1，j)向x方向前進(jìn)一步到達(dá)關(guān)鍵節(jié)點KN(i，j)(下標(biāo)(i－1，j)和(i，j)表示圖1中關(guān)鍵節(jié)點的下標(biāo)索引值，下同);若相鄰兩關(guān)鍵節(jié)點中后一個關(guān)鍵節(jié)點與前一個關(guān)鍵節(jié)點滿足表達(dá)式LD[i][j]=LD[i][j－1]+1 時，稱關(guān)鍵節(jié)點KN(i，j－1)向y方向前進(jìn)一步到達(dá)關(guān)鍵節(jié)點KN(i，j);若相鄰兩關(guān)鍵節(jié)點中后一個關(guān)鍵節(jié)點與前一個關(guān)鍵節(jié)點滿足表達(dá)式LD[i][j]=LD[i－1][j－1]+edit(i，j)時，稱關(guān)鍵節(jié)點KN(i－1，j－1)向z方向前進(jìn)一步到達(dá)關(guān)鍵節(jié)點KN(i，j)。

對所有關(guān)鍵節(jié)點遞推應(yīng)用上述方法，發(fā)現(xiàn)形成的最優(yōu)路徑都需要經(jīng)過上述3種方向變換之一，起始節(jié)點為LD[0][0]，結(jié)束節(jié)點為LD[m][n]。因此，可得計算編輯距離的另一種表示形式

圖1 字符串“sikitting”與“kitten”之間的編輯距離圖及其對應(yīng)的最優(yōu)路徑

其中X表示向x方向行進(jìn)的關(guān)鍵點個數(shù)，Y表示向y方向行進(jìn)的關(guān)鍵點個數(shù)，向z方向行進(jìn)的關(guān)鍵點總個數(shù)用Z表示(其中Z=Z0+Z1，Z1表示向z方向行進(jìn)且edit(i，j)=1的關(guān)鍵點個數(shù)，Z0表示向z方向行進(jìn)且edit(i，j)=0的關(guān)鍵點個數(shù))。如圖1所示為計算字符串“sikitting”和“kitten”之間的編輯距離值的過程，其中X=3，Y=0，Z0=5，Z1=1，最終求得的編輯距離值為4。

式(4)基于插入、刪除、替換操作的權(quán)值都是1并結(jié)合矩陣所具有的數(shù)據(jù)結(jié)構(gòu)特征，把LD[][]矩陣抽象成圖論中的一個圖，抽象化后圖中的每一個節(jié)點代表原矩陣中每一個索引位置的元素，圖中每一個節(jié)點具有x方向(豎直方向)、y方向(水平方向)、z方向(斜對角方向)，3個方向分別對應(yīng)于計算編輯距離時的刪除、插入、替換3種基本操作，說明編輯距離值可由最優(yōu)路徑中不同方向的關(guān)鍵節(jié)點總數(shù)確定。如圖1中豎直箭頭(“↓”)表示前進(jìn)方向為x方向，斜對角箭頭(“↘”)表示前進(jìn)方向為z方向，水平箭頭(“→”)表示前進(jìn)方向為y方向。圖中單元格內(nèi)的數(shù)字表示相應(yīng)編輯距離值，符號標(biāo)記d，e，s，i分別表示刪除、不變、替換、插入操作。

假設(shè)最優(yōu)路徑中有兩個關(guān)鍵點分別記為LD[i][j]、LD[k][s](0≤i＜k，0 ≤j＜s)，LD[i][j]在整個路徑中沿x方向連續(xù)行進(jìn)a(0≤a＜k－i)步(非連續(xù)的情況可以轉(zhuǎn)化為連續(xù)，任意位置都可以轉(zhuǎn)換為LD[i][j]開始)后到達(dá)點LD[i+a][j]，從LD[i+a][j]到LD[k][s]需要向z方向行進(jìn)k－i－a步，向y方向行進(jìn) (sk)+(i－j)+a步，且滿足下述關(guān)系:

因此可得變量X、Y、Z、m、n之間存在下述關(guān)系:

將式(6)代入式(4)可得計算LD[m][n]值的表達(dá)式:

或表達(dá)式:

其中LD[m][n]值滿足條件LD[m][n]≤max(m，n)，而每向x方向行進(jìn)1步，則向z方向行進(jìn)機會便減少1，由式(7)可知會使LD的值增加2，為了使LD[m][n]的值盡可能小，需要使z方向中滿足edit(i，j)=0的點數(shù)盡可能多。因此，選擇構(gòu)成最優(yōu)路徑的節(jié)點向x方向行進(jìn)的條件為:向x方向行進(jìn)a步后，新的z方向上的節(jié)點滿足條件edit(i，j)=0的個數(shù)大于2a。因此，為了使LD[m][n]值最小，可求只有當(dāng)X＜m/3時，有可能使關(guān)系式Z0＞2X成立，從而求得關(guān)鍵節(jié)點的坐標(biāo)取值范圍

同理，由式(8)可求關(guān)鍵節(jié)點的坐標(biāo)取值范圍也位于以下區(qū)域

根據(jù)式(9)、(10)構(gòu)造如下區(qū)域

由式(11)形成的區(qū)域由3個子區(qū)域組成，由位置(0，0)沿著近似對角線方向(z方向)到達(dá)位置(m，n)。

為了確定最優(yōu)路徑，使LD[m][n]值盡可能小，定義符號＜a，b＞表示路徑中先后沿著方向a和方向b通過相鄰兩節(jié)點，最優(yōu)路徑的前進(jìn)方向可以為＜x，x＞、＜y，y＞、＜z，z＞、＜x，z＞、＜y，z＞、＜z，x＞、＜z，y＞幾種情況，但不能為＜x，y＞和＜y，x＞2種情況，即不能出現(xiàn)相鄰兩節(jié)點之間前一節(jié)點為x方向，后一節(jié)點為y方向，或者相反的情況。x與y相鄰的原理為:先執(zhí)行一次刪除操作(x方向)，然后執(zhí)行一次添加操作(y方向)，或者相反的操作，整個過程執(zhí)行了兩次操作，可以用一次替換操作代替(z方向)。因此，可得性質(zhì):最優(yōu)路徑中不能出現(xiàn)路徑的前進(jìn)方向為x方向與y方向相鄰的情況。

3 確定最優(yōu)路徑所在的關(guān)鍵區(qū)域

綜合第2節(jié)討論可知，在矩陣區(qū)域LD中存在一條由一系列關(guān)鍵節(jié)點序列所構(gòu)成的最優(yōu)路徑，通過最優(yōu)路徑可以快速地直接求解出編輯距離值LD[m][n]。然而，基于Levenshtein編輯距離算法的基本思想關(guān)鍵節(jié)點上的值受其相鄰的非關(guān)鍵節(jié)點影響，因此通過確定最優(yōu)路徑所在的關(guān)鍵區(qū)域，保證關(guān)鍵節(jié)點上的值只受關(guān)鍵區(qū)域內(nèi)非關(guān)鍵節(jié)點值的影響，降低問題的求解規(guī)模，由式(9)、(10)可知，由一系列關(guān)鍵節(jié)點所形成的最優(yōu)路徑同時通過由公式(9)、(10)所構(gòu)成的區(qū)域。由此，可得性質(zhì):最優(yōu)路徑沿著由公式(11)所形成的近似對角線方向且必通過由式(11)所構(gòu)成的區(qū)域范圍。

基于最優(yōu)路徑通過由式(11)所確定區(qū)域的邊界問題的解決辦法為添加輔助區(qū)域，確保由式(11)所確定區(qū)域的各邊界完全落在該輔助區(qū)域范圍內(nèi)，使最優(yōu)路徑完全位于輔助區(qū)域范圍，輔助區(qū)域所圍成的范圍即為最優(yōu)路徑所在的關(guān)鍵區(qū)域。

添加輔助區(qū)域的方式分為3種情況，即X=Y、X＞Y、X＜Y。圖2～4描述3種不同情形添加輔助區(qū)域的不同方式，采用深色顏色標(biāo)記由式(11)所形成的區(qū)域范圍，淺色顏色標(biāo)記添加的輔助區(qū)域范圍，深色區(qū)域剛好落在輔助區(qū)域范圍內(nèi)。

圖2所示為X=Y情形，這種是規(guī)則形式，輔助區(qū)域的左邊界和右邊界由起始位置沿著斜對角線方向(z方向)前進(jìn)到達(dá)終點位置。圖3所示為X＞Y情形，這種是不規(guī)則形式，為確保深色陰影部分的所有邊界都落在輔助區(qū)域所圍成的范圍內(nèi)，輔助區(qū)域的左邊界和右邊界需以對齊各子區(qū)域起始位置沿著x方向移動|X－Y|步，剩余輔助區(qū)域的左邊界和右邊界沿著z方向前進(jìn)。圖4所示為X＜Y情形，這種是不規(guī)則形式，為確保深色陰影部分的所有邊界都落在輔助區(qū)域所圍成的范圍內(nèi)，各子區(qū)域起始位置處的輔助區(qū)域的左邊界和右邊界需沿著y方向移動|Y－X|步，剩余輔助區(qū)域的左邊界和右邊界沿著z方向前進(jìn)。

圖2 X=Y形式的關(guān)鍵區(qū)域

圖3 X＞Y形式的關(guān)鍵區(qū)域

圖4 X＜Y形式的關(guān)鍵

最后，由圖2～4所示的淺色區(qū)域即為添加的輔助區(qū)域，淺色區(qū)域和深色區(qū)域共同組成的部分即為最終所求的關(guān)鍵區(qū)域。

4 算法描述

對最優(yōu)路徑所在關(guān)鍵區(qū)域進(jìn)行研究可知，在關(guān)鍵區(qū)域內(nèi)存在一條最優(yōu)路徑可以快速地直接求得兩字符串之間的編輯距離值。最優(yōu)路徑中相鄰兩關(guān)鍵節(jié)點之間后一個關(guān)鍵節(jié)點的值由其前一個關(guān)鍵節(jié)點的值求得，區(qū)域內(nèi)其他非關(guān)鍵節(jié)點的值作為關(guān)鍵節(jié)點的參照與關(guān)鍵節(jié)點上的值做比較，并不直接參與最優(yōu)路徑上值地計算。關(guān)鍵區(qū)域確保最優(yōu)路徑上所有關(guān)鍵節(jié)點都位于該區(qū)域內(nèi)，因此只要求得關(guān)鍵區(qū)域內(nèi)所有節(jié)點的值，即可求兩字符串之間的最小編輯距離值。算法用二維數(shù)組LD[1…X][1…2Y]保存關(guān)鍵區(qū)域內(nèi)所有節(jié)點的計算結(jié)果，整個關(guān)鍵區(qū)域按x方向長度為X、y方向長度為2Y劃分為各個子區(qū)域，子區(qū)域個數(shù)N(sub－area)≥3。對所有子區(qū)域采用動態(tài)規(guī)劃方法進(jìn)行迭代計算，經(jīng)過最后一步計算操作LD[][]中所保存的結(jié)果即為所求的最小編輯距離值。關(guān)于關(guān)鍵區(qū)域邊界節(jié)點的求值問題，根據(jù)添加輔助區(qū)域，右邊界沿著y方向向右延伸，左邊界沿著x方向向下延伸。由性質(zhì)1知，關(guān)鍵區(qū)域右邊界節(jié)點值可由沿著y方向或者z方向前進(jìn)的節(jié)點求得，關(guān)鍵區(qū)域左邊界節(jié)點值可由沿著x方向或者z方向前進(jìn)的節(jié)點求得。核心算法如下，表示關(guān)鍵區(qū)域的每一個子區(qū)域的求解過程。

通過迭代計算關(guān)鍵區(qū)域內(nèi)所有子區(qū)域的值，最后求得的值即為兩字符串之間的編輯距離值。

5 算法效率分析

設(shè)源字符串與目標(biāo)字符串的長度分別為m和n，根據(jù)關(guān)鍵區(qū)域的結(jié)構(gòu)特點，基于最優(yōu)路徑策略的關(guān)鍵區(qū)域算法在計算編輯距離值過程中所用空間為(m/3)×(2n/3)，即該算法與原算法相比在空間改進(jìn)方面由(m×n)變?yōu)?(2/9)×(m×n))，較原算法提升了(7/9);所用時間按基本循環(huán)操作次數(shù)進(jìn)行估量使原算法的問題求解規(guī)模由(m×n)變?yōu)?m/3)×(2n/3)×3，即時間效率提升方面變?yōu)?(2/3)×(m×n))，較原算法提升(1/3)，可以看出改進(jìn)后的算法在時間上和空間上都優(yōu)于Levenshtein算法。

6 實驗結(jié)果與分析

為驗證基于最優(yōu)路徑策略的關(guān)鍵區(qū)域算法較Levenshtein算法在時間和空間性能上的提高，選擇環(huán)境為Dell OptiPlex 790，CPU 3.10GHZ，內(nèi)存8GB條件下進(jìn)行實驗。實驗數(shù)據(jù)采用從字符個數(shù)范圍為200～20000抽出100組不同長度的源字符串和目標(biāo)字符串。

圖5為基于最優(yōu)路徑策略的關(guān)鍵區(qū)域算法和Levenshtein算法分別計算不同長度字符串之間的編輯距離值所用的時間對比情況(時間單位:秒)，算法用一個二維數(shù)組保存中間結(jié)果。圖中不同算法名稱簡寫所代表的具體算法類型說明如下。

CA-I算法:基于最優(yōu)路徑策略的關(guān)鍵區(qū)域算法(critical area)，采用一個二維數(shù)組保存求解結(jié)果;

LV算法:Levenshtein[1]算法，采用一個二維數(shù)組保存求解結(jié)果。

由圖5可知，當(dāng)字符串長度達(dá)到一定值時LV算法所用時間大于CA-I算法所用時間。

圖5 CA-I算法和LV算法隨著字符串長度變化所用時間對比圖

圖6 CA-II算法和SH算法隨著字符串長度變化所用時間對比圖

Sten Hjelmqvist提出采用兩個一維數(shù)組分別保存每一次迭代求解的結(jié)果，使Levenshtein算法所用空間減少為2×min(m，n)，即空間復(fù)雜度為O(2×min(m，n))。基于Sten Hjelmqvist算法思想采用兩個一維數(shù)組分別對基于最優(yōu)路徑策略的關(guān)鍵區(qū)域算法和Levenshtein算法進(jìn)行改進(jìn)，對比分析計算不同長度字符串之間的編輯距離值所用的時間(時間單位:秒)，實驗環(huán)境和實驗數(shù)據(jù)與圖5一致，實驗結(jié)果如圖6所示。圖中不同算法名稱簡寫所代表的具體算法類型說明如下:

CA-II算法:基于最優(yōu)路徑策略的關(guān)鍵區(qū)域算法(critical area)，采用2個一維數(shù)組分別保存前一行和當(dāng)前行的求解結(jié)果;

SH算法:Sten Hjelmqvist算法，基于Levenshtein算法采用2個一維數(shù)組分別保存前一行和當(dāng)前行的求解結(jié)果。

由圖6可知，當(dāng)字符串長度達(dá)到一定值時SH算法所用時間大于CA-II算法所用時間。

針對圖5和圖6的實驗結(jié)果進(jìn)行分析:設(shè)LV算法、SH算法、CA-I算法、CA-II算法所用時間分別為t(LV)、t(SH)、t(CA-I)、t(CA-II)。LV算法和SH算法需要遍歷矩陣LD[m][n]整個區(qū)域，問題求解規(guī)模為(m×n);CA-I算法和CA-II算法只需遍歷矩陣LD[m][n]中的關(guān)鍵區(qū)域，問題求解規(guī)模降低為((2/3)×(m×n))，因此t(LV)＞t(CA-I)，t(SH)＞t(CA-II)。上述4種算法的問題求解規(guī)模和空間需求差異如表1所示。

表1 不同算法時間復(fù)雜度和空間復(fù)雜度對比

針對圖5和圖6的實驗結(jié)果對比分析可得基于最優(yōu)路徑策略的關(guān)鍵區(qū)域算法CA-I、CA-II較傳統(tǒng)針對矩陣所有區(qū)域進(jìn)行遍歷的算法LV、SH在時間性能上都有所提高，對比不同算法所提高的時間性能用時間加速比(Time Speedup Rate)描述。定義時間加速比的計算公式為(t()為時間函數(shù)，A和B表示2種不同的算法)

算法A較算法B時間加速比

圖5、6中實驗采用100組不同的實驗數(shù)據(jù)，因此計算時間加速比的平均值作為衡量不同算法的時間性能對比情況，計算公式為(TSRi為第i組數(shù)據(jù)的時間加速比，n為總的數(shù)據(jù)組數(shù))

對應(yīng)算法的時間平均加速比如圖7所示。

由圖7可看出，基于最優(yōu)路徑策略的關(guān)鍵區(qū)域算法較傳統(tǒng)算法在時間性能上的提高超過20%，理想情況下超過30%。因為基于最優(yōu)路徑策略的關(guān)鍵區(qū)域算法的問題求解規(guī)模為((2/3)×(m×n))，是傳統(tǒng)算法的2/3(傳統(tǒng)算法的問題求解規(guī)模為(m×n))。

圖7 相應(yīng)算法時間提高對比圖

圖8 LV算法和SH算法隨著字符串長度變化所用時間對比圖

圖9 CA-I算法和CA-II算法隨著字符串長度變化所用時間對比圖

另外通過分析圖8和圖9中的實驗結(jié)果可以看出算法的執(zhí)行時間t(LV)≥t(SH)，t(CA-I)≤t(CA-II)。從理論上分析LV算法和SH算法需遍歷矩陣LD[m][n]的整個區(qū)域并計算相應(yīng)位置上的值，基于LV算法是構(gòu)造一個范圍大小為m×n的矩陣區(qū)域并遍歷計算該區(qū)域內(nèi)所有位置上的值，需要分配的物理內(nèi)存大小為m×n;而基于SH算法是構(gòu)造兩個長度為n的線性區(qū)域，需要分配的物理內(nèi)存大小為2×n，但每計算完一次線性區(qū)域內(nèi)所有位置上的值后都需要針對線性區(qū)域內(nèi)每一個位置上的值執(zhí)行一次復(fù)制操作[3]。CA-I算法和CA-II算法只需遍歷并計算矩陣區(qū)域LD[m][n]中關(guān)鍵區(qū)域內(nèi)各個位置上的值，CA-I算法需要分配的物理內(nèi)存大小為X×2×Y(X?m，Y?n，符合“?”表示遠(yuǎn)小于，下同)，遍歷計算方式同LV算法;CA-II算法需要分配的物理內(nèi)存大小為2×Y(Y?n)，遍歷計算方式同SH算法。因此基于內(nèi)存分配和CPU時鐘頻率因素而出現(xiàn)了算法執(zhí)行時間t(LV)≥t(SH)和t(CA-I)≤t(CA-II)2種不一致的情形。

7 結(jié)束語

在研究傳統(tǒng)編輯距離算法的基礎(chǔ)上提出一種改進(jìn)方法，即在原算法進(jìn)行計算過程中所形成的矩陣區(qū)域內(nèi)存在一條最優(yōu)路徑，通過最優(yōu)路徑可以直接求出兩字符串之間的編輯距離。然而，基于Levenshtein編輯距離算法的基本思想最優(yōu)路徑中關(guān)鍵節(jié)點上的值受其相鄰的非關(guān)鍵節(jié)點的影響，因此，提出基于最優(yōu)路徑策略方法的關(guān)鍵區(qū)域算法思想計算兩字符串之間的編輯距離，該方法雖然沒有僅僅基于最優(yōu)路徑的方法高效，但與傳統(tǒng)編輯距離算法相比縮小了整個問題的求解規(guī)模，適用于求解長字符串之間的編輯距離問題，提高了問題的求解速度。針對算法特點該算法對源字符串長度大于等于目標(biāo)字符串長度且都大于或等于3的情形所獲得的處理結(jié)果更理想，未來的研究工作可從如何確定僅僅通過最優(yōu)路徑即可計算兩字符串之間的編輯距離入手并實現(xiàn)構(gòu)造最優(yōu)路徑的并行化工作，進(jìn)一步優(yōu)化編輯距離算法。此外，所描述的改進(jìn)思想同樣適用于圖論中使用動態(tài)規(guī)劃方法求解一般問題地應(yīng)用，比如最優(yōu)分配問題和背包問題等。

[1] Levenshtein V I.Binary codes capable of correcting deletions，insertions and reversals[C].Soviet physics doklady，1966，10:707.

[2] Wagner R A，Lowrance R.An extension of the string-to-string correction problem[J].Journal of the ACM(JACM)，1975，22(2):177－183.

[3] Hjelmqvist Sten.Fast，memory efficient Levenshtein algorithm[EB/OL].http://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm，2012.

[4] 趙作鵬，尹志民，王潛平，等.一種改進(jìn)的編輯距離算法及其在數(shù)據(jù)處理中的應(yīng)用[J].計算機應(yīng)用，2009，29(2):424－426.

[5] 吳玲，秦志光，石竑松，等.分段處理的1/p概率字符串匹配[J].計算機科學(xué)，2008，35(7):91－95.

[6] Monge A E，Elkan C P.Efficient domain-independent detection of approximately duplicate database records[C].Proc.of the ACM-SIGMOD Workshop on Research Issues in on Knowledge Discovery and Data Mining，1997.

[7] Hernández M A，Stolfo S J.The merge/purge problem for large databases[C].ACM SIGMOD Record.ACM，1995，24(2):127－138.

[9] 董國卿，童維勤.數(shù)據(jù)庫元數(shù)據(jù)的自動語義標(biāo)注[J].計算機科學(xué)，2012，(3).

[10] Cohen W W.Data integration using similarity joins and a word-based information representation language[J].ACM Transactions on Information Systems(TOIS)，2000，18(3):288－321.

[11] Bakker D，Müller A，Velupillai V，et al.Adding typology to lexicostatistics:a combined approach to language classification[J].Linguistic Typology，2009，13(1):169－181.

[12] Holman E W，Wichmann S，Brown C H，et al.Advances in automated language classification[J].Quantitative Investigations In Theoretical Linguistics(QITL3)，2008:40.

[13] Petroni F，Serva M.Measures of lexical distance between languages[J].Physica A:Statistical Mechanics and its Applications，2010，389(11):2280－2283.

[14] Wichmann S，Holman E W，Bakker D，et al.Evaluating linguistic distance measures[J].Physica A:Statistical Mechanics and its Applications，2010，389(17):3632－3639.

[15] Gooskens C，Heeringa W.Perceptive evaluation of Levenshtein dialect distance measurements using Norwegian dialect data[J].Language variation and Change，2004，16(3):189－207.

[16] Beijering K，Gooskens C，Heeringa W.Predi-cting intelligibility and perceived linguistic distance by means of the Levenshtein algorithm[J].Linguistics in the Netherlands，2008，25(1):13－24.

[17] Brill E，Moore R C.An improved error model for noisy channel spelling correction[C].Proceedings of the 38th Annual Meeting on Association for Computational Linguistics.Association for Computational Linguistics，2000:286－293.

[18] R Durbin.Biological sequence analysis:probabi-listic models of proteins and nucleic acids[M].Cambridge university press，1998.

[19] Patil N，Toshniwal D，Garg K.Genome data classification based on fuzzy matching[J].CSI Transactions on ICT，2013，1(1):9－28.

[20] Myers E W.An O(ND)difference algorithm and its variations[J].Algorithmica，1986，1(1－4):251－26.