基于局部變化性的改進(jìn)編輯距離算法

王衛(wèi)紅，李 君

（浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州310023）

·開發(fā)研究與工程應(yīng)用·

基于局部變化性的改進(jìn)編輯距離算法

王衛(wèi)紅，李 君

（浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州310023）

針對(duì)經(jīng)典編輯距離算法在求解字符串相似度時(shí)計(jì)算效率過低的問題，提出一種改進(jìn)的編輯距離算法。先求得2個(gè)字符串的最長(zhǎng)公共前綴和最長(zhǎng)公共后綴，再根據(jù)經(jīng)典編輯距離算法得到2個(gè)字符串剩余部分之間的編輯距離，由反證法證明該編輯距離即為2個(gè)原始字符串的編輯距離。在此基礎(chǔ)上，分析改進(jìn)算法的優(yōu)勢(shì)并將其應(yīng)用于網(wǎng)頁(yè)篡改檢測(cè)中。實(shí)驗(yàn)結(jié)果表明，與經(jīng)典算法相比，改進(jìn)算法在求解同一網(wǎng)址的網(wǎng)頁(yè)相似度時(shí)具有更高的計(jì)算效率。

編輯距離；相似度；公共前綴；公共后綴；局部變化性；篡改檢測(cè)

中文引用格式：王衛(wèi)紅，李 君.基于局部變化性的改進(jìn)編輯距離算法［J］.計(jì)算機(jī)工程，2015，41（7）：294?298，304.

英文引用格式：Wang Weihong，Li Jun.Improved Edit Distance Algorithm Based on Local Variability［J］.Computer Engineering，2015，41（7）：294?298，304.

1 概述

字符串相似度問題在抄襲檢測(cè)系統(tǒng)、數(shù)據(jù)清洗、信號(hào)處理、搜索引擎等領(lǐng)域具有廣泛應(yīng)用。根據(jù)計(jì)算所依據(jù)特征的不同，計(jì)算方法可以劃分為3種方法［1?2］：基于字面相似的方法，基于統(tǒng)計(jì)關(guān)聯(lián)的方法，基于語(yǔ)義相似的方法?；诰庉嬀嚯x的相似度算法是基于字面相似方法中的一種，它從整體上考慮了文本上下文之間的語(yǔ)義關(guān)系，是一種經(jīng)典而廣為使用的方法。

近年來(lái)，對(duì)基于編輯距離相似度算法的研究偏重于算法效果的改善。比如考慮到字符串之間公共子串對(duì)相似度的影響，對(duì)相似度度量公式和編輯距離計(jì)算方法進(jìn)行了改進(jìn)［3］?？梢酝ㄟ^拓展交換操作減少編輯操作的數(shù)量得到更理想的編輯距離［4］。針對(duì)中西文混合字符串，采用將漢字作為西文字符的等價(jià)單位、拼音編碼、五筆編碼3種方式計(jì)算編輯距離以獲得更好的效果［5］。也有一些編輯距離在新領(lǐng)域的應(yīng)用，比如將編輯距離應(yīng)用于編程題自動(dòng)評(píng)閱中［6］、改進(jìn)編輯距離算法以解決網(wǎng)頁(yè)搜索中簡(jiǎn)短域與用戶查詢之間相關(guān)性的排序問題［7］?？紤]編輯距離算法計(jì)算效率這類問題比較少，比如基于Karp?Rabin和最長(zhǎng)公共子串算法思想，可以使用串的散列值匹配來(lái)加快計(jì)算［8］。本文在這些算法的基礎(chǔ)上，提出一種改進(jìn)的編輯距離算法。

2 基于經(jīng)典編輯距離算法的相似度計(jì)算

2.1 經(jīng)典編輯距離算法

編輯距離是指由源字符串S轉(zhuǎn)換到目標(biāo)字符串T所需最少編輯操作數(shù)，所需要的操作數(shù)越少，2個(gè)字符串相關(guān)性越高。基本編輯操作有3種：（1）把串S中的一個(gè)字符替換為串T中的一個(gè)字符。（2）把串S中的一個(gè)字符刪除。（3）在串 S中插入一個(gè)字符。

