王衛(wèi)紅，李 君

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

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

基于局部變化性的改進編輯距離算法

王衛(wèi)紅，李 君

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

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

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

中文引用格式：王衛(wèi)紅，李 君.基于局部變化性的改進編輯距離算法［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 概述

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

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

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

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

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

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

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

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

其中：

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

2.2 基于編輯距離的相似度

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

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

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

3.1 檢測方案

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

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

服從N（0，1）。

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

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

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

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

4 改進的編輯距離算法

4.1 算法步驟

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

圖1 改進算法流程

改進的編輯距離算法步驟如下：

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è)改進的算法求得的解不是正確的編輯距離。設(shè)字符串A與B根據(jù)改進算法求得的解為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改進算法正確性證明示意圖可得S［1，2，…，shstart-1］與 T［1，2，…，Tstart-1］長度差為，兩者的編輯距離至少為，即：

圖2 改進算法正確性證明示意圖

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

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

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

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

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

綜合上述幾個公式可得：

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

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

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

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

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

5 實驗與結(jié)果分析

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

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

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

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

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

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

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

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

6 結(jié)束語

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

［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］ 吳 波.改進的編輯距離算法的研究及其在電子政務(wù)中的應(yīng)用［D］.成都：電子科技大學(xué)，2011.

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

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

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

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

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

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

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

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

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

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

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

［14］ 魏文晗，鄧一貴.基于局部變化性的網(wǎng)頁篡改識別模型及方法［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

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

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

2015?01?30

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