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

王衛紅，李 君

（浙江工業大學計算機科學與技術學院，杭州310023）

·開發研究與工程應用·

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

王衛紅，李 君

（浙江工業大學計算機科學與技術學院，杭州310023）

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

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

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

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

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

2 基于經典編輯距離算法的相似度計算

2.1 經典編輯距離算法

編輯距離是指由源字符串S轉換到目標字符串T所需最少編輯操作數，所需要的操作數越少，2個字符串相關性越高?；揪庉嫴僮饔?種：（1）把串S中的一個字符替換為串T中的一個字符。（2）把串S中的一個字符刪除。（3）在串 S中插入一個字符。

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

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

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

其中：

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

2.2 基于編輯距離的相似度

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

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

3 網頁篡改檢測原理及現狀

3.1 檢測方案

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

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

服從N（0，1）。

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

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

3.2 現有檢測方案的不足

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

4 改進的編輯距離算法

4.1 算法步驟

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

圖1 改進算法流程

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

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

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

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

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

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

4.2 算法正確性證明

假設改進的算法求得的解不是正確的編輯距離。設字符串A與B根據改進算法求得的解為dis（A，B）improve，根據經典的編輯距離算法求得的解為dis（A，B）true，由假設可得：

設在經典編輯距離算法中，編輯成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］，編輯次數為。在字符串結尾，添加S［Send+1，Send+2，…，shend］（shend＞Send時）或刪除S［shend+1，shend+2，…，Send］（shend≤Send時），類似同理可得編輯次數為。這一過程中總的編輯次數為

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

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

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

綜合上述幾個公式可得：

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

4.3 改進的編輯距離算法優勢分析

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

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

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

5 實驗與結果分析

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

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

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

圖3 網址1中改進算法與經典算法的對比

圖4 網址2中改進算法與經典算法的對比

圖5 網址3中改進算法與經典算法的對比

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

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

6 結束語

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

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

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

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

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

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

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

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

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

［10］ 張振華.基于LAMP平臺架構的網頁防篡改系統設計與實現［D］.北京：北京郵電大學，2010.

［11］ 陳 潔.網頁集中監控防篡改系統技術研究［D］.成都：電子科技大學，2009.

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

［13］ 魏文晗.網頁篡改檢測系統的研究與實現［D］.重慶：重慶大學，2013.

［14］ 魏文晗，鄧一貴.基于局部變化性的網頁篡改識別模型及方法［J］.計算機應用，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

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

王衛紅（1969-），男，教授，主研方向：空間信息服務，網絡信息安全；李 君，碩士研究生。

2015?01?30

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