編輯距離快速算法研究.pdf

1、字符串匹配技術(shù)是計(jì)算機(jī)科學(xué)中研究最為廣泛的問題之一，在眾多領(lǐng)域中發(fā)揮著重要的作用。通常，衡量兩個(gè)字符串之間的匹配程度是通過計(jì)算兩個(gè)字符串之間的距離函數(shù)來確定的，而編輯距離是衡量兩個(gè)字符串的匹配程度最常用的距離函數(shù)指標(biāo)。所以，編輯距離問題已經(jīng)成為信息理論和計(jì)算機(jī)科學(xué)研究領(lǐng)域中的一個(gè)重點(diǎn)問題。
　　編輯距離又稱Levenshtein距離，是由俄羅斯科學(xué)家Vladimir Levenshtein在1965年提出的。目前，計(jì)算編輯距離最常

2、使用的算法是動態(tài)規(guī)劃算法。動態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為O(mn)，時(shí)間開銷很大，尋找一種新的編輯距離快速算法意義重大?；诖?，本文對編輯距離算法作進(jìn)一步的研究和改進(jìn)。
　　本文的主要內(nèi)容為:首先對字符串相似匹配進(jìn)行了定義，介紹了近似字符串相似匹配相關(guān)技術(shù)的理論及主要研究方法，并對基于FFT(快速傅里葉變換)的序列相似性進(jìn)行了研究。為了實(shí)現(xiàn)編輯距離的快速計(jì)算，本文利用快速傅里葉變換和線性卷積的思想，首先提出了一種新的距離函數(shù):基于FF

3、T的字符串距離函數(shù)FFT-D，并利用字符串距離函數(shù)FFT-D提出了字符串過濾方法，通過對數(shù)據(jù)集的過濾，實(shí)現(xiàn)減少一些不必要的編輯距離計(jì)算，從而提高了字符串匹配的效率。最后，本文還提出了基于線性卷積思想的編輯距離LC-ED算法，該算法的最重要特點(diǎn)就是利用插入空格代替插入和刪除操作，即通過對兩個(gè)字符串序列的不同位置比對，找到插入空位的數(shù)量以及位置，從而實(shí)現(xiàn)編輯距離的快速計(jì)算。該算法在理論上和實(shí)踐中均有較好的表現(xiàn)。實(shí)驗(yàn)測試表明本文所提出的方法可