設(shè)2個(gè)字符串S＝s1s2…sm和T＝t1t2…tn。建立S與T的（m+1）×（n+1）階矩陣LD：

其中，di，j為s1s2…si和t1t2…ti之間的編輯距離。

可由以下公式求得矩陣LD中的di，j：

其中：

可動(dòng)態(tài)規(guī)劃［9］求解得編輯距離，即當(dāng)i＝1→m和j＝1→n時(shí)依次根據(jù)上式求解di，j。所有di，j需要遍歷一次，算法時(shí)間復(fù)雜度為O（mn）。矩陣LD右下角的元素dm，n為字符串S與T之間的編輯距離，即字符串S轉(zhuǎn)換到字符串T所需最少的編輯操作次數(shù)。

2.2 基于編輯距離的相似度

可以由編輯距離獲得2個(gè)字符串之間的相似度。直觀上，2個(gè)字符串越相似，編輯距離越小，相似度越大。將編輯距離轉(zhuǎn)化為值在［0，1］區(qū)間相似度的公式如下：

其中，｜S｜，｜T｜分別表示字符串S和T的長(zhǎng)度；dm，n表示字符串S和T之間的編輯距離。sim（S，T）越大，表示2個(gè)字符串相似度越大。

3 網(wǎng)頁(yè)篡改檢測(cè)原理及現(xiàn)狀

3.1 檢測(cè)方案

網(wǎng)頁(yè)篡改檢測(cè)是指盡早發(fā)現(xiàn)網(wǎng)頁(yè)被篡改，并通知相關(guān)方面采取應(yīng)急措施。傳統(tǒng)的檢測(cè)方案集中于基于服務(wù)器端的網(wǎng)頁(yè)篡改檢測(cè)，這類方案盡管檢測(cè)精度較高，但存在諸多不足之處：只適合單機(jī)部署，應(yīng)用成本巨大；不適宜批量檢測(cè)篡改；因?yàn)樯婕暗綌?shù)據(jù)隱私、服務(wù)器第三方托管、系統(tǒng)穩(wěn)定性等問題，很多單位不希望在服務(wù)器上安裝不熟悉的軟件?；诳蛻舳说木W(wǎng)頁(yè)篡改技術(shù)能有效避免以上問題，而且能對(duì)網(wǎng)站的運(yùn)行情況進(jìn)行實(shí)時(shí)監(jiān)測(cè)［10?11］?；谙嗨贫鹊目蛻舳司W(wǎng)頁(yè)篡改檢測(cè)方法是其中一種簡(jiǎn)單有效的篡改檢測(cè)方法。它將整個(gè)HTML文件看成一個(gè)字符串，使用相似度算法計(jì)算2個(gè)連續(xù)網(wǎng)頁(yè)之間的相似度。對(duì)于特定網(wǎng)址，每隔相同時(shí)間爬取網(wǎng)頁(yè)。由概率論可得，每次爬取的頁(yè)面與上一頁(yè)面的相似度服從指數(shù)分布，即概率密度和分布函數(shù)分別為：

根據(jù)中心極限定理［12］可知：當(dāng)樣本容量n取得充分大，統(tǒng)計(jì)量近似服從正態(tài)分布N（0， 1）。 即：

服從N（0，1）。

假設(shè)當(dāng)前頁(yè)面與上一頁(yè)面的相似度值為s0，取顯著性水平α為0.2。本文提出的2個(gè)對(duì)立假設(shè)如下所示：

當(dāng)α為0.2，查表可知Φ0.1＝1.3。當(dāng)Φ0.1＞1.3時(shí)，即，則H0被拒絕，也即當(dāng)前μ0值異常，應(yīng)該觸發(fā)報(bào)警，提示發(fā)生篡改［13?15］。

3.2 現(xiàn)有檢測(cè)方案的不足

