基于最優路徑策略方法快速計算字符串編輯距離

王遠超，安俊秀，程芃森，王 鵬

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

0 引言

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

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

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

通過研究編輯距離算法的求解過程，發現存在一條最優路徑可以直接求解出兩字符串之間的編輯距離值。通過確定該路徑所在的關鍵區域，求解出關鍵區域內的值，即可沿著最優路徑方向求解出最小編輯距離值，除去存在于傳統方法中無需進行計算的區域，縮小問題的求解規模。從理論上分析以及對實驗結果進行觀察發現，該方法優于傳統的處理方式。

1 編輯距離算法基本思想

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

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

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

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

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

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

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

其中j=0表示字符串Sour通過刪除所有字符變為空的目標字符串Dest，i=0表示字符串Dest可以通過在Sour中插入每一個字符形成;LD[i][j]與LD[i－1][j]相比字符串Sour多了一個字符，因此計算LD[i][j]時字符串Sour需要執行一次刪除操作;LD[i][j]與LD[i][j－1]相比字符串Dest多了一個字符，因此計算LD[i][j]時字符串Sour需要執行一次添加操作;LD[i][j]與LD[i－1][j－1]相比根據字符串Sour的第i個字符和字符串Dest的第j個字符是否相同確定是否執行一次替換操作。

2 確定最優路徑的方法

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

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

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

圖1 字符串“sikitting”與“kitten”之間的編輯距離圖及其對應的最優路徑

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

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

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

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

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

或表達式:

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

同理，由式(8)可求關鍵節點的坐標取值范圍也位于以下區域

根據式(9)、(10)構造如下區域

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

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

3 確定最優路徑所在的關鍵區域

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

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

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

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

圖2 X=Y形式的關鍵區域

圖3 X＞Y形式的關鍵區域

圖4 X＜Y形式的關鍵

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

4 算法描述

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

通過迭代計算關鍵區域內所有子區域的值，最后求得的值即為兩字符串之間的編輯距離值。

5 算法效率分析

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

6 實驗結果與分析

為驗證基于最優路徑策略的關鍵區域算法較Levenshtein算法在時間和空間性能上的提高，選擇環境為Dell OptiPlex 790，CPU 3.10GHZ，內存8GB條件下進行實驗。實驗數據采用從字符個數范圍為200～20000抽出100組不同長度的源字符串和目標字符串。

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

CA-I算法:基于最優路徑策略的關鍵區域算法(critical area)，采用一個二維數組保存求解結果;

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

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

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

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

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

CA-II算法:基于最優路徑策略的關鍵區域算法(critical area)，采用2個一維數組分別保存前一行和當前行的求解結果;

SH算法:Sten Hjelmqvist算法，基于Levenshtein算法采用2個一維數組分別保存前一行和當前行的求解結果。

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

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

表1 不同算法時間復雜度和空間復雜度對比

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

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

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

對應算法的時間平均加速比如圖7所示。

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

圖7 相應算法時間提高對比圖

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

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

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

7 結束語

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

[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].計算機應用，2009，29(2):424－426.

[5] 吳玲，秦志光，石竑松，等.分段處理的1/p概率字符串匹配[J].計算機科學，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] 董國卿，童維勤.數據庫元數據的自動語義標注[J].計算機科學，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.