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

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

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