作為一種基于客戶端的篡改檢測(cè)方案，該方案從概率統(tǒng)計(jì)學(xué)上研究篡改問題，能在客戶端批量檢測(cè)大量網(wǎng)址對(duì)應(yīng)網(wǎng)頁(yè)是否發(fā)生篡改。在該方案中，其中一個(gè)步驟需要計(jì)算網(wǎng)頁(yè)頁(yè)面之間相似度。經(jīng)典算法的時(shí)間復(fù)雜度為O（mn），當(dāng)計(jì)算同一網(wǎng)址相鄰時(shí)刻網(wǎng)頁(yè)之間相似度時(shí)，往往需要花費(fèi)幾分鐘甚至幾個(gè)小時(shí)。這樣的計(jì)算效率遠(yuǎn)遠(yuǎn)不能適應(yīng)大規(guī)模批量網(wǎng)頁(yè)篡改檢測(cè)需要。與此同時(shí)，由于網(wǎng)頁(yè)的局部性變化原理［8］，即網(wǎng)頁(yè)的更新方式是局部更新的，相鄰網(wǎng)頁(yè)之間往往存在很多公共相同部分，計(jì)算相似度時(shí)，需要很多多余的計(jì)算。基于這類情況，本文提出了一種改進(jìn)的編輯距離算法。

4 改進(jìn)的編輯距離算法

4.1 算法步驟

與同一網(wǎng)址相鄰時(shí)刻網(wǎng)頁(yè)之間存在很多公共字符串類似，很多時(shí)候，字符串之間存在局部性變化，此時(shí)，若按照經(jīng)典算法求解編輯距離，往往存在很多多余的計(jì)算。針對(duì)這一情況，提出一種改進(jìn)的編輯距離算法，算法流程如圖1所示。設(shè)S＝s1，s2，…，sm和T＝t1，t2，…，tn，則可以先貪心求得S和T的最長(zhǎng)公共前綴comprefix和最長(zhǎng)公共后綴comsuffix，將S和T都在開頭減去字符串序列comprefix和結(jié)尾減去字符串序列comsuffix后，再根據(jù)經(jīng)典算法求得剩余部分的編輯距離C，則S與T的編輯距離為：

圖1 改進(jìn)算法流程

改進(jìn)的編輯距離算法步驟如下：

Step1 初始化 Sstart＝ 1，Send＝ m，Tstart＝ 1，Tend＝n。

Step2 如果 Sstart≤ m，Tstart≤ n，S［Sstart］ ＝T［Tstart］，則Sstart++，Tstart++，并跳轉(zhuǎn)Step2。

Step3 如果 Send≥Sstart，Tend≥Tstart，S［Send］ ＝T［Tend］，則可得Send--，Tend--，并跳轉(zhuǎn)Step3。

Step4 可以設(shè) remainS＝sSstart，sSstart+1，…，sSend和remainT＝tTstartt，tTstart+1，…，tTend，使用經(jīng)典的編輯距離算法 求 得 remainS和 remainT 的 編 輯 距 離remainDis。

Step5 求得S和T的編輯距離為：

4.2 算法正確性證明

假設(shè)改進(jìn)的算法求得的解不是正確的編輯距離。設(shè)字符串A與B根據(jù)改進(jìn)算法求得的解為dis（A，B）improve，根據(jù)經(jīng)典的編輯距離算法求得的解為dis（A，B）true，由假設(shè)可得：

設(shè)在經(jīng)典編輯距離算法中，編輯成T［1，2，…，Tstart-1］的S最短前綴字符串為 S［1，2，…，shstart-1］，編輯成T［Tend+1，Tend+2，…，n］的 S最短后綴字符串為S［shend+1，shend+2，…，m］。 則：

由圖2改進(jìn)算法正確性證明示意圖可得S［1，2，…，shstart-1］與 T［1，2，…，Tstart-1］長(zhǎng)度差為，兩者的編輯距離至少為，即：

圖2 改進(jìn)算法正確性證明示意圖

將S［Sstart，…，Send］編輯成 T［Tstart，…，Tend］的一些方案中，有一種方案詳細(xì)步驟如下：

