資源描述：
《正則表達(dá)式匹配算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、碩士學(xué)位論文MASTER?SDISSERTATION論文題目正則表達(dá)式匹配算法研究作者姓名陳航宇學(xué)科專業(yè)軟件工程指導(dǎo)教師王璿副教授2016年05月中圖分類號(hào)：TP312學(xué)校代碼：10216UDC：621.3密級(jí)：公開工學(xué)碩士學(xué)位論文正則表達(dá)式匹配算法研究碩士研究生：陳航宇導(dǎo)師：王璿副教授申請(qǐng)學(xué)位：工學(xué)碩士學(xué)科專業(yè)：軟件工程所在單位：信息科學(xué)與工程學(xué)院答辯日期：2016年5月授予學(xué)位單位：燕山大學(xué)ADissertationinSoftwareEngineeringRESEARCHONREGULAREXPRESSIONMATCHINGALGORITHMByC
2、henHangyuSupervisor:ProfessorWangXuanYanshanUniversityMay,2016燕山大學(xué)碩士學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：此處所提交的碩士學(xué)位論文《正則表達(dá)式匹配算法研究》，是本人在導(dǎo)師指導(dǎo)下，在燕山大學(xué)攻讀碩士學(xué)位期間獨(dú)立進(jìn)行研究工作所取得的成果。論文中除已注明部分外不包含他人已發(fā)表或撰寫過的研究成果。對(duì)本文的研究工作做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式注明。本聲明的法律結(jié)果將完全由本人承擔(dān)。作者簽字：日期：年月日燕山大學(xué)碩士學(xué)位論文使用授權(quán)書《正則表達(dá)式匹配算法研究》系本人在燕山大學(xué)攻讀碩士學(xué)位
3、期間在導(dǎo)師指導(dǎo)下完成的碩士學(xué)位論文。本論文的研究成果歸燕山大學(xué)所有，本論文的研究?jī)?nèi)容不得以其它單位的名義發(fā)表。本人完全了解燕山大學(xué)關(guān)于保存、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向有關(guān)部門送交論文的復(fù)印件和電子版本，允許論文被查閱和借閱。本人授權(quán)燕山大學(xué)，可以采用影印、縮印或其它復(fù)制手段保存論文，可以公布論文的全部或部分內(nèi)容。保密□，在年解密后適用本授權(quán)書。本學(xué)位論文屬于不保密□。(請(qǐng)?jiān)谝陨舷鄳?yīng)方框內(nèi)打“√”)作者簽名：日期：年月日導(dǎo)師簽名：日期：年月日摘要摘要正則表達(dá)式匹配是從文本中找出與給定正則表達(dá)式匹配的所有字符序列的起始和結(jié)束位置，該操作在文本編輯、
4、生物信息學(xué)、模式識(shí)別等領(lǐng)域有著重要的應(yīng)用。通過分析發(fā)現(xiàn)現(xiàn)存方法需要對(duì)文本建立后綴樹索引，而本文后綴樹索引空間大，建樹過程復(fù)雜且查找正則表達(dá)式的前綴、后綴位置信息時(shí)需要遍歷整個(gè)后綴樹效率較低。為了提高匹配效率，本文從以下幾個(gè)方面對(duì)正則表達(dá)式匹配問題進(jìn)行了深入研究：首先，提出了基于數(shù)組索引的訪問策略，該策略先查詢正則表達(dá)式中一定出現(xiàn)的字符序列的位置，然后根據(jù)這些位置進(jìn)行對(duì)正則表達(dá)式左右匹配，最后找出能夠與此正則表達(dá)式匹配的所有位置，從而避免遍歷整個(gè)后綴樹，并提出了基于上述策略的正則表達(dá)式匹配算法-Match算法。其次，針對(duì)在正則表達(dá)式的匹配階段存在的冗余計(jì)算
5、問題，提出了新的匹配方法，即依照出現(xiàn)次數(shù)最少的字符序列位置進(jìn)行左右匹配；根據(jù)左右匹配的不同限制以及以前方法的過濾思想提出了兩種過濾策略，即左右匹配的過濾策略和基于消極因子的過濾策略，進(jìn)一步減少了候選結(jié)果和驗(yàn)證時(shí)間，從而提高算法的執(zhí)行效率。最后，在不同特征數(shù)據(jù)集上，通過比較同一正則表達(dá)式的匹配時(shí)間，將Match算法與當(dāng)前最好的正則表達(dá)式匹配算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提算法的高效性。關(guān)鍵詞：正則表達(dá)式；后綴樹；Match算法；過濾策略I燕山大學(xué)工學(xué)碩士學(xué)位論文AbstractRegularexpressionmatchingistofindthest
6、artingpositionandtheendingpositionofthecharactersequencematchingthegivenregularexpressionfromthetext,theoperationhasimportantapplicationsintextediting,bioinformatics,patternrecognition,etc.Throughanalyzingtheexistingmethods,theresultsfindthattheexistingmethodsneedtobuildasuffixtr
7、eeindex.Andthesuffixtreeindexspaceisbig,establishingprocessiscomplexandlocatingtheinformationofregularexpressionprefixandsuffixneedstotraversetheentiresuffixtree，whichhaslowefficiency.Inordertoimprovetheefficiency,thisarticlestudiesthematchingquestionofregularexpressionfromthefol
8、lowingseveralaspects:Firstly,puttingacce
