編輯距離算法的優(yōu)化與實(shí)現(xiàn)

《編輯距離算法的優(yōu)化與實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、編輯距離算法的優(yōu)化與實(shí)現(xiàn)摘要：在分析基于動(dòng)態(tài)規(guī)劃的編輯距離算法對(duì)文本相似度計(jì)算的不足的基礎(chǔ)上，利用數(shù)據(jù)結(jié)構(gòu)在空間效率和時(shí)間效率上優(yōu)化該算法、采用中文分詞的思想優(yōu)化和改善該算法的時(shí)間效率和準(zhǔn)確率，克服了原有的基于動(dòng)態(tài)規(guī)劃的計(jì)算方法所具有的效率低、準(zhǔn)確率低、耗內(nèi)存高的缺點(diǎn)。通過多種優(yōu)化方案的實(shí)驗(yàn)測(cè)試和分析，結(jié)果表明優(yōu)化后的算法取得了很好的準(zhǔn)確率和時(shí)空效率，更好的用于文本相似度計(jì)算。關(guān)鍵詞：編輯距離算法；文本相似度計(jì)算；算法優(yōu)化；動(dòng)態(tài)規(guī)劃1引言文本相似度的計(jì)算在信息檢索、文本分類、知識(shí)挖掘、網(wǎng)頁去重、問答系統(tǒng)等諸多領(lǐng)域有著極為廣泛的應(yīng)用，長(zhǎng)期以來一直是研究的熱點(diǎn)和難點(diǎn)。人們?cè)?/p>

2、文本相似度計(jì)算中使用編輯距離算法，但該方法單純以字為單位計(jì)算各個(gè)字符之間的編輯距離，插入刪除替換三種基本操作的代價(jià)值的方法不夠明確合理，從而使計(jì)算結(jié)果存在一定的偏差。故對(duì)傳統(tǒng)的文本相似度檢測(cè)編輯距離算法進(jìn)行優(yōu)化和改善，提出了一種基于改進(jìn)編輯距離和中文分詞相融合的計(jì)算文本相似度的方法，使優(yōu)化改善后的算法具有較高的準(zhǔn)確率和效率、較低的存儲(chǔ)空間，更符合文本相似度計(jì)算的要求，有效提高文本相似度算法的效率和準(zhǔn)確性，使文本相似度計(jì)算的性能進(jìn)一步改善。2編輯距離算法4.3.1編輯距離定義編輯距離又稱Levenshtein距離（也叫做EditDistance），是由俄國科學(xué)家Vladi

3、mirLevenshtein于1965年在文獻(xiàn)[1]中提出的，是一種常用的距離函數(shù)度量方法，在多個(gè)領(lǐng)域特別是文本相似度檢測(cè)得到了廣泛的應(yīng)用。編輯距離是指兩系列字符串之間只能通過插入、刪除和替換三種基本操作把源字符串（S）轉(zhuǎn)換成目標(biāo)字符串（T）所需的最少基本操作次數(shù)。編輯距離值越大，則相似度越小。214.3.1編輯距離算法原理對(duì)于求兩個(gè)字符串之間的編輯距離實(shí)際上可以轉(zhuǎn)化為一個(gè)求最優(yōu)解的問題，可以利用動(dòng)態(tài)規(guī)劃的思想[2]來計(jì)算，計(jì)算原理的步驟如下表2-1所示：表2-1編輯距離算法原理的計(jì)算步驟步驟描述1設(shè)置n為源字符串s的長(zhǎng)度。設(shè)置m為目標(biāo)字符串t的長(zhǎng)度。如果n等于0，返回

4、m并退出。如果m等于0，返回n并退出。構(gòu)造一個(gè)矩陣d[m+1,n+1]含有0..m行和0..n列。2初始化矩陣第一行0..?。初始化矩陣第一列0..m。3檢查s(ifrom1ton)中的每個(gè)字符。4檢查t(jfrom1tom)中的每個(gè)字符。5如果s[i]等于t[j]，則編輯代價(jià)cost為0；如果s[i]不等于t[j]，則編輯代價(jià)cost為1。6設(shè)置矩陣單元格d[i,j]的值為下面的最小值:a.正上方單元格的值1:d[i-1,j]+1.b.左邊單元格的值加1:d[i,j-1]+1.c.對(duì)角線單元格的值加上編輯代價(jià)cost的值:d[i-1,j-1]+cost.7在完成迭代(

5、3,4,5,6)之后，d[m,n]便是編輯距離的值。本小節(jié)將演示如何計(jì)算源字符串"GUMBO"和目標(biāo)字符串"GAMBOL"兩個(gè)字符串之間的Levenshtein距離，計(jì)算步驟如下：步驟1、2步驟3、6，當(dāng)i=1步驟3、6，當(dāng)i=221??GUMBO?012345G1??A2??M3??B4??O5??L6????GUMBO?012345G10??A21??M32??B43??O54??L65????GUMBO?012345G101??A211??M322??B433??O544??L655??步驟3、6，當(dāng)i=3步驟3、6，當(dāng)i=4步驟3、6，當(dāng)i=5??GUMBO?0

6、12345G1012??A2112??M3221??B4332??O5443??L6554????GUMBO?012345G10123?A21123?M32212?B43321?O54432?L65543???GUMBO?012345G101234A211234M322123B433212O544321L655432步驟7，編輯距離是矩陣右下角的值，d[m,n]=2；源字符串"GUMBO"變換為目標(biāo)字符串"GAMBOL"的過程，直觀可看出的，即通過將"A"替換為"U"，并在末尾追加"L"字符，這跟計(jì)算的結(jié)果一致。4.3.1編輯距離以及文本相似度計(jì)算編輯距離D（S,T）的

7、計(jì)算方法如下所述。首先假設(shè)Dij=D(s1…si,,t1…tj)，0≤i≤m,0≤j≤n,Dij表示從s1…si到t1…tj的編輯距離，那么（m+1）×(n+1)階矩陣Dij可通過下面的（1）式計(jì)算得到：0i=0且j=0;Di-1j-1+(ifsi=tjthen0else1);Dij=MinDi-1,j+1;i>0或j>0；(1)式Di,j-1+1;21(1)式包含刪除、插入、替換三種操作，該算法是從兩字符串的左邊開始比較，記錄已經(jīng)比較過的編輯距離，然后進(jìn)一步得到下一個(gè)字符位置時(shí)的編輯距離。矩陣Dij能夠通過從D00逐步逐列計(jì)算獲取，最終