步驟1 將S［Sstart，…，Send］編輯成 S［shstart，…，shend］。 在這一編輯過程中，在字符串開頭，當(dāng)shstart＜Sstart時(shí)，可以添加 S［shstart，shstart+1，…，Sstart-1］于S［Sstart，…，Send］開頭，當(dāng) shiftstart≥Sstart時(shí)，可以在 S［Sstart，…，Send］開頭處刪除 S［Sstart，Sstart+1，…，shstart-1］，編輯次數(shù)為。在字符串結(jié)尾，添加S［Send+1，Send+2，…，shend］（shend＞Send時(shí)）或刪除S［shend+1，shend+2，…，Send］（shend≤Send時(shí)），類似同理可得編輯次數(shù)為。這一過程中總的編輯次數(shù)為

步驟2 將S［shstart，…，shend］編輯成T［Tstart，…，Tend］。在這個(gè)過程中使用最優(yōu)編輯次數(shù)的編輯方法，所得的編輯次數(shù)即為 dis（S［shstart，…，shend］，T［Tstart，…，Tend］）true。

在這個(gè)方案中，所需要總的編輯次數(shù)是：

它必定大于 S［Sstart，…，Send］編輯成 T［Tstart，…，Tend］的最少編輯次數(shù)，即 dis（S［Sstart，…，Send］，T［Tstart，…，Tend］）true。 所以：

綜合上述幾個(gè)公式可得：

與假設(shè)不符合，假設(shè)不成立。改進(jìn)的編輯距離算法所得解等于經(jīng)典的編輯距離算法所得解，改進(jìn)編輯距離算法正確性得到證明。

4.3 改進(jìn)的編輯距離算法優(yōu)勢(shì)分析

改進(jìn)的編輯距離算法可以分為2個(gè)部分：求解最長(zhǎng)公共前綴字符串和后綴字符串部分，求解剩余字符串編輯距離部分。前者的時(shí)間復(fù)雜度為線性時(shí)間復(fù)雜度，后者的時(shí)間復(fù)雜度為O（mn）（其中，m，n分別為剩余部分2個(gè)字符串的長(zhǎng)度）。在字符串長(zhǎng)度相等條件下，前者的比例增大，所用時(shí)間增大，后者所用時(shí)間減小，但前者增大的幅度遠(yuǎn)沒有后者減小的幅度大，所用總時(shí)間減小。

可見改進(jìn)算法適用于求解具有較長(zhǎng)最長(zhǎng)公共前綴或后綴的字符串之間的相似度。在基于相似度的客戶端網(wǎng)頁(yè)篡改檢測(cè)方法中［13?15］，同一網(wǎng)址相鄰時(shí)刻網(wǎng)頁(yè)就是屬于這類情況。由于網(wǎng)頁(yè)的局部性變化原理［14］，相鄰網(wǎng)頁(yè)之間往往存在很多公共相同部分，很多時(shí)候，2個(gè)網(wǎng)頁(yè)字符串之間存在較長(zhǎng)的最長(zhǎng)公共前綴字符串和后綴字符串，使用改進(jìn)算法能獲得一定效果。編程題自動(dòng)評(píng)閱也同樣適用于該算法［6］，在編程題自動(dòng)評(píng)閱中，很多答案與標(biāo)準(zhǔn)答案具有很高的相似度，往往存在較長(zhǎng)的最長(zhǎng)公共前綴字符串和后綴字符串，這時(shí)改進(jìn)的編輯距離算法具有更好的時(shí)間效率。

