基于自動糾錯的最小編輯距離優(yōu)化算法

◆歐曉聰

基于自動糾錯的最小編輯距離優(yōu)化算法

◆歐曉聰

（四川大學網(wǎng)絡空間安全學院 四川 610065）

算法優(yōu)化，最小編輯距離，動態(tài)規(guī)劃，自動糾錯

1 概述

最小編輯距離是為解決語義的相似性而提出[1]，然而詞語形式上的“差之千里”會導致語義中的“謬以千里”，因此最小編輯距離并未能在語義相似性計算中占據(jù)一席之地。但是最小編輯距離作為一種相似度計算函數(shù)具有極高的抗噪性，能夠很好描述序列間差異性。隨著機器學習領(lǐng)域的飛速發(fā)展，越來越多的算法通過引入最小編輯距離來衡量特征間關(guān)系，以此提高算法準確率。例如：鄭榮鋒等人使用編輯距離在信息安全領(lǐng)域識別惡意軟件特征[2]；袁二毛等人使用編輯距離挖掘生物序列頻繁模式[3]；李勃昊等人使用最小編輯距離作為代價函數(shù)構(gòu)建聲學分段模型[4]；王汀等人將最小編輯距離運用到本體映射取得了良好的總體性能[5]；韓博洋等人使用編輯距離在k-means算法中計算軌跡與聚類中心距離以實現(xiàn)出租車異常軌跡的檢測[6]；陳裕潮等人在模式識別中運用最小編輯距離檢測輪胎模具表面字符[7]。但是編輯距離經(jīng)典算法時空復雜度高，為了降低算法時空復雜度本文提出了編輯距離優(yōu)化算法，該算法不依賴于序列間元素排列方式，只依賴于序列長度。

2 相關(guān)工作

3 經(jīng)典算法優(yōu)化

3.1 經(jīng)典算法原理

任意兩序列間編輯距離是指使用限定操作：修改序列中一個元素、增加序列中一個元素和刪除序列中一個元素，通過上述三種操作將其中一個序列變化為另一個序列的次數(shù)，而最小編輯距離是指變換最少操作的次數(shù)。為了求解最小編輯距離，Levenshtein提出了一種基于動態(tài)規(guī)劃求解算法，該算法緊扣動態(tài)規(guī)劃核心思想，將序列間最小編輯距離求解轉(zhuǎn)化為序列子序列間的最小編輯距離求解。因此，Levenshtein設計了一個二維矩陣實現(xiàn)該算法。

3.2 經(jīng)典算法數(shù)學特性論證

證明：

由上述證明過程遞歸得：

證明：

3.3 優(yōu)化算法設計與分析

該組元素滿足行下標從1逐次增大、列下標從任意下標逐次增大。

圖1 矩陣M中的一組元素

圖2 當參考值大于真實值時可能受影響區(qū)域

圖2中淺色背景為參考值比真實值大的元素，深色背景為可能因此而受影響的區(qū)域，該區(qū)域為該元素正下方及斜后方所包圍區(qū)域，即在計算過程中該元素直接參與或遞歸參與的元素。但通過證明可發(fā)現(xiàn)，受其影響區(qū)域有限，算法本身具有一定的糾錯能力。

證明：

圖3 極端情形下估計值錯誤區(qū)域

圖3所示陰影部分為極端情形下參考值錯誤區(qū)域，在該狀態(tài)下錯誤參考值區(qū)域最大，參考值偏離真實值最遠。如果能夠給出足夠的區(qū)域來滿足參考值錯誤區(qū)間的自動糾差過程，就能夠在錯誤區(qū)域外保障參考值與真實值一致。

圖4 經(jīng)典算法求解區(qū)域與優(yōu)化算法求解區(qū)域疊加圖

3.4 實驗

由于經(jīng)典算法同優(yōu)化算法的時空復雜度對序列元素排列順序不敏感、與序列長度相關(guān)，所以本文實驗采用如下三個數(shù)據(jù)集：2006年《自然綜述：微生物學》數(shù)據(jù)集RRM，該數(shù)據(jù)集一共包含299條蛋白質(zhì)序列[11]；DBLP中AUTHOR數(shù)據(jù)集，該數(shù)據(jù)集一共包含12315763個人名；國外知名web2.0網(wǎng)站delicious（www.delicious.com）中用戶對條目的標注數(shù)據(jù)集BOOKMARK，該數(shù)據(jù)集一共包含3767462個條目。數(shù)據(jù)集中序列長度與序列個數(shù)分布如圖5所示。

圖5 序列長度分布

