【摘要】：模式匹配(也稱為串匹配)是計(jì)算機(jī)科學(xué)中基本問題之一,已經(jīng)廣泛地應(yīng)用到了生物研究、音樂信息檢索和序列模式挖掘等各個(gè)領(lǐng)域。在模式匹配中,有的僅僅考慮最后一個(gè)模式子串在序列中匹配的位置,這種模式匹配稱為寬松模式匹配;更為挑戰(zhàn)性的問題是對(duì)每個(gè)模式串均考慮其在序列串中匹配的位置,而這種模式匹配稱為嚴(yán)格模式匹配。嚴(yán)格模式匹配中近似模式匹配允許模式串與所匹配的序列串之間存在一定差異,增加了匹配的靈活性。本文研究的是具有Hamming距離的近似模式匹配。無重疊約束是要求任何兩個(gè)出現(xiàn)中不能在相同位置處使用序列中相同字符。具有無重疊約束的模式匹配問題是指給定模式P在序列S中的所有出現(xiàn)集合中找到最大子集C,使得集合C中任意兩個(gè)出現(xiàn)均是無重疊的出現(xiàn)。目前研究的模式匹配多為精確匹配,精確匹配要求每個(gè)字符必須匹配,一定程度上限定了匹配的靈活性。為此本文提出了無重疊約束的近似模式匹配問題(Approximate Pattern matching with Non-Overlapping constraints,APNO)。我們運(yùn)用網(wǎng)樹結(jié)構(gòu)解決該問題,提出了NETLOR和NETROL算法,并對(duì)其改進(jìn)提出了NETLORE和NETROLE算法。該算法在求解時(shí),先將模式匹配問題轉(zhuǎn)換為一棵網(wǎng)樹,然后在網(wǎng)樹中每次查找樹根葉子路徑,并將該路徑所對(duì)應(yīng)的解作為一個(gè)無重疊近似出現(xiàn),之后依據(jù)樹根葉子路徑在網(wǎng)樹的局部范圍內(nèi)進(jìn)行快速剪枝,為下一次查找樹根葉子路徑做準(zhǔn)備。最后大量實(shí)驗(yàn)驗(yàn)證了本文提出的四個(gè)算法的正確性,并且驗(yàn)證了NETLORE是更為高效的算法。
[Abstract]:Pattern matching (also called string matching) is one of the basic problems in computer science, which has been widely used in biological research, music information retrieval and sequential pattern mining and other fields. In pattern matching, some only consider the position of the last pattern string matching in the sequence, this pattern matching is called loose pattern matching; the more challenging problem is that each pattern string considers its matching position in the sequence string. This pattern matching is called strict pattern matching. In strict pattern matching, approximate pattern matching allows some difference between pattern string and matching sequence string, which increases the flexibility of matching. In this paper, approximate pattern matching with Hamming distance is studied. No overlap constraint requires any two occurrences not to use the same characters in the sequence at the same location. The problem of pattern matching with no overlap constraint is that given pattern P finds the largest subset C in all appearance sets of sequence S so that any two occurrences in set C are non-overlapping. At present, the pattern matching is mostly precise matching, which requires each character to match, which limits the flexibility of matching to a certain extent. In this paper, an approximate pattern matching problem without overlapping constraints, (Approximate Pattern matching with Non-Overlapping constraints, is proposed. We use the net tree structure to solve this problem, propose NETLOR and NETROL algorithms, and propose NETLORE and NETROLE algorithms to improve them. In the algorithm, the pattern matching problem is first transformed into a net tree, and then the root leaf path of the tree is searched in the network tree each time, and the corresponding solution of this path appears as a non-overlapping approximation. Then pruning is carried out in the local area of the web tree according to the tree root leaf path to prepare for the next search of the tree root leaf path. Finally, a large number of experiments verify the correctness of the proposed four algorithms, and verify that NETLORE is a more efficient algorithm.
【學(xué)位授予單位】：河北工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP391.1

【參考文獻(xiàn)】

相關(guān)期刊論文 前7條

1 柴欣;賈曉菲;武優(yōu)西;江賀;吳信東;;一般間隙及一次性條件的嚴(yán)格模式匹配[J];軟件學(xué)報(bào);2015年05期

2 武優(yōu)西;劉亞偉;郭磊;吳信東;;子網(wǎng)樹求解一般間隙和長(zhǎng)度約束嚴(yán)格模式匹配[J];軟件學(xué)報(bào);2013年05期

3 黃國(guó)林;郭丹;胡學(xué)鋼;;基于通配符和長(zhǎng)度約束的近似模式匹配算法[J];計(jì)算機(jī)應(yīng)用;2013年03期

4 李艷;孫樂;朱懷忠;武優(yōu)西;;網(wǎng)樹求解有向無環(huán)圖中具有長(zhǎng)度約束的簡(jiǎn)單路徑和最長(zhǎng)路徑問題[J];計(jì)算機(jī)學(xué)報(bào);2012年10期

5 黃國(guó)林;郭丹;胡學(xué)鋼;;求解近似模式匹配的啟發(fā)式算法[J];計(jì)算機(jī)科學(xué)與探索;2013年01期

6 武優(yōu)西;吳信東;江賀;閔帆;;一種求解MPMGOOC問題的啟發(fā)式算法[J];計(jì)算機(jī)學(xué)報(bào);2011年08期

7 陸麗娜,魏恒義,楊怡玲,管旭東;Web日志挖掘中的序列模式識(shí)別[J];小型微型計(jì)算機(jī)系統(tǒng);2000年05期

，

本文編號(hào)：2154835