當(dāng)2個(gè)字符串S和T開頭處和結(jié)尾處都不相同時(shí)，改進(jìn)編輯距離算法（最長(zhǎng)公共前綴字符串和最長(zhǎng)公共后綴字符串長(zhǎng)度均為0）時(shí)間復(fù)雜度為O（mn）。其中，m，n分別為字符串S和T的長(zhǎng)度，與經(jīng)典編輯距離算法的時(shí)間復(fù)雜度一樣，但是這種類似情況在基于相似度的客戶端網(wǎng)頁(yè)篡改檢測(cè)和編程題自動(dòng)評(píng)閱中較少發(fā)生，很多情況下字符串之間具有較長(zhǎng)的最長(zhǎng)公共前綴字符串和后綴字符串，此時(shí)具有較好的計(jì)算效率。總的來(lái)說(shuō)，盡管有一些個(gè)體需要與經(jīng)典算法類似的大量計(jì)算時(shí)間，但平均到單個(gè)個(gè)體上的平均計(jì)算時(shí)間，與經(jīng)典算法相比，具有很大的改善。

5 實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證改進(jìn)算法在計(jì)算效率方面的優(yōu)勢(shì)，將它與經(jīng)典算法進(jìn)行比較?？紤]到在基于相似度的客戶端網(wǎng)頁(yè)篡改檢測(cè)方法中，需要監(jiān)測(cè)的網(wǎng)頁(yè)具有局部變化性［14］，即相鄰網(wǎng)頁(yè)之間往往具有較長(zhǎng)的最長(zhǎng)公共前綴或最長(zhǎng)公共后綴，可以每隔一定時(shí)間下載固定網(wǎng)址的網(wǎng)頁(yè)，分別使用改進(jìn)算法和經(jīng)典算法計(jì)算相鄰網(wǎng)頁(yè)之間的相似度，比較所用時(shí)間。

本文對(duì)3個(gè)網(wǎng)站每隔4個(gè)小時(shí)爬取并下載一張網(wǎng)頁(yè)，為期一個(gè)月。對(duì)于每個(gè)網(wǎng)址下載的網(wǎng)頁(yè)，分別按下載時(shí)間進(jìn)行排序，共建立180個(gè)序列。對(duì)于這3個(gè)有序序列，從第11個(gè)網(wǎng)頁(yè)到第30個(gè)網(wǎng)頁(yè)，依次計(jì)算與前一個(gè)網(wǎng)頁(yè)之間的相似度，記錄計(jì)算到第n張網(wǎng)頁(yè)時(shí)所用的總時(shí)間。分別使用2種算法計(jì)算相似度，測(cè)試環(huán)境為2 GHz Intel雙核處理器、2 GB內(nèi)存。使用C++實(shí)現(xiàn)算法。

圖3～圖5分別對(duì)應(yīng)3個(gè)網(wǎng)址的實(shí)驗(yàn)結(jié)果。在計(jì)算相鄰網(wǎng)頁(yè)相似度時(shí)，相對(duì)于經(jīng)典算法，改進(jìn)算法在計(jì)算時(shí)間方面具有明顯優(yōu)勢(shì)，同時(shí)這種優(yōu)勢(shì)并不是很穩(wěn)定。在這3個(gè)網(wǎng)址中，經(jīng)典算法所用時(shí)間基本是均勻增長(zhǎng)的，這主要是由于經(jīng)典算法的時(shí)間復(fù)雜度為O（mn）（其中，m，n分別為2個(gè)字符串的長(zhǎng)度），第10張網(wǎng)頁(yè)到第30張網(wǎng)頁(yè)總的監(jiān)測(cè)時(shí)間為44 h（大約2天），在這段時(shí)間里，這些網(wǎng)址的網(wǎng)頁(yè)長(zhǎng)度并沒有發(fā)生很大的變化，從而導(dǎo)致計(jì)算同一網(wǎng)址相鄰網(wǎng)頁(yè)相似度時(shí)所需時(shí)間基本相等，總的累計(jì)計(jì)算時(shí)間基本呈線性增長(zhǎng)。

圖3 網(wǎng)址1中改進(jìn)算法與經(jīng)典算法的對(duì)比

圖4 網(wǎng)址2中改進(jìn)算法與經(jīng)典算法的對(duì)比

圖5 網(wǎng)址3中改進(jìn)算法與經(jīng)典算法的對(duì)比

