基于后綴數(shù)組的近似字符串匹配.pdf

1、字符串匹配問題是計算機(jī)科學(xué)研究中最基礎(chǔ)的問題之一。早期的研究多集中于精確字符串匹配領(lǐng)域，就精確字符串匹配提出了許多單模式和多模式匹配算法。然而在信息檢索、模式識別和計算生物學(xué)等一些實(shí)際應(yīng)用中有時候更需要查找的是近似匹配字符串。因此研究高效的近似字符串匹配算法具有重要的理論價值和實(shí)際意義。
　　本文首先介紹了近似字符串匹配算法的研究現(xiàn)狀和近似字符串的相關(guān)理論和主要研究方法—動態(tài)規(guī)劃、自動機(jī)、位并行、過濾等技術(shù)。結(jié)合后綴數(shù)組這一索引結(jié)

2、構(gòu)，本文提出了基于后綴數(shù)組的近似字符串匹配算法，即IS-DP算法。算法使用后綴數(shù)組加快在動態(tài)規(guī)劃矩陣上的迭代速度，從而達(dá)到O(kn)的時間復(fù)雜度和空間復(fù)雜度。用后綴數(shù)組構(gòu)造算法可以預(yù)先排序文本串后綴，求解后綴數(shù)組中相鄰后綴的最長公共前綴，從而可以在O(1)時間內(nèi)計算出任意兩個后綴串的最長共有前綴長度。本文算法是對原有的基于動態(tài)規(guī)劃的近似字符串匹配算法的改進(jìn)，通過加速矩陣對角線上擴(kuò)展的方式降低了構(gòu)造動態(tài)規(guī)劃矩陣的時間消耗，進(jìn)而在O(kn)