無重疊條件下嚴格模式匹配的研究.pdf

1、序列模式挖掘是數(shù)據(jù)挖掘分支，而序列模式匹配是序列模式挖掘的重要基礎。將挖掘方法用于生物序列、顧客購買序列、網(wǎng)絡日志的分析，我們可從大數(shù)據(jù)中獲取各種潛在的規(guī)律和感興趣的信息。在這些研究中，帶有通配符間隙約束的生物序列匹配和挖掘比傳統(tǒng)的串匹配方法更具有挑戰(zhàn)性，且衍生出諸多種類的條件和約束。有一種方法是建立在無重疊條件基礎上的模式匹配，該問題是當給定具有間隙約束的模式串時，在給定的序列中找到滿足無重疊約束的最多出現(xiàn)，而無重疊出現(xiàn)是指任何兩個出

2、現(xiàn)中不能在相同位置處使用相同字符。因此本文對無重疊約束的嚴格模式匹配問題進行研究。
　　本文的主要研究內(nèi)容和相關工作如下：
　?。?）給出了無重疊約束模式匹配的嚴格形式化定義；
　?。?）理論證明了無重疊約束模式匹配的計算復雜性是P的，即無重疊約束模式匹配是具有多項式時間的確定性算法來求解的判定問題；
　?。?）采用網(wǎng)樹結構構造了完備性求解算法NETLAP-Best算法；
　?。?）大量對比性實驗驗證了NE