相對(duì)于經(jīng)典算法，改進(jìn)算法所需總的累計(jì)計(jì)算時(shí)間總體保持在較低水平，但在某些網(wǎng)頁(yè)之間會(huì)發(fā)生躍變。產(chǎn)生這種情況主要是因?yàn)榛诰W(wǎng)頁(yè)的局部變化性原理，大部分相鄰網(wǎng)頁(yè)在4 h內(nèi)只動(dòng)態(tài)更新一小部分甚至不更新。這些相鄰網(wǎng)頁(yè)動(dòng)態(tài)更新部分的最前位置與最后位置之間距離差較小，即相鄰網(wǎng)頁(yè)之間的最長(zhǎng)公共前綴字符串和后綴字符串總的長(zhǎng)度較長(zhǎng)，由此導(dǎo)致時(shí)間復(fù)雜度為O（n）部分?jǐn)?shù)據(jù)量較大，時(shí)間復(fù)雜度為O（mn）部分?jǐn)?shù)據(jù)量較小。此時(shí)總的計(jì)算時(shí)間由時(shí)間復(fù)雜度為O（n）部分的數(shù)據(jù)量決定，所花費(fèi)的時(shí)間較少，反映到實(shí)驗(yàn)結(jié)果中，即在使用改進(jìn)算法時(shí)，大部分情況下，總的累計(jì)計(jì)算時(shí)間隨著計(jì)算相鄰網(wǎng)頁(yè)數(shù)量的遞增，遞增的幅度很小，對(duì)應(yīng)曲線在大部分情況下保持基本水平狀態(tài)。與之相反，在少數(shù)情況下，由于相鄰網(wǎng)頁(yè)動(dòng)態(tài)更新部分的最前位置與最后位置之間距離差較大，即相鄰網(wǎng)頁(yè)之間的最長(zhǎng)公共前綴字符串和后綴字符串總的長(zhǎng)度較小，導(dǎo)致時(shí)間復(fù)雜度為O（n）部分?jǐn)?shù)據(jù)量較小，時(shí)間復(fù)雜度為O（mn）部分?jǐn)?shù)據(jù)量較大，總的計(jì)算時(shí)間由時(shí)間復(fù)雜度為O（mn）部分?jǐn)?shù)據(jù)量決定，此時(shí)所花費(fèi)的時(shí)間較大，反映到實(shí)驗(yàn)結(jié)果中，即改進(jìn)算法對(duì)應(yīng)曲線發(fā)生躍變。

改進(jìn)算法在某些網(wǎng)頁(yè)之間相似度所用時(shí)間與經(jīng)典算法相比，差距并不是很大，比如計(jì)算網(wǎng)址 1第23個(gè)網(wǎng)頁(yè)與第24個(gè)網(wǎng)頁(yè)之間相似度，網(wǎng)址 2第19頁(yè)與第20個(gè)網(wǎng)頁(yè)之間相似度。但總體上，當(dāng)計(jì)算所有從第11個(gè)網(wǎng)頁(yè)到第30個(gè)網(wǎng)頁(yè)這20個(gè)網(wǎng)頁(yè)與它們前一個(gè)網(wǎng)頁(yè)之間相似度所用總時(shí)間時(shí)，改進(jìn)算法與經(jīng)典算法相差懸殊。證明在計(jì)算批量網(wǎng)頁(yè)相似度時(shí)，與經(jīng)典算法相比，改進(jìn)的編輯距離算法在計(jì)算效率上有很大提升。

6 結(jié)束語(yǔ)

本文分析了經(jīng)典編輯距離算法及其在計(jì)算2個(gè)字符串相似度時(shí)存在的問題，基于局部變化性原理，提出了一種改進(jìn)的編輯距離算法。實(shí)驗(yàn)表明，當(dāng)求解大量相似字符串之間的相似度時(shí)，盡管該算法在少量字符串之間計(jì)算相似度時(shí)需要花費(fèi)較多時(shí)間，但是與經(jīng)典算法相比，該算法具有較高的計(jì)算效率。

