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

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

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