一般間隙與one-off條件的序列模式匹配

　　帶有間隙約束的模式匹配問題是序列模式挖掘的關(guān)鍵問題之一．目前大多數(shù)的研究都為非負(fù)間隙，對(duì)字符串中的每個(gè)字符的出現(xiàn)順序有著嚴(yán)格的要求．為了增加匹配的靈活性，并且考慮到在序列模式挖掘中采用one-off條件更加合理，研究一般間隙與one-off條件下的模式匹配問題，該問題為NP-Hard問題．為了有效的求解該問題，提出了MSAING（Maximum Sequential pattern mAtching wlth oNe-off and General gaps condition）算法，首先利用Reverse策略使模式與序列達(dá)到最佳的匹配狀態(tài)：然后，使用線性表的結(jié)構(gòu)使匹配過程中消耗的時(shí)間和空間大幅度的降低，同利用回溯機(jī)制提高匹配的成功率；最后，根據(jù)inside_Checking機(jī)制，判斷模式串是否會(huì)產(chǎn)生內(nèi)部重復(fù)現(xiàn)象，進(jìn)一步提高算法的執(zhí)行效率．理論證明了MSAING算法的完備性。實(shí)驗(yàn)結(jié)果驗(yàn)證了MSAING算法匹配結(jié)果的準(zhǔn)確性，以及在時(shí)間和空間方面的高效性。