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

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

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

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