資源描述：
《論文資料：基于sse指令集的串匹配算法優(yōu)化(》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、基于SSE指令集的串匹配算法優(yōu)化基金項(xiàng)目：國(guó)家973計(jì)劃重點(diǎn)基礎(chǔ)研究項(xiàng)目（2007CB311100）；國(guó)家242信息安全計(jì)劃項(xiàng)目（（242）2009A43）邵妍1,2,4,劉燕兵1,3,4,劉萍1,4,郭莉1,4（1.中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京100190；2.北京郵電大學(xué)，北京100876；3.中國(guó)科學(xué)院研究生院，北京100039；信息內(nèi)容安全技術(shù)國(guó)家工程實(shí)驗(yàn)室，北京100190）；摘要：串匹配是計(jì)算機(jī)研究領(lǐng)域的經(jīng)典問(wèn)題之一，在網(wǎng)絡(luò)安全、計(jì)算生物學(xué)、信息檢索等領(lǐng)域發(fā)揮著關(guān)鍵的作用。其中，基于位并行的串匹配算法所需存儲(chǔ)空間小、匹配速度快，但由于受到機(jī)器字的限制，只適合小規(guī)模的串
2、匹配。基于SSE系列指令集對(duì)經(jīng)典的位并行算法Shift-And、BNDM進(jìn)行了優(yōu)化，優(yōu)化算法利用SSE指令集提供的128位大位寬寄存器，將多個(gè)狀態(tài)向量打包到SSE寄存器上，并通過(guò)SSE的位操作指令狀態(tài)向量進(jìn)行更新。在隨機(jī)數(shù)據(jù)和真實(shí)數(shù)據(jù)上的測(cè)試結(jié)果顯示，優(yōu)化算法的匹配速度達(dá)到原算法的2倍以上。關(guān)鍵詞：串匹配算法；位并行；SSE指令集；Shift-And；BNDM中圖分類(lèi)號(hào)：TP302文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：OptimizingStringMatchingAlgorithmsbyUsingSSEInstructionsSHAOYan1,2,4,LIUYan-bing1,3,4,LIUP
3、ing1,4,GUOLi1,4(1.InstituteofComputingTechnologyChineseAcademyofSciences,Beijing100190,China;2.BeijingUniversityofPostsandTelecommunications,Beijing,100876,China;3.GraduateUniversityofChineseAcademyofSciences,Beijing100039,China;3.NationalEngineeringLaboratoryforInformationSecurityTechnologies
4、,Beijing100190,China)Abstract:Stringmatchingisaclassicresearchareaincomputerscienceandplaysanimportantroleinvariouskindoffields,suchasinformationsecurity,computationalbiology,informationretrial,etc.Bit-parallelstringmatchingalgorithmsrequirelessmemoryspaceandmatchpatternsatahighspeed.However,l
5、imitedbythemachineword,theyareonlysuitableforsmall-scalestringmatching.WeoptimizedtheclassicShift-AndalgorithmandBNDMalgorithmbyusingSSEinstructions.Wepackedseveralbit-vectorsintothe128-bitregistersprovidedbySSEinstructionset,andupdatedbit-vectorsbyusingSSEinstructions.Wetestedtheoptimizedalgo
6、rithmsonrandomdatasetaswellasrealdataset,andtheresultsindicatedthatthematchingspeedsoftheoptimizedalgorithmswereacceleratedtoatleasttwiceasmuchastheoriginalalgorithms’.Keywords:stringmatchingalgorithms;bitparallel;SSEinstructionset;Shift-And;BNDM1引言精確串匹配（后面簡(jiǎn)稱“串匹配”）問(wèn)題是計(jì)算機(jī)科學(xué)研究領(lǐng)域的一個(gè)經(jīng)典問(wèn)題。它指在文本T=t1
7、t2…tn中找出某個(gè)給定的模式串集合P={p1,p2,…,pr}的所有出現(xiàn)位置，其中T和pi(1≤i≤r)是在有限字符表∑上的字符序列。串匹配技術(shù)廣泛應(yīng)用于網(wǎng)絡(luò)信息安全領(lǐng)域，典型的應(yīng)用包括：入侵檢測(cè)/防御系統(tǒng)（IDS/IPS）、反病毒和反垃圾郵件檢測(cè)（AV/AS）、網(wǎng)絡(luò)帶寬管理和服務(wù)質(zhì)量（QoS）、統(tǒng)一威脅管理（UTM）等。近年來(lái)，隨著寬帶技術(shù)的發(fā)展和多媒體應(yīng)用的廣泛流行，互聯(lián)網(wǎng)技術(shù)得到極大的普及和發(fā)展。由于互聯(lián)網(wǎng)協(xié)議和計(jì)算機(jī)系統(tǒng)的漏洞，網(wǎng)絡(luò)安全形勢(shì)日趨嚴(yán)峻。傳統(tǒng)的網(wǎng)
