基于后綴數(shù)組的字符串模式查找的算法.pdf

1、模式匹配問題是計(jì)算機(jī)科學(xué)的一個(gè)基本問題。在早期的模式匹配研究中,多數(shù)算法集中于精確模式匹配的研究,如:著名的單模式匹配算法KMP、BM及多模式匹配算法CA、CW、BNDM等。但在實(shí)際應(yīng)用中,近似模式匹配算法在信息過濾及計(jì)算生物學(xué)等領(lǐng)域顯得非常重要。比如人們通常在DNA的片段分析中,只是尋找到與目標(biāo)模式相似的DNA片段,從而判斷它們之間是否有親緣關(guān)系等等。要在海量的信息中快速地找到有意義的模式串,運(yùn)用一般的方法進(jìn)行模式查找,所花費(fèi)的時(shí)間讓

2、人難以忍受,為了提高模式查找算法的運(yùn)行效率,這里提出了模式查找的新算法。
　　本文是針對長篇英文小說中的高頻詞(模式串)查找問題,應(yīng)用了近似串匹配的過濾的思想,提出了模式查找的算法Epattern_searcherH和Epattern_searcher。
　　本論文的主要工作如下:
　　(1)提出了模式查找的算法。針對近似模式匹配中過濾思想設(shè)計(jì)模式查找的算法,首先按照一定的過濾原則(某種條件限定)搜索文本串,過濾掉那些

3、不可能發(fā)生匹配的的文本段;然后驗(yàn)證剩下的匹配候選位置處是否真的存在成功匹配。由于過濾去了大部分不可能發(fā)生匹配的文本串,加速了匹配的查找過程,從而達(dá)到提高模式查找算法運(yùn)行效率的目的。
　　(2)應(yīng)用后綴數(shù)組的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)提出的算法。對于字符串處理問題,后綴樹是一種很好的數(shù)據(jù)結(jié)構(gòu),但后綴樹需要占用較大內(nèi)存空間,而空間問題一直是運(yùn)用后綴樹數(shù)據(jù)結(jié)構(gòu)來處理超長字符串的一個(gè)瓶頸。與后綴樹結(jié)構(gòu)相比,后綴數(shù)組可節(jié)約三分之二以上的空間,因此這里運(yùn)