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

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

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

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

5、本小節(jié)將演示如何計算源字符串"GUMBO"和目標字符串"GAMBOL"兩個字符串之間的Levenshtein距離，計算步驟如下：步驟1、2 步驟3、6，當i=1 步驟3、6，當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，當i=3 步驟3、6，當i=4 步驟3、6，當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"變換為目標字符串"GAMBOL"的過程，直觀可看出的，即通過將"A&quo

8、t;替換為"U"，并在末尾追加"L"字符，這跟計算的結(jié)果一致。4.3.3 編輯距離以及文本相似度計算編輯距離D（S,T）的計算方法如下所述。首先假設(shè)Dij=D(s1si, t1tj)，0im,0jn, Dij表示從s1si到t1tj的編輯距離，那么（m+1）×(n+1)階矩陣Dij可通過下面的（1）式計算得到： 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、從兩字符串的左邊開始比較，記錄已經(jīng)比較過的編輯距離，然后進一步得到下一個字符位置時的編輯距離。矩陣Dij能夠通過從D00逐步逐列計算獲取，最終Dmn表示D(S，T)的值，即S和T的編輯距離。文本相似度計算3：編輯距離越大，相似度越小。假設(shè)源字符串S與目標字符串T長度的最大值為Lmax，編輯距離為LD，相似度為SI，則相似度SI的計算如（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和目標字符串T的長度，則上述的基于動態(tài)規(guī)劃的編輯距離算法，其算法的空間復雜度為O（mn），時間復雜度為O（mn）。盡管編輯距離算法在文本相似度檢測方面具有一定的

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

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

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

15、的值。本小節(jié)仍以源字符串"GUMBO"和目標字符串"GAMBOL"來演示如何計算這兩個字符串之間的Levenshtein距離，計算步驟如下：步驟1、2 步驟3、6，當i=1 步驟3、6，當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，當i=3 步驟3、6，當i=4 步驟3、6，當i=5   GUMBO  012345G101234V0A211234V1M322123B  O  L&

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

18、傳統(tǒng)的編輯距離算法會創(chuàng)建一個矩陣dm+1,n+1,但此經(jīng)過優(yōu)化的算法將會創(chuàng)建兩個一維數(shù)組v0n+1 和v1n+1，其計算結(jié)果沒有發(fā)生變化，但內(nèi)存占用更少，其空間復雜度可為兩個字符串長度的最小值O(min(m，n)。在經(jīng)過空間復雜度優(yōu)化的編輯距離算法，其編輯步數(shù)一樣，因而相應的文本相似度計算的結(jié)果也一樣。編輯距離算法的空間復雜度優(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 時間效率優(yōu)化4.3.1 編輯距離算法的時間效率優(yōu)化思想在對上面的傳統(tǒng)編輯距離算法仔細分析后，發(fā)現(xiàn)兩個字符串相對應位置上的字符相同時，把這兩個相對應的相同的字符刪除掉后，對計算結(jié)果沒有任何影響。刪除這些相對

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

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

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

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

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

26、它們所對應的文本相似度的計算為：因為Lmax= Max(S1.Length,T1.Length)=7；（即為兩個字符串刪除標點符號后的字符串長度的最大值。）所以 SI=1-LD/ Lmax=1-5/728.57%對這兩個文本相似度計算的結(jié)果分析，容易發(fā)現(xiàn)經(jīng)過時間效率優(yōu)化后的編輯距離算法更符合實際情況，更加實用。刪除了字符串中標點符號和相對應位置的相同的字符后，使得計算量減少，所占內(nèi)存減少，并加快了計算的效率，提高了準確率。4.3.4 編輯距離算法的時間效率優(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 準確率優(yōu)化4.3.1 編輯距離算法的準確率優(yōu)化思想對傳統(tǒng)的編輯距離算法分析，發(fā)現(xiàn)單純以字為單位計算字符串之間的編輯距離，計算出的語義距離4和實際情況出入很大，而且序列長度對代價函數(shù)的計算結(jié)果也有很大的影響，針對這些情況，下文提出了一種基于詞語的編輯距離算法5的文本相似度檢測方法，對字符串進行分詞后進行編輯計算，從而使得計算結(jié)果更符合字符串詞語相似度計算的要求，計算的速率和文本相似度的準確率都得以提高，使文本相似度計算的性能進一步改善，更符合實際情況。4.3.2 中文分詞介紹中文分詞6指的是使用計

31、算機自動對中文文本進行詞語切分，將一個漢字序列切分成一個個單獨的詞，即像英文那樣使中文句子中的詞之間有空格以標識。而中文之間僅能通過標點符號、句和段作為分界符來簡單劃分，中文的劃分比英文的劃分要復雜的多、困難的多。因此對于中文分詞一般都采用分詞技術(shù)來進行分詞。目前的分詞方法可以分為兩類，一是基于統(tǒng)計的方法, 一種是基于字典的方法。基于統(tǒng)計的方法一般精度低。基于字典的方法精度高, 實現(xiàn)簡單。因此本文所提出改進算法是選用一種基于字典方法的“盤古分詞”作為中文分詞匹配時的詞庫。盤古分詞的分詞技術(shù)7相當成熟，在詞頻優(yōu)先、歧義問題、中文未登錄詞識別、中文人名識別等方面有著非常好的功能，相對較完善。如：

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

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

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

35、0%對這兩個文本相似度計算的結(jié)果分析，我們可以看出，單純以字為單位的編輯距離算法，在漢語中，單個的字往往是不具備意義的。例如上面的“蘋”、“果”等字, 并不能反映其所合成詞的意義，計算出的語義距離與實際情況有很大的出入。因此本文采用分詞的思想，用詞語代替單個漢字或者字符作為基本的編輯單元參與運算，充分考慮詞語的概念，是一種基于詞語的編輯距離算法，使得計算的結(jié)果更符合文本相似度計算的要求，并且提高了計算的速度和提高了準確率。4.3.5 編輯距離算法的準確率優(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 實驗測試和結(jié)果分析4.1 實驗環(huán)境本文實驗是在Windows XP操作系統(tǒng)、Microsoft Visual Studio 2005的開發(fā)環(huán)境下，通過C#語言8實現(xiàn)的一個算法應用原型軟件，用于測試算法的運行結(jié)果以及統(tǒng)計分析。4.2 實驗目的通過實驗測試分析上面提出的編輯距離算法是否正確，

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

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

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