一般間隙與one-off條件的序列模式匹配
大小：0.96 MB 人氣： 2017-12-19 需要積分：3
標簽：序列(19484)
帶有間隙約束的模式匹配問題是序列模式挖掘的關鍵問題之一．目前大多數的研究都為非負間隙，對字符串中的每個字符的出現順序有著嚴格的要求．為了增加匹配的靈活性，并且考慮到在序列模式挖掘中采用one-off條件更加合理，研究一般間隙與one-off條件下的模式匹配問題，該問題為NP-Hard問題．為了有效的求解該問題，提出了MSAING（Maximum Sequential pattern mAtching wlth oNe-off and General gaps condition）算法，首先利用Reverse策略使模式與序列達到最佳的匹配狀態：然后，使用線性表的結構使匹配過程中消耗的時間和空間大幅度的降低，同利用回溯機制提高匹配的成功率；最后，根據inside_Checking機制，判斷模式串是否會產生內部重復現象，進一步提高算法的執行效率．理論證明了MSAING算法的完備性。實驗結果驗證了MSAING算法匹配結果的準確性，以及在時間和空間方面的高效性。
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%