一般間隙和長度約束的嚴(yán)格近似模式匹配.pdf

1、模式匹配（也稱為串匹配）是計算機科學(xué)中基本問題之一，在諸多研究領(lǐng)域都有著十分廣泛的應(yīng)用。近年來具有間隙約束的模式匹配在音樂信息檢索和序列模式挖掘中得到了應(yīng)用。在模式匹配中，有的僅僅考慮最后一個模式子串在序列中匹配的位置，這種模式匹配稱為寬松模式匹配；更為挑戰(zhàn)性的問題是對每個模式串均考慮其在序列串中匹配的位置，而這種模式匹配稱為嚴(yán)格模式匹配。嚴(yán)格模式匹配問題能夠計算出在給定序列中某種模式的出現(xiàn)頻度，進(jìn)而判定該模式的頻繁性，因此嚴(yán)格模式匹配

2、問題是具有間隙約束的序列模式挖掘問題的核心工作之一。在具有間隙約束的模式匹配問題中模式P可以描述為p0[min0, max0]p1…[minj-1, maxj-1]pj…[minm-2, maxm-2]pm-1的形式，這里的minj-1和maxj-1分別描述字符pj-1和pj之間可以通配的最小和最大字符的數(shù)量，更為一般性的研究是模式P中的字符pj-1和pj之間的間隙值可以為負(fù)。目前模式匹配問題主要是針對精確模式匹配的，而在實際研究過程中

3、更多情形屬于近似模式匹配，因此與精確模式匹配相比，近似模式匹配是更為一般性的問題。
　　本文對更具有一般性的嚴(yán)格近似模式匹配進(jìn)行研究，提出了Hamming距離下間隙約束值可以為負(fù)值的一般間隙以及長度約束的嚴(yán)格近似模式匹配問題。論文首先給出了該問題的形式化定義；在此基礎(chǔ)上，證明了一個SAP問題實例可以轉(zhuǎn)換為指數(shù)個對應(yīng)精確模式匹配問題實例；論文將SAP問題轉(zhuǎn)化為一棵子網(wǎng)樹并運用子網(wǎng)樹結(jié)構(gòu)設(shè)計了一個有效的在線求解算法并證明了算法的完備性