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

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)。通過(guò)多種優(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ì)算在信息檢索、文本分類(lèi)、知識(shí)挖掘、網(wǎng)頁(yè)去重、問(wèn)答系統(tǒng)等諸多領(lǐng)域有著極為廣泛的應(yīng)用，長(zhǎng)期以來(lái)一直是研究的熱點(diǎn)和難點(diǎn)。人們?cè)谖谋鞠嗨贫扔?jì)算中使用

2、編輯距離算法，但該方法單純以字為單位計(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 編輯距離定義編輯距離又稱(chēng)Levenshtein距離（也叫做Edit Distance），是由俄國(guó)科學(xué)家Vladimir Levenshtein于196

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

4、有0.m行和0.n列。2初始化矩陣第一行0.ñ。初始化矩陣第一列0.m。3檢查 s (i from 1 to n) 中的每個(gè)字符。4檢查 t (j from 1 to m) 中的每個(gè)字符。5如果 si 等于 tj，則編輯代價(jià)cost為0；如果 si 不等于 tj，則編輯代價(jià)cost為1。6設(shè)置矩陣單元格d i,j 的值為下面的最小值:a. 正上方單元格的值1: di-1,j + 1.b. 左邊單元格的值加1: di,j-1 + 1.c. 對(duì)角線單元格的值加上編輯代價(jià)cost的值: di-1,j-1 + cost.7在完成迭代 (3, 4, 5, 6) 之后，dm,n便是編輯距離的值。

5、本小節(jié)將演示如何計(jì)算源字符串"GUMBO"和目標(biāo)字符串"GAMBOL"兩個(gè)字符串之間的Levenshtein距離，計(jì)算步驟如下：步驟1、2 步驟3、6，當(dāng)i=1 步驟3、6，當(dāng)i=2  GUMBO 012345G1  A2  M3  B4  O5  L6    GUMBO 012345G10  A21  M32  B4

6、3  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 012345G1012  A2112  M3221  B4332  O54

7、43  L6554    GUMBO 012345G10123 A21123 M32212 B43321 O54432 L65543   GUMBO 012345G101234A211234M322123B433212O544321L655432步驟7，編輯距離是矩陣右下角的值，dm,n=2；源字符串"GUMBO"變換為目標(biāo)字符串"GAMBOL"的過(guò)程，直觀可看出的，即通過(guò)將"A&quo

8、t;替換為"U"，并在末尾追加"L"字符，這跟計(jì)算的結(jié)果一致。4.3.3 編輯距離以及文本相似度計(jì)算編輯距離D（S,T）的計(jì)算方法如下所述。首先假設(shè)Dij=D(s1si, t1tj)，0im,0jn, Dij表示從s1si到t1tj的編輯距離，那么（m+1）×(n+1)階矩陣Dij可通過(guò)下面的（1）式計(jì)算得到： 0 i=0且j=0;Di-1 j-1+(if si= tj then 0 else 1); Dij= Min Di-1,j+1; i>0或j>0； (1)式 Di,j-1+1; (1)式包含刪除、插入、替換三種操作，該算法是

9、從兩字符串的左邊開(kāi)始比較，記錄已經(jīng)比較過(guò)的編輯距離，然后進(jìn)一步得到下一個(gè)字符位置時(shí)的編輯距離。矩陣Dij能夠通過(guò)從D00逐步逐列計(jì)算獲取，最終Dmn表示D(S，T)的值，即S和T的編輯距離。文本相似度計(jì)算3：編輯距離越大，相似度越小。假設(shè)源字符串S與目標(biāo)字符串T長(zhǎng)度的最大值為L(zhǎng)max，編輯距離為L(zhǎng)D，相似度為SI，則相似度SI的計(jì)算如（2）式所示。SI=1-LD/Lmax (2)式4.3.4 編輯距離算法核心代碼public int LevenshteinDistance(string strs1, string strs2) char str1=strs1.ToCharArray(); ch

10、ar str2=strs2.ToCharArray(); int i,j,temp; if (str1.Length = 0) temp = str2.Length; if (str2.Length = 0) temp = str1.Length; int, dist = new intstr1.Length + 1, str2.Length + 1; for(i=0;i<=str1.Length;i+) disti,0=i; for(i=0;i<=str2.Length;i+) dist0,i=i; for(i=1;i<=str1.Length;i+) for(j=1;j&

11、lt;=str2.Length;j+) if( str1i-1 = str2j-1) disti,j=disti-1,j-1; else disti, j = LowerOfThree(disti, j - 1, disti - 1, j-1, disti - 1, j) + 1; temp = diststr1.Length, str2.Length; return temp;4.3.5 編輯距離算法分析假設(shè)m, n分別表示源字符串S和目標(biāo)字符串T的長(zhǎng)度，則上述的基于動(dòng)態(tài)規(guī)劃的編輯距離算法，其算法的空間復(fù)雜度為O（mn），時(shí)間復(fù)雜度為O（mn）。盡管編輯距離算法在文本相似度檢測(cè)方面具有一定的

12、優(yōu)勢(shì)，具有簡(jiǎn)單易于計(jì)算，并有一定的正確率，但仍然存在一些問(wèn)題。（1）此編輯距離算法忽略了序列長(zhǎng)度對(duì)編輯距離產(chǎn)生的影響，沒(méi)有考慮到算法所需的內(nèi)存，因而造成所耗內(nèi)存較大。（2）單純以字為單位計(jì)算各個(gè)字符之間的編輯距離，計(jì)算出來(lái)的距離只是文字表面的距離，并沒(méi)有充分考慮詞語(yǔ)的概念，使得計(jì)算結(jié)果的語(yǔ)義準(zhǔn)確率不高，特別是對(duì)中文的檢測(cè)時(shí)常常得不到滿意的結(jié)果。針對(duì)以上兩個(gè)問(wèn)題，下文提出了幾種優(yōu)化方案，分別是基于算法結(jié)構(gòu)的內(nèi)部調(diào)整優(yōu)化以及基于詞語(yǔ)相似度的文本計(jì)算，通過(guò)大量的實(shí)驗(yàn)測(cè)試證明了可降低計(jì)算所耗的存儲(chǔ)空間，提高了算法的效率和準(zhǔn)確率。 3 改進(jìn)編輯距離算法3.1 空間復(fù)雜度優(yōu)化經(jīng)過(guò)對(duì)上面的傳統(tǒng)編輯距離算法計(jì)

13、算過(guò)程的分析，發(fā)現(xiàn)算法中作為存儲(chǔ)的二維矩陣，在每一個(gè)循環(huán)中，其實(shí)只有一行的數(shù)據(jù)參與了計(jì)算，之前的數(shù)據(jù)行都不再參與計(jì)算了。因此，從這個(gè)出發(fā)點(diǎn)入手，對(duì)算法結(jié)構(gòu)進(jìn)行調(diào)整，將二維數(shù)組改為兩個(gè)一維數(shù)組。經(jīng)測(cè)試，計(jì)算結(jié)果和速度沒(méi)有太大的差異。但空間復(fù)雜度減少了很多，改進(jìn)后空間復(fù)雜度降為：O（min(m,n）。設(shè)置n為源字符串s的長(zhǎng)度，m為目標(biāo)字符串t的長(zhǎng)度。我們不妨設(shè)n<m，即源字符串s的長(zhǎng)度較小，那么空間復(fù)雜度優(yōu)化的編輯距離算法步驟如表3-1： 表3-1 空間復(fù)雜度優(yōu)化的編輯距離算法步驟步驟描述1設(shè)置n為源字符串s的長(zhǎng)度。設(shè)置m為目標(biāo)字符串t的長(zhǎng)度。如果n等于0，返回m并退出。如果m等于0，返回n

14、并退出。構(gòu)造兩個(gè)一維數(shù)組v0n+1 和v1n+1，串聯(lián)0.n之間所有的元素。2初始化v0 to 0.n。3檢查 t (j from 1 to m) 中的每個(gè)字符。4檢查 s (i from 1 to n) 中的每個(gè)字符。5如果 si 等于 tj，則編輯代價(jià)cost為0；如果 si 不等于 tj，則編輯代價(jià)cost為1。6設(shè)置一維數(shù)組單元格v1i 的值為下面的最小值:a. 正上方單元格的值1: v0i + 1.b. 左邊單元格的值加1: v1i-1 + 1.c. 對(duì)角線單元格的值加上編輯代價(jià)cost的值: v0i-1 + cost.7在完成迭代 (3, 4, 5, 6) 之后，v1n便是編輯距離

15、的值。本小節(jié)仍以源字符串"GUMBO"和目標(biāo)字符串"GAMBOL"來(lái)演示如何計(jì)算這兩個(gè)字符串之間的Levenshtein距離，計(jì)算步驟如下：步驟1、2 步驟3、6，當(dāng)i=1 步驟3、6，當(dāng)i=2   GUMBOV0 012345V1G    A  M  B  O  L     GUMBOv0 012345V1G1012 34A&

16、#160; M  B  O  L     GUMBO  012345v0G101234V1A211234M  B  O  L  步驟3、6，當(dāng)i=3 步驟3、6，當(dāng)i=4 步驟3、6，當(dāng)i=5   GUMBO  012345G101234V0A211234V1M322123B  O  L&

17、#160;    GUMBO  012345G101234A211234V0M322123V1B433212O L    GUMBO  012345G101234A211234M322123V0B433212V1O544321L步驟3、6，當(dāng)i=6   GUMBO  012345G101234A211234M322123B433212V0O544321V1L655432步驟7，右下角的值便是編輯距離的值，v1n=2；

18、傳統(tǒng)的編輯距離算法會(huì)創(chuàng)建一個(gè)矩陣dm+1,n+1,但此經(jīng)過(guò)優(yōu)化的算法將會(huì)創(chuàng)建兩個(gè)一維數(shù)組v0n+1 和v1n+1，其計(jì)算結(jié)果沒(méi)有發(fā)生變化，但內(nèi)存占用更少，其空間復(fù)雜度可為兩個(gè)字符串長(zhǎng)度的最小值O(min(m，n)。在經(jīng)過(guò)空間復(fù)雜度優(yōu)化的編輯距離算法，其編輯步數(shù)一樣，因而相應(yīng)的文本相似度計(jì)算的結(jié)果也一樣。編輯距離算法的空間復(fù)雜度優(yōu)化核心代碼如下：public int LevenshteinDistance(string strs1, string strs2) char str1 = strs1.ToCharArray(); char str2 = strs2.ToCharArray(); in

19、t i, j,temp; if (str1.Length = 0) temp = str2.Length; if (str2.Length = 0) temp = str1.Length; int, dist = new int2, str2.Length + 1; for (i = 0; i <= str2.Length; i+) dist0, i = i; for (i = 1; i <= str1.Length; i+) dist1, 0 = i; for (j = 1; j <= str2.Length; j+) if (str1i - 1 = str2j - 1)

20、dist1, j = dist0, j - 1; else dist1, j = LowerOfThree(dist0, j - 1, dist0, j, dist1, j - 1) + 1; for (j = 0; j <= str2.Length; j+) dist0, j = dist1, j; temp = dist1, str2.Length; return temp;3.2 時(shí)間效率優(yōu)化4.3.1 編輯距離算法的時(shí)間效率優(yōu)化思想在對(duì)上面的傳統(tǒng)編輯距離算法仔細(xì)分析后，發(fā)現(xiàn)兩個(gè)字符串相對(duì)應(yīng)位置上的字符相同時(shí)，把這兩個(gè)相對(duì)應(yīng)的相同的字符刪除掉后，對(duì)計(jì)算結(jié)果沒(méi)有任何影響。刪除這些相對(duì)

21、應(yīng)位置相同的字符后將會(huì)減少編輯計(jì)算的字符，即參與計(jì)算的兩字符的長(zhǎng)度變短，從而使得計(jì)算的時(shí)間效率加快，達(dá)到提高算法時(shí)間效率的效果。再者，針對(duì)于純中文的文本，我們考慮到文本中的標(biāo)點(diǎn)符號(hào)也會(huì)被當(dāng)成一個(gè)獨(dú)立的字符參與計(jì)算，但是這些標(biāo)點(diǎn)符號(hào)對(duì)于我們所要計(jì)算的文本相似度來(lái)說(shuō)毫無(wú)意義。因此可采取的做法就是把這些標(biāo)點(diǎn)符號(hào)全部刪除，只保留文字，用純文字的字符來(lái)參與計(jì)算，這樣將會(huì)使得參與計(jì)算的字符長(zhǎng)度變短，加快計(jì)算的速率，減少計(jì)算所占用的內(nèi)存空間，而且使得計(jì)算的結(jié)果更加地符合實(shí)際，獲得更高的準(zhǔn)確率。4.3.2 編輯距離算法的時(shí)間效率優(yōu)化原理步驟一：把源字符串S里含有的標(biāo)點(diǎn)符號(hào)用空格替換掉。步驟二：把源字符串S中所

22、含的空格全部清除。步驟三：把目標(biāo)字符串T里含有的標(biāo)點(diǎn)符號(hào)用空格替換掉。步驟四：把目標(biāo)字符串T中所含的空格全部清除。步驟五：把去除標(biāo)點(diǎn)符號(hào)的源字符串S轉(zhuǎn)換成一維字符數(shù)組S1。步驟六：把去除標(biāo)點(diǎn)符號(hào)的目標(biāo)字符串T轉(zhuǎn)換成一維字符數(shù)組T1。步驟七：從兩數(shù)組的起始位置開(kāi)始，比較S1和T1中相對(duì)應(yīng)位置的字符是否相等，若相等，則S1和T1中相對(duì)應(yīng)位置的字符將用空格代替。步驟八：從兩數(shù)組的末尾位置開(kāi)始，比較S1和T1中相對(duì)應(yīng)位置的字符是否相等，若相等，則S1和T1中相對(duì)應(yīng)位置的字符將用空格代替。步驟九：把經(jīng)過(guò)步驟五、六后的數(shù)組S1轉(zhuǎn)換成字符串S2，并把里面所含的空格全部清除。步驟十：把經(jīng)過(guò)步驟五、六后的數(shù)組T

23、1轉(zhuǎn)換成字符串T2，并把里面所含的空格全部清除。步驟十一:再把所得到的字符串S2和字符串T2進(jìn)行計(jì)算它們之間的編輯距離。本小節(jié)以源字符串S“計(jì)算機(jī),不怕你!”和目標(biāo)字符串T“物理機(jī)電,誰(shuí)怕誰(shuí)?”來(lái)演示如何計(jì)算這兩個(gè)字符串之間的Levenshtein距離。計(jì)算機(jī)，不怕你！源字符串S:物理機(jī)電，誰(shuí)怕誰(shuí)？目標(biāo)字符串T: 計(jì)算機(jī) 不怕你步驟一：源字符串S:計(jì)算機(jī)不怕你步驟二：源字符串S:物理機(jī)電 誰(shuí)怕誰(shuí) 步驟三：目標(biāo)字符串T: 物理機(jī)電誰(shuí)怕誰(shuí)步驟四：目標(biāo)字符串T:計(jì)算機(jī)不怕你步驟五：字符數(shù)組S1:物理機(jī)電誰(shuí)怕誰(shuí)步驟六：字符數(shù)組T1:步驟七：計(jì)算不怕你物理電誰(shuí)怕誰(shuí)字符數(shù)組S1:字符數(shù)組T1:計(jì) 算 不

24、你 步驟八:字符數(shù)組S1:物 理 電 誰(shuí) 誰(shuí)字符數(shù)組T1:計(jì)算不你 步驟九：源字符串S2:物理電誰(shuí)誰(shuí)步驟十：目標(biāo)字符串T2:步驟十一：計(jì)算字符串S2和字符串T2之間的編輯距離，如表3-2所示。表3-2 字符串S2和字符串T2之間的編輯距離計(jì)算計(jì)算不你01234物11234理22234電33334誰(shuí)44444誰(shuí)55555步驟十一右下角的值便是源字符串S“計(jì)算機(jī),不怕你!”和目標(biāo)字符串T“物理機(jī)電,誰(shuí)怕誰(shuí)?”的編輯距離的值，編輯步數(shù)為5。4.3.3 編輯距離算法的時(shí)間效率優(yōu)化比較和分析源字符串S“計(jì)算機(jī),不怕你!”和目標(biāo)字符串T“物理機(jī)電,誰(shuí)怕誰(shuí)?”在沒(méi)有經(jīng)過(guò)時(shí)間效率優(yōu)化的編輯距離算法，其算法步驟

25、如表3-3所示：表3-3 源字符串S和目標(biāo)字符串T之間的編輯距離計(jì)算計(jì)算機(jī)，不怕你！012345678物112345678理222345678機(jī)333234567電444334567，555434567誰(shuí)666544567怕777655456誰(shuí)888766556？999877666右下角的值為源字符串S“計(jì)算機(jī),不怕你!”和目標(biāo)字符串T“物理機(jī)電,誰(shuí)怕誰(shuí)?”的編輯距離的值，編輯步數(shù)為6，則它們所對(duì)應(yīng)的文本相似度計(jì)算為：因?yàn)長(zhǎng)max= Max(S.Length,T.Length)=9；所以 SI=1-LD/ Lmax=1-6/933.33%經(jīng)過(guò)時(shí)間效率優(yōu)化后的編輯距離算法，它們的編輯步數(shù)為5，則

26、它們所對(duì)應(yīng)的文本相似度的計(jì)算為：因?yàn)長(zhǎng)max= Max(S1.Length,T1.Length)=7；（即為兩個(gè)字符串刪除標(biāo)點(diǎn)符號(hào)后的字符串長(zhǎng)度的最大值。）所以 SI=1-LD/ Lmax=1-5/728.57%對(duì)這兩個(gè)文本相似度計(jì)算的結(jié)果分析，容易發(fā)現(xiàn)經(jīng)過(guò)時(shí)間效率優(yōu)化后的編輯距離算法更符合實(shí)際情況，更加實(shí)用。刪除了字符串中標(biāo)點(diǎn)符號(hào)和相對(duì)應(yīng)位置的相同的字符后，使得計(jì)算量減少，所占內(nèi)存減少，并加快了計(jì)算的效率，提高了準(zhǔn)確率。4.3.4 編輯距離算法的時(shí)間效率優(yōu)化核心代碼string s1 = Regex.Replace(string1, "u4e00-u9fa5s", &qu

27、ot; ");string ss1 = Regex.Replace(s1, "s", "");string s2 = Regex.Replace(string2, "u4e00-u9fa5s", " ");string ss2 = Regex.Replace(s2, "s", "");if (ss1.Length < ss2.Length) string ss3; ss3 = ss1; ss1 = ss2; ss2 = ss3;char strs1 = ss1

28、.ToCharArray();char strs2 = ss2.ToCharArray();int k = 0;Stopwatch watch = new Stopwatch();watch.Start();for (int i = 0; i < strs2.Length; i+) if (strs2i = strs1i) strs1i = Convert.ToChar(" "); strs2i = Convert.ToChar(" "); if (strs1.Length != strs2.Length) for (int j = strs1.L

29、ength - strs2.Length; j < strs1.Length; j+) if (strs1j = strs2k) strs1j = Convert.ToChar(" "); strs2k = Convert.ToChar(" "); k+; string word1 = new String(strs1);string str1 = Regex.Replace(word1, "s", "");string word2 = new String(strs2);string str2 = Rege

30、x.Replace(word2, "s", "");3.3 準(zhǔn)確率優(yōu)化4.3.1 編輯距離算法的準(zhǔn)確率優(yōu)化思想對(duì)傳統(tǒng)的編輯距離算法分析，發(fā)現(xiàn)單純以字為單位計(jì)算字符串之間的編輯距離，計(jì)算出的語(yǔ)義距離4和實(shí)際情況出入很大，而且序列長(zhǎng)度對(duì)代價(jià)函數(shù)的計(jì)算結(jié)果也有很大的影響，針對(duì)這些情況，下文提出了一種基于詞語(yǔ)的編輯距離算法5的文本相似度檢測(cè)方法，對(duì)字符串進(jìn)行分詞后進(jìn)行編輯計(jì)算，從而使得計(jì)算結(jié)果更符合字符串詞語(yǔ)相似度計(jì)算的要求，計(jì)算的速率和文本相似度的準(zhǔn)確率都得以提高，使文本相似度計(jì)算的性能進(jìn)一步改善，更符合實(shí)際情況。4.3.2 中文分詞介紹中文分詞6指的是使用計(jì)

31、算機(jī)自動(dòng)對(duì)中文文本進(jìn)行詞語(yǔ)切分，將一個(gè)漢字序列切分成一個(gè)個(gè)單獨(dú)的詞，即像英文那樣使中文句子中的詞之間有空格以標(biāo)識(shí)。而中文之間僅能通過(guò)標(biāo)點(diǎn)符號(hào)、句和段作為分界符來(lái)簡(jiǎn)單劃分，中文的劃分比英文的劃分要復(fù)雜的多、困難的多。因此對(duì)于中文分詞一般都采用分詞技術(shù)來(lái)進(jìn)行分詞。目前的分詞方法可以分為兩類(lèi)，一是基于統(tǒng)計(jì)的方法, 一種是基于字典的方法?；诮y(tǒng)計(jì)的方法一般精度低?；谧值涞姆椒ň雀? 實(shí)現(xiàn)簡(jiǎn)單。因此本文所提出改進(jìn)算法是選用一種基于字典方法的“盤(pán)古分詞”作為中文分詞匹配時(shí)的詞庫(kù)。盤(pán)古分詞的分詞技術(shù)7相當(dāng)成熟，在詞頻優(yōu)先、歧義問(wèn)題、中文未登錄詞識(shí)別、中文人名識(shí)別等方面有著非常好的功能，相對(duì)較完善。如：

32、輸入：我愛(ài)吃蘋(píng)果分詞結(jié)果：我|愛(ài)|吃|蘋(píng)果|輸入：我喜歡吃香蕉分詞結(jié)果：我|喜歡|吃|香蕉|4.3.3 編輯距離算法的準(zhǔn)確率優(yōu)化原理經(jīng)過(guò)準(zhǔn)確率優(yōu)化的編輯距離算法以詞語(yǔ)為單位代替以字為單位進(jìn)行計(jì)算，基本步驟如下：步驟一：對(duì)源字符串S進(jìn)行分詞。步驟二：對(duì)目標(biāo)字符串T進(jìn)行分詞。步驟三：把源字符串S分詞后的詞語(yǔ)組成數(shù)組S1。步驟四：把目標(biāo)字符串T分詞后的詞語(yǔ)組成數(shù)組T1。步驟五：對(duì)數(shù)組S1與數(shù)組T1進(jìn)行編輯距離計(jì)算。本小節(jié)以源字符串S“我愛(ài)吃蘋(píng)果”和目標(biāo)字符串T“我喜歡吃香蕉”來(lái)演示如何計(jì)算這兩個(gè)字符串之間的Levenshtein距離。源字符串S: 我愛(ài)吃蘋(píng)果目標(biāo)字符串T: 我喜歡吃香蕉步驟一：我|愛(ài)

33、|吃|蘋(píng)果|步驟二：我|喜歡|吃|香蕉|我愛(ài)吃蘋(píng)果步驟三：數(shù)組S1：我喜歡吃香蕉步驟四：數(shù)組T1：步驟五：數(shù)組S1與數(shù)組T1的編輯距離計(jì)算結(jié)果如表3-4所示：表3-4 數(shù)組S1與數(shù)組T1的編輯距離計(jì)算我愛(ài)吃蘋(píng)果01234我10123喜歡21123吃32212香蕉43322步驟五右下角的值便是源字符串S“我愛(ài)吃蘋(píng)果”和目標(biāo)字符串T“我喜歡吃香蕉”的編輯距離的值，編輯步數(shù)為2。4.3.4 編輯距離算法的準(zhǔn)確率優(yōu)化比較和分析源字符串S“我愛(ài)吃蘋(píng)果”和目標(biāo)字符串T“我喜歡吃香蕉”在沒(méi)有經(jīng)過(guò)時(shí)間效率優(yōu)化的編輯距離算法，其算法步驟如表3-5所示：表3-5源字符串S與目標(biāo)字符串T的編輯距離計(jì)算我愛(ài)吃蘋(píng)果01

34、2345我101234喜211234歡322234吃433234香544334蕉655444右下角的值為源字符串S“我愛(ài)吃蘋(píng)果”和目標(biāo)字符串T“我喜歡吃香蕉”的編輯距離的值，編輯步數(shù)為4，則它們所對(duì)應(yīng)的文本相似度計(jì)算為：因?yàn)長(zhǎng)max= Max(S.Length,T.Length)=6；所以 SI=1-LD/ Lmax=1-4/633.33%經(jīng)過(guò)時(shí)間效率優(yōu)化后的編輯距離算法，它們的編輯步數(shù)為2，則它們所對(duì)應(yīng)的文本相似度的計(jì)算為：因?yàn)長(zhǎng)max= Max(S1.Length,T1.Length)=4；（即為兩個(gè)字符串刪除標(biāo)點(diǎn)符號(hào)后的字符串長(zhǎng)度的最大值。）所以 SI=1-LD/ Lmax=1-2/45