在如圖5所示的序列長度分布中，RRM數(shù)據(jù)集單個序列長度分布不集中，在圖5（a）所示的分布表示以50為間隔的范圍分布；而（b）（c）表示為普通序列長度分布。由此可見，RRM數(shù)據(jù)集的序列長度集中在250到300間；AUTHOR數(shù)據(jù)集的序列長度集中在10到20間；BOOKMARK數(shù)據(jù)集的序列長度集中在1到20間。三個數(shù)據(jù)集的一般序列長度統(tǒng)計信息如表1所示。

表1 數(shù)據(jù)集序列長度統(tǒng)計信息

如表1所示，實驗所選用數(shù)據(jù)集長度基本特定分散，眾數(shù)偏差大，能夠有效驗證數(shù)據(jù)集長度同算法效率間關(guān)系。

實驗機器主要配置如表2所示。

表2 實驗用機主要配置信息

實驗方法如下，從數(shù)據(jù)集的長度最小值、長度最大值、長度眾數(shù)和長度中位數(shù)中分別隨機取出一條序列作為基準序列；使用本文優(yōu)化算法與經(jīng)典算法分別對基準序列與同一數(shù)據(jù)集中的序列一一比對，每次實驗有效算法執(zhí)行次數(shù)均為數(shù)據(jù)集大小。算法效率如圖6所示。

在圖6所示的經(jīng)典算法與優(yōu)化算法對比圖中橫坐標中的“min”表示基準序列為最小值，“mode”表示基準序列為眾數(shù)，“median”表示基準序列為中位數(shù)，“max”表示基準序列為最大值；縱坐標表示執(zhí)行算法所消耗的時間。由圖6可知，在三個數(shù)據(jù)集上、使用不同長度的基準序列，優(yōu)化算法較經(jīng)典算法效率都有明顯提升，并且隨著數(shù)據(jù)集中長度眾數(shù)的增大優(yōu)化算法的效率優(yōu)勢更突出。

圖6 算法效率對比圖

4 結(jié)束語

本文提出了一種新的基于經(jīng)典算法的編輯距離求解算法，該算法利用了經(jīng)典算法中所蘊含的自動糾錯機制，在一定程度上降低了編輯距離求解算法的時空復雜。本算法最大特點是不依賴于對原始序列的元素排列分析。事實上，本文只評估了參考值與真實值偏差的上限，但如能發(fā)現(xiàn)參考值與真實值偏差下限就可以繼續(xù)減少時空復雜度。如果需要在本算法的基礎(chǔ)上繼續(xù)實施優(yōu)化，就需要對元素排列進行快速且有效的分析。在算法的論證與研究過程中，發(fā)現(xiàn)似乎參考值與真實值偏差的下限與序列元素間的某種概率相關(guān)。該猜測需要后續(xù)工作論證求解。

[1]Levenshtein，Vladimir I. Binary codes capable of correcting deletions，insertions，and reversals[j]. Soviet Physics Doklady，1966，10（01）：707–710.

[2]鄭榮鋒，方勇，劉亮.基于動態(tài)行為指紋的惡意代碼同源性分析[J].四川大學學報（自然科學版），2016，53（04）：793-798.

[3]袁二毛，郭丹，胡學鋼，吳信東.基于打分矩陣的生物序列頻繁模式挖掘[J].模式識別與人工智能，2016，29（10）：894-906.

[4]李勃昊，張連海，鄭永軍.基于聲學分段模型的無監(jiān)督語音樣例檢測[J].數(shù)據(jù)采集與處理，2016，31（02）：407-414.

[5]王汀，徐天晟，冀付軍.基于數(shù)據(jù)場和全局序列比對的大規(guī)模中文關(guān)聯(lián)數(shù)據(jù)模型[J].中文信息學報，2016，30（03）：204-212.

[6]韓博洋，汪兆洋，金蓓弘. 一種基于軌跡大數(shù)據(jù)離線挖掘與在線實時監(jiān)測的出租車異常軌跡檢測算法[J].中國科學技術(shù)大學學報，2016，46（03）：247-252.

[7]陳裕潮，蔡念，劉根，張福，李沅時，王晗，陳新度. 一種基于機器視覺的輪胎模具表面字符檢測方法[J].鍛壓技術(shù)，2016，41（12）：127-130.

[8]張潤梁，牛之賢.基于基本操作序列的編輯距離順序驗證[J].計算機科學，2016，43（6A）：51-54.

[9]王衛(wèi)紅，李君.基于局部變化性的改進編輯距離算法[J]. 計算機工程，2015，41（07）：294-298+304.

[10]Li W S.Top-K String Similarity Search with Edit-Distance Constraints[C]//IEEE，International Conference on Data Engineering. IEEE，2013：925-936.

[11]Jennifer L. Gardy and Fiona S.L. Brinkman. Methods for predicting bacterial protein subcellular localization[J]， Nature Reviews Microbiology，2006，4（10）：741-751.