支持編輯距離約束的近似最長公共子串匹配及其優(yōu)化算法.pdf

1、目前許多信息都以文本的形式存放在計算機(jī)中，所以基于文本的信息檢索技術(shù)，如最長公共子串匹配問題一直是文本管理、程序分析等領(lǐng)域的經(jīng)典問題，長期以來受到廣泛地關(guān)注與研究。
　　然而最長公共子串的要求過于嚴(yán)格，在實(shí)際應(yīng)用中，兩個局部非常相似的文本其中的公共部分往往不是完全精確匹配的，因此需要提供支持近似匹配的最長公共子串匹配方法。目前尚未有相關(guān)技術(shù)的報道。因此，本文重點(diǎn)研究支持編輯距離約束的近似最長公共子串匹配問題。
　　本文首先綜

2、述了現(xiàn)有的字符串近似匹配技術(shù)，并基于此，提出了一種基于動態(tài)規(guī)劃的算法，這個算法首先用最長公共子串的動態(tài)規(guī)劃算法求出公共子串，再用編輯距離和最長公共子序列的動態(tài)規(guī)劃方法，計算具有公共前綴的子串組成的比對區(qū)域，找到所有支持編輯距離約束的近似公共子串，最后進(jìn)行長度驗(yàn)證找到支持編輯距離約束的近似最長公共子串。該算法可以保證O(kmn)的時間復(fù)雜度。為了進(jìn)一步提高算法的效率，本文提出了基于后綴數(shù)組的公共子串匹配優(yōu)化算法。該算法先采用后綴數(shù)組的方法

3、求出所有公共子串，再將相鄰連接距離不大于編輯距離閾的公共子串連接起來構(gòu)造驗(yàn)證集，在構(gòu)造驗(yàn)證集的過程中采用了基于公共子串位置和基于公共子串間距離的過濾策略，最后用啟發(fā)式的方法在驗(yàn)證集中找出支持編輯距離約束的近似最長公共子串，提高了查詢效率。
　　最后，本文在三個不同的真實(shí)數(shù)據(jù)集上測試了這兩種算法的性能，基于動態(tài)規(guī)劃的算法，由于需要對所有具有相同前綴開始的比對區(qū)域進(jìn)行動態(tài)規(guī)劃計算，所以算法的性能比基于公共子串的查詢算法差。實(shí)驗(yàn)發(fā)現(xiàn)，基