◆歐曉聰

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

◆歐曉聰

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

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

1 概述

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

2 相關(guān)工作

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

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

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

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

證明：

由上述證明過程遞歸得：

證明：

3.3 優(yōu)化算法設(shè)計(jì)與分析

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

圖1 矩陣M中的一組元素

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

圖2中淺色背景為參考值比真實(shí)值大的元素，深色背景為可能因此而受影響的區(qū)域，該區(qū)域?yàn)樵撛卣路郊靶焙蠓剿鼑鷧^(qū)域，即在計(jì)算過程中該元素直接參與或遞歸參與的元素。但通過證明可發(fā)現(xiàn)，受其影響區(qū)域有限，算法本身具有一定的糾錯(cuò)能力。

證明：

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

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

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

3.4 實(shí)驗(yàn)

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

圖5 序列長度分布

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

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

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

實(shí)驗(yàn)機(jī)器主要配置如表2所示。

表2 實(shí)驗(yàn)用機(jī)主要配置信息

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

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

圖6 算法效率對比圖

4 結(jié)束語

本文提出了一種新的基于經(jīng)典算法的編輯距離求解算法，該算法利用了經(jīng)典算法中所蘊(yùn)含的自動(dòng)糾錯(cuò)機(jī)制，在一定程度上降低了編輯距離求解算法的時(shí)空復(fù)雜。本算法最大特點(diǎn)是不依賴于對原始序列的元素排列分析。事實(shí)上，本文只評估了參考值與真實(shí)值偏差的上限，但如能發(fā)現(xiàn)參考值與真實(shí)值偏差下限就可以繼續(xù)減少時(shí)空復(fù)雜度。如果需要在本算法的基礎(chǔ)上繼續(xù)實(shí)施優(yōu)化，就需要對元素排列進(jìn)行快速且有效的分析。在算法的論證與研究過程中，發(fā)現(xiàn)似乎參考值與真實(shí)值偏差的下限與序列元素間的某種概率相關(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]鄭榮鋒，方勇，劉亮.基于動(dòng)態(tài)行為指紋的惡意代碼同源性分析[J].四川大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，53（04）：793-798.

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

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

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

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

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

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

[9]王衛(wèi)紅，李君.基于局部變化性的改進(jìn)編輯距離算法[J]. 計(jì)算機(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.