發(fā)布時(shí)間：2021-10-24 16:57

　　隨著網(wǎng)絡(luò)設(shè)備軟硬件技術(shù)的提高和網(wǎng)絡(luò)用戶的日益增加,網(wǎng)絡(luò)上的數(shù)據(jù)流量正在以爆發(fā)式的趨勢(shì)增長(zhǎng)。隨著大數(shù)據(jù)相關(guān)科技的發(fā)展,大數(shù)據(jù)的處理算法面臨著更加嚴(yán)峻的挑戰(zhàn),模式匹配作為許多前沿技術(shù)的基礎(chǔ)而被廣泛研究,而模式匹配的一個(gè)分支——字符串近似匹配往往用于信息搜索、安全檢測(cè)、生物計(jì)算等。提高解決大數(shù)據(jù)應(yīng)用問題的高性能近似模式匹配算法之性能是當(dāng)前一個(gè)極具探索價(jià)值的問題。本文引入了一類新型近似模式匹配問題——允許文本中相鄰兩字符交換的近似匹配算法,并提出了相應(yīng)算法以及理論分析和實(shí)驗(yàn)。首先定義了交換的概念,交換是文本中相鄰的互不相同的兩字符的交換。字符串的交換版本是該字符串經(jīng)過幾次交換操作而轉(zhuǎn)換成的字符串。本文提出了一種允許文本中相鄰兩字符交換的近似匹配算法,該算法首先采用過濾的思想將文本串劃分為兩個(gè)文本段集合:不匹配集合與候選段集合。我們改進(jìn)以往的近似串匹配算法,將算法的適用范圍擴(kuò)展到額外允許出現(xiàn)交換的情況。與已有的相關(guān)算法不同,該算法能夠更加符合現(xiàn)實(shí)應(yīng)用的要求,具有一定的實(shí)用性。另外為了提高匹配效率,我們?cè)谏鲜鲞^濾思想的基礎(chǔ)上,直接過濾掉不可能發(fā)生匹配的匹配集合,將改進(jìn)的近似匹配算法應(yīng)用到候選段集合... 

【文章來源】：吉林大學(xué)吉林省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：64 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

有限模式匹配自動(dòng)機(jī)如圖2.1所示自動(dòng)機(jī)，自動(dòng)機(jī)的第i行代表進(jìn)行到當(dāng)前行中狀態(tài)時(shí)已經(jīng)出現(xiàn)

圖 2.2 變量打包字節(jié)具體計(jì)算過程如下：1. 將四個(gè)數(shù)字如上述打包到一個(gè)機(jī)器字 V 中。2. addone ← 00000001 00000001 00000001 000000013. V += addone4. return V由此可見位并行算法的效率要比串行方法高數(shù)倍，另外如果存儲(chǔ)一個(gè)單位所需的字節(jié)數(shù)越少，一個(gè)機(jī)器字所能容納的元素?cái)?shù)量就越多，效率就越高。一個(gè)種常見的字符串匹配算法的位并行實(shí)現(xiàn)首先是運(yùn)用在精確模式匹配算法上，隨后對(duì)精確模式匹配算法進(jìn)行改進(jìn)，形成了一種近似串模式匹配算法的位并行實(shí)現(xiàn)。精確串模式匹配位并行實(shí)現(xiàn)：定義一個(gè)數(shù)組 R 來表示文本串當(dāng)前位置與模式串的匹配情況，該數(shù)組的取值

因此 L[ d][e]> i，這與假設(shè)相矛盾，證同樣為 O (mn)，但是空間復(fù)雜度相較于Morris 和 V.R.Pratt 三人根據(jù)暴力匹配想，該算法使用三人姓名的縮寫被稱為 K效快速的算法之一[18]。配字符串的算法中模式串首先從文本串不匹配則從文本串第二位重新匹配，以此結(jié)束。

【參考文獻(xiàn)】：
期刊論文
[1]網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)中的模式匹配算法設(shè)計(jì)優(yōu)化[J]. 陳卓民.  電子設(shè)計(jì)工程. 2018(15)
[2]模式匹配算法的研究與實(shí)現(xiàn)[J]. 李萍,趙潤(rùn)林.  電腦知識(shí)與技術(shù). 2017(18)
[3]氨基酸序列特征向量提取方法的探討[J]. 譚生龍.  電腦知識(shí)與技術(shù). 2016(22)
[4]應(yīng)用Q-gram命中特征優(yōu)化的近似串匹配算法[J]. 王曉霞,孫德才.  電子設(shè)計(jì)工程. 2016(15)
[5]一種改進(jìn)的BM模式匹配算法[J]. 蔣亞平,田月霞,趙軍偉.  科技通報(bào). 2015(09)
[6]近似串匹配過濾算法研究[J]. 孫德才,王曉霞.  計(jì)算機(jī)技術(shù)與發(fā)展. 2015(04)
[7]基于WM算法改進(jìn)的多模式匹配算法[J]. 董迎亮,玄雪花,王德民.  吉林大學(xué)學(xué)報(bào)(信息科學(xué)版). 2011(04)
[8]改進(jìn)的近似模式匹配算法[J]. 張麗霞,宋鴻陟.  計(jì)算機(jī)工程與設(shè)計(jì). 2011(05)
[9]一種改進(jìn)的模式匹配算法[J]. 田宏,李君秋.  大連交通大學(xué)學(xué)報(bào). 2010(04)
[10]一種基于有限自動(dòng)機(jī)的快速串匹配算法[J]. 陳倩.  計(jì)算機(jī)技術(shù)與發(fā)展. 2009(01)

碩士論文
[1]相似字符串查找算法研究[D]. 黃厚柱.安徽大學(xué) 2017
[2]基于網(wǎng)絡(luò)安全系統(tǒng)的大規(guī)模模式集合匹配算法的研究[D]. 姜麗麗.東南大學(xué) 2015
[3]基于局部過濾的字符串近似匹配算法和優(yōu)化技術(shù)[D]. 王堯舒.東北大學(xué) 2014
[4]網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)中模式匹配算法的應(yīng)用研究[D]. 劉鑫.大連海事大學(xué) 2013
[5]單模式字符串匹配算法效率的研究[D]. 潘冠樺.太原理工大學(xué) 2013
[6]基于后綴數(shù)組的近似字符串匹配[D]. 張喜娟.西安電子科技大學(xué) 2012
[7]編輯距離快速算法研究[D]. 王培培.東北大學(xué) 2011
[8]程序代碼抄襲檢測(cè)中串匹配算法的研究與實(shí)現(xiàn)[D]. 王春暉.內(nèi)蒙古師范大學(xué) 2008
[9]網(wǎng)絡(luò)內(nèi)容過濾關(guān)鍵技術(shù)與研究[D]. 徐國(guó)勝.電子科技大學(xué) 2007
[10]用位并行法進(jìn)行過濾的中文近似串匹配算法[D]. 范立新.浙江大學(xué) 2006



本文編號(hào)：3455636