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

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

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

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