［1］ Nirenburg S，Domashnev C，Grannes D J.Two Approaches to Matching in Example?based Machine Translation［C］／／Proceedings of the 5th International Conference on Theoretical and Methodological Issues in Machine Translation.Kyoto，Japan：UB／TIB Hannover，1993.

［2］ 吳 波.改進(jìn)的編輯距離算法的研究及其在電子政務(wù)中的應(yīng)用［D］.成都：電子科技大學(xué)，2011.

［3］ 姜 華，韓安琪，王美佳，等.基于改進(jìn)編輯距離的字符串相似度求解算法［J］.計(jì)算機(jī)工程，2014，40（1）：222?227.

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

［5］ 刁興春，譚明超，曹建軍.一種融合多種編輯距離的字符串相似度計(jì)算方法［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（12）：4523?4525.

［6］ 周漢平.Levenshtein距離在編程題自動(dòng)評(píng)閱中的應(yīng)用研究［J］.計(jì)算機(jī)應(yīng)用與軟件，2011，28（5）：328?331.

［7］ 薛曄偉，沈鈞毅，張 云.一種編輯距離算法及其在網(wǎng)頁(yè)搜索中的應(yīng)用［J］.西安交通大學(xué)學(xué)報(bào)，2008，42（12）：1450?1454.

［8］ 鄧愛萍.程序代碼相似度度量算法研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（17）：4636?4638.

［9］ Thomas H C，Charles E L，Ronald L R，等.算法導(dǎo)論［M］.2版.潘金貴，顧鐵成，李成法，譯.北京：機(jī)械工業(yè)出版社，2006.

［10］ 張振華.基于LAMP平臺(tái)架構(gòu)的網(wǎng)頁(yè)防篡改系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)［D］.北京：北京郵電大學(xué)，2010.

［11］ 陳 潔.網(wǎng)頁(yè)集中監(jiān)控防篡改系統(tǒng)技術(shù)研究［D］.成都：電子科技大學(xué)，2009.

［12］ 盛 驟，謝式遷，潘承毅.概率論與數(shù)理統(tǒng)計(jì)［M］.4版.北京：高等教育出版社，2008.

［13］ 魏文晗.網(wǎng)頁(yè)篡改檢測(cè)系統(tǒng)的研究與實(shí)現(xiàn)［D］.重慶：重慶大學(xué)，2013.

［14］ 魏文晗，鄧一貴.基于局部變化性的網(wǎng)頁(yè)篡改識(shí)別模型及方法［J］.計(jì)算機(jī)應(yīng)用，2013，33（2）：430?433.

［15］ Davanzo G，Medvet E，Bartoli A.Anomaly Detection Techniques for a Web Defacement Monitoring Service［J］.Expert Systems w ith Applications，2011，38（10）：12521?12530.

編輯 顧逸斐

Im proved Edit Distance Algorithm Based on Local Variability

WANGWeihong，LIJun
（College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310023，China）

For the low computational efficiency in solving the sim ilarity of two strings by traditional algorithm，an improved edit distance algorithm is proposed.It firstly obtains the longest common prefix and the longest common suffix of the two strings，and then gets the edit distance between the remainder of the two strings by traditional algorithm.Proof by contradiction is used to prove that this edit distance equals to the solution by traditional algorithm.On this basis，the improved algorithm is researched about the advantages and be applied to the Web tamper detection.Experimental results show that compared w ith the traditional algorithm，the improved edit distance algorithm has better computational efficiency in obtaining the sim ilarity between the pages in the same URL.

edit distance；sim ilarity；common prefix；common suffix；local variability；tamper detection

1000?3428（2015）07?0294?05

A

TP301.6

10.3969／j.issn.1000?3428.2015.07.056

國(guó)家自然科學(xué)基金資助項(xiàng)目（61340058）；浙江省自然科學(xué)基金資助項(xiàng)目（LZ14F020001）。

王衛(wèi)紅（1969-），男，教授，主研方向：空間信息服務(wù)，網(wǎng)絡(luò)信息安全；李 君，碩士研究生。

2015?01?30

2015?03?05E?mail：zjut_lijun＠126.com