35、0%對(duì)這兩個(gè)文本相似度計(jì)算的結(jié)果分析，我們可以看出，單純以字為單位的編輯距離算法，在漢語(yǔ)中，單個(gè)的字往往是不具備意義的。例如上面的“蘋(píng)”、“果”等字, 并不能反映其所合成詞的意義，計(jì)算出的語(yǔ)義距離與實(shí)際情況有很大的出入。因此本文采用分詞的思想，用詞語(yǔ)代替單個(gè)漢字或者字符作為基本的編輯單元參與運(yùn)算，充分考慮詞語(yǔ)的概念，是一種基于詞語(yǔ)的編輯距離算法，使得計(jì)算的結(jié)果更符合文本相似度計(jì)算的要求，并且提高了計(jì)算的速度和提高了準(zhǔn)確率。4.3.5 編輯距離算法的準(zhǔn)確率優(yōu)化核心代碼public class WordSegmentpublic static string GetWords(string word

36、) return Segment(word); private static string Segment(string word) Analyzer analyzer = new PanGuAnalyzer(); TokenStream tokenStream = analyzer.TokenStream("", new StringReader(word);Lucene.Net.Analysis.Token token = null; string txt = "" while (token = tokenStream.Next() != null)

37、txt += token.TermText() + "|" string segmentword = txt.Split(new char '|' , StringSplitOptions.RemoveEmptyEntries); return segmentword; 4 實(shí)驗(yàn)測(cè)試和結(jié)果分析4.1 實(shí)驗(yàn)環(huán)境本文實(shí)驗(yàn)是在Windows XP操作系統(tǒng)、Microsoft Visual Studio 2005的開(kāi)發(fā)環(huán)境下，通過(guò)C#語(yǔ)言8實(shí)現(xiàn)的一個(gè)算法應(yīng)用原型軟件，用于測(cè)試算法的運(yùn)行結(jié)果以及統(tǒng)計(jì)分析。4.2 實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)實(shí)驗(yàn)測(cè)試分析上面提出的編輯距離算法是否正確，

38、以及通過(guò)實(shí)驗(yàn)數(shù)據(jù)的統(tǒng)計(jì)和分析得出實(shí)驗(yàn)結(jié)論。4.3 實(shí)驗(yàn)內(nèi)容根據(jù)上面的提出的三種優(yōu)化方案，本實(shí)驗(yàn)提出了五種實(shí)驗(yàn)方案，采用對(duì)比的方法來(lái)測(cè)試分析各優(yōu)化方案的結(jié)果的差異，進(jìn)而得出實(shí)驗(yàn)結(jié)論。實(shí)驗(yàn)結(jié)果的數(shù)據(jù)包括編輯距離算法計(jì)算的編輯步數(shù)、文本相似度、計(jì)算所用時(shí)間、所耗內(nèi)存等。4.3.1 原方案與方案一比較分析本小節(jié)以源字符串“GUMBO”和目標(biāo)字符串“GAMBOL”為例，計(jì)算它們之間的編輯距離，原方案為傳統(tǒng)的編輯距離算法，方案一為經(jīng)過(guò)空間復(fù)雜度優(yōu)化的編輯距離算法，實(shí)驗(yàn)結(jié)果如圖4-1所示： 圖4-1 原方案和方案一的編輯距離算法計(jì)算結(jié)果圖由實(shí)驗(yàn)測(cè)試結(jié)果，可見(jiàn)方案一算法結(jié)果中的編輯步數(shù)、文本相似度和計(jì)算時(shí)間跟

39、原方案的結(jié)果一樣，所耗內(nèi)存比原方案少很多。由此可以證明前面提出的編輯距離算法的空間復(fù)雜度的優(yōu)化原理是正確的，改進(jìn)后的編輯距離算法有效地提高算法運(yùn)算過(guò)程中所耗的內(nèi)存。4.3.2 原方案與方案二、三比較分析由于沒(méi)有標(biāo)準(zhǔn)的文本相似度測(cè)試資料，所以實(shí)驗(yàn)所有的資料都是由我們自己構(gòu)造。本小節(jié)實(shí)驗(yàn)所用的資料來(lái)源于圖書(shū)文章的截取。原方案為傳統(tǒng)的編輯距離算法，方案二為經(jīng)過(guò)時(shí)間效率優(yōu)化的編輯距離算法，方案三為在方案二優(yōu)化的基礎(chǔ)上，增加了空間復(fù)雜度的優(yōu)化。實(shí)驗(yàn)結(jié)果如圖4-2、4-3、4-4、4-5所示：圖4-2 兩個(gè)完全一樣的字符串的編輯距離計(jì)算結(jié)果圖4-3 兩個(gè)相似度很大的字符串的編輯距離計(jì)算結(jié)果圖4-4 兩個(gè)相

40、似度接近50%的字符串的編輯距離計(jì)算結(jié)果圖4-5 兩個(gè)相似度很小的字符串編輯距離計(jì)算結(jié)果由圖4-2、4-3、4-4、4-5實(shí)驗(yàn)結(jié)果分析，可見(jiàn)方案二的算法結(jié)果中的編輯步數(shù)、文本相似度與原方案的計(jì)算結(jié)果相差不大，計(jì)算時(shí)間和所耗內(nèi)存的大小隨著兩字符串的文本相似度的增大而不斷減小。方案三在方案二優(yōu)化的基礎(chǔ)上，增加了空間復(fù)雜度的優(yōu)化，使得算法所耗的內(nèi)存更少。由此可以證明上面提出的編輯距離算法的時(shí)間效率的優(yōu)化原理是正確的，改進(jìn)后的編輯距離算法，使得參與計(jì)算的字符串序列變短，所耗內(nèi)存減少，加快了計(jì)算的速率，提高了準(zhǔn)確率。4.3.3 原方案與方案四、五比較分析本小節(jié)以源字符串“我愛(ài)吃蘋(píng)果”和目標(biāo)字符串“我喜歡吃香蕉”為例，計(jì)算它們之間的編輯距離，原方案為傳統(tǒng)的編輯距離算法，方案四為經(jīng)過(guò)準(zhǔn)確率優(yōu)化的編輯距離算法，方案五為在方案四優(yōu)化的基礎(chǔ)上，增加了空間復(fù)雜度的優(yōu)化。實(shí)驗(yàn)結(jié)果如圖4-6所示：圖4-6 原方案和方案四、五的編輯距離算法計(jì)算結(jié)果圖由