賈博威+吳志剛+張樹(shù)壯

摘要：大規(guī)模高速URL匹配是許多網(wǎng)絡(luò)安全系統(tǒng)中的關(guān)鍵技術(shù)，經(jīng)典串匹配算法在大規(guī)模URL情況下有許多限制。針對(duì)URL數(shù)據(jù)的特點(diǎn)在經(jīng)典多模式串匹配算法Wu-Manber基礎(chǔ)上提出XWM-Tree算法和XWM-Hash算法。算法應(yīng)用了模式串窗口選擇，兩階段哈希和關(guān)聯(lián)容器組織沖突鏈表等多種優(yōu)化手段，大幅度提高了算法的匹配性能。在大規(guī)模真實(shí)數(shù)據(jù)集上的測(cè)試結(jié)果表明本文提出的算法匹配速度可以提高一倍以上，尤其是當(dāng)最短模式串較長(zhǎng)的時(shí)候更有優(yōu)勢(shì)。

關(guān)鍵詞： 多模式串匹配； URL匹配； Wu-Manber算法

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：2095-2163（2017）05-0004-06

JIA Bowei， WU Zhigang， ZHANG Shuzhuang

Institute of Network Technology， Beijing University of Posts and Telecommunications， Beijing 100876， China）

Abstract：

Largescale highspeed URL matching is a key technology in many network security systems The classical pattern string matching algorithm has many limitations in largescale URLs In this paper， based on the WuManber algorithm， the XWMTree and XWMHash are proposed for URL matching The algorithm proposed in this paper applies a variety of optimization methods to speed up matching performance， such as optimal window selection， twophase hash and associative data structure The test on the real data set shows that the algorithms proposed in this paper has better matching performance than other algorithms， especially when the shortest pattern string is longer and the matching speed is about twice than other algorithms

Keywords：multistring matching； URL matching； WuManber algorithm

基金項(xiàng)目： 國(guó)家重點(diǎn)研發(fā)計(jì)劃資助項(xiàng)目（2016YFB0801200）。

收稿日期： 2017-08-28

0引言

多模式串匹配是計(jì)算機(jī)科學(xué)領(lǐng)域的一個(gè)經(jīng)典問(wèn)題，所謂多模式串匹配就是在給定一個(gè)模式串集合P={p1，p2，…，pr}的情況下，（其中pi=pi1pi2…pim）對(duì)于一個(gè)任意給定的字符串T=t1t2…tn，找出P中的字符串在T中所有的出現(xiàn)位置。這里稱P為模式串集合，pi為模式串，T為文本串，并且P和T都是定義在字母表Σ上的字符串。

多模式串匹配在網(wǎng)絡(luò)信息安全領(lǐng)域有著十分廣泛的應(yīng)用，包括網(wǎng)絡(luò)入侵檢測(cè)/防御系統(tǒng)（IDS/IPS）、防火墻系統(tǒng)、垃圾郵件檢測(cè)系統(tǒng)和反病毒系統(tǒng)等[1]。除此之外，串匹配技術(shù)在其它領(lǐng)域也有十分廣泛的應(yīng)用，如拼寫(xiě)檢查、語(yǔ)言翻譯、數(shù)據(jù)壓縮、搜索引擎等[2]。目前，超文本傳輸協(xié)議（Hypertext Transfer Protocol， HTTP）是互聯(lián)網(wǎng)領(lǐng)域應(yīng)用最廣泛的協(xié)議之一，除了傳統(tǒng)的桌面端應(yīng)用之外，很多移動(dòng)端應(yīng)用也使用HTTP協(xié)議作為承載協(xié)議。URL在HTTP協(xié)議中是最重要的一個(gè)域，標(biāo)識(shí)著被請(qǐng)求的資源的位置[3]。對(duì)有害的URL進(jìn)行過(guò)濾可以有效地對(duì)訪問(wèn)非法、有害等不良信息內(nèi)容進(jìn)行控制與管理。在海量的URL數(shù)據(jù)中檢測(cè)有害信息需要消耗大量的計(jì)算資源和存儲(chǔ)資源，在這種情況下如何保證串匹配算法正確高效地運(yùn)行，是當(dāng)前網(wǎng)絡(luò)信息安全領(lǐng)域面臨的一個(gè)重大難題。目前，在大規(guī)模URL匹配方面已有學(xué)者進(jìn)行研究[4-6]，但是還未達(dá)到實(shí)際系統(tǒng)中的應(yīng)用需求，亟待進(jìn)一步的探討研究。

本文在經(jīng)典多模式串匹配算法Wu-Manber[7]的基礎(chǔ)上結(jié)合URL數(shù)據(jù)的特點(diǎn)提出改進(jìn)措施，大幅度提高了算法的匹配性能，尤其在最短模式串長(zhǎng)度較長(zhǎng)的時(shí)候則更具優(yōu)勢(shì)。本文第二節(jié)論述了大規(guī)模URL模式串匹配的相關(guān)工作；第三節(jié)詳細(xì)介紹了本文提出的改進(jìn)措施和算法；第四節(jié)將本文的改進(jìn)算法和其它串匹配算法進(jìn)行實(shí)驗(yàn)評(píng)估；第五節(jié)是本文的結(jié)論。

1相關(guān)工作

URL匹配是模式串匹配的一種特殊應(yīng)用，目前主要有2種解決方法：一種是直接使用經(jīng)典的模式串匹配方法，另一種是在經(jīng)典模式串的基礎(chǔ)上結(jié)合URL的特點(diǎn)進(jìn)行改進(jìn)。

經(jīng)典模式串應(yīng)用于大規(guī)模URL匹配方面大致可以分為3類：基于自動(dòng)機(jī)的多模式串匹配算法、基于哈希表的多模式串匹配算法和基于位并行的多模式串匹配算法。在此，可做基礎(chǔ)闡釋如下。

1）基于自動(dòng)機(jī)的匹配算法的典型代表是AC算法[8]和SBOM算法[9]，該類算法匹配性能穩(wěn)定，不受模式串長(zhǎng)度和統(tǒng)計(jì)特征的影響，算法時(shí)間復(fù)雜度正比于待匹配文本串的長(zhǎng)度。應(yīng)用于大規(guī)模URL串匹配時(shí)，該類算法的主要問(wèn)題是存儲(chǔ)自動(dòng)機(jī)需要消耗巨大的內(nèi)存。針對(duì)以上問(wèn)題，文獻(xiàn)[10]在AC算法基礎(chǔ)上運(yùn)用統(tǒng)計(jì)策略提出基于數(shù)據(jù)訪問(wèn)特征的混合自動(dòng)機(jī)構(gòu)建算法，在真實(shí)的數(shù)據(jù)上測(cè)試表明這種改進(jìn)能夠壓縮掉5%的內(nèi)存。endprint

2）基于哈希的多模式串匹配算法是以哈希表作為基本數(shù)據(jù)結(jié)構(gòu)并使用字符塊技術(shù)來(lái)增大文本串和模式串不匹配的可能性，從而提高跳躍的機(jī)會(huì)。該類算法的典型代表是Wu-Manber算法[7]，該算法在十萬(wàn)規(guī)模的隨機(jī)字符串上能夠取得較好的匹配效果。但是由于URL數(shù)據(jù)是一種帶有語(yǔ)義特征的數(shù)據(jù)，其字符的分布并不具有隨機(jī)性，因此在大規(guī)模URL匹配中Wu-Manber算法由于嚴(yán)重的哈希沖突導(dǎo)致性能十分低劣。文獻(xiàn)[11]提出HashTrie算法，該算法利用遞歸散列技術(shù)將模式串集合信息存儲(chǔ)在位向量中，并用rank操作進(jìn)行快速校驗(yàn)，該算法比AC算法能夠節(jié)約高達(dá)996%的內(nèi)存開(kāi)銷，但是實(shí)際匹配性能卻只有AC算法的一半左右，并不適合高速匹配的應(yīng)用環(huán)境。

3）基于位并行的算法是用位向量來(lái)模擬自動(dòng)機(jī)的匹配過(guò)程，將自動(dòng)機(jī)的狀態(tài)跳轉(zhuǎn)表示為位向量的運(yùn)算，利用機(jī)器字來(lái)并行執(zhí)行。這類算法的代表是shift-and和shift-or算法[5]，但是該類算法受限于機(jī)器字長(zhǎng)只在小規(guī)模模式串的時(shí)候取得較好的匹配效果，不適用于大規(guī)模URL模式串匹配。文獻(xiàn)[12]利用q-gram技術(shù)對(duì)shift-or和BNDM算法[13]進(jìn)行拓展，基本思想是：將多個(gè)模式串利用q-gram技術(shù)規(guī)約成一個(gè)簡(jiǎn)單的模式串，然后使用快速的單模式串匹配技術(shù)快速過(guò)濾掉不可能匹配的文本，但是這種技術(shù)只能在1～10萬(wàn)規(guī)模的模式串上取得較好的效果，不適合大規(guī)模模式串匹配。

目前，在大規(guī)模URL匹配方面已有學(xué)者展開(kāi)廣泛研究。文獻(xiàn)[4]提出一種基于過(guò)濾的SOGOPT算法，該算法基于經(jīng)典的SOG算法結(jié)合模式串窗口選擇和分組規(guī)約兩種優(yōu)化技術(shù)，大幅度提高了算法的匹配性能。但是該算法受限于系統(tǒng)的機(jī)器字長(zhǎng)和最短模式串的長(zhǎng)度，當(dāng)機(jī)器字長(zhǎng)較短或者模式集的最短模式串長(zhǎng)度較長(zhǎng)時(shí)，能夠同時(shí)并行搜索的模式串個(gè)數(shù)減少，導(dǎo)致算法的匹配性能降低。文獻(xiàn)[6]結(jié)合哈希技術(shù)和雙數(shù)組Trie數(shù)據(jù)結(jié)構(gòu)提出TFD算法，該算法是在哈希表中沖突的節(jié)點(diǎn)上建立雙數(shù)組Trie樹(shù)結(jié)構(gòu)來(lái)加快精確校驗(yàn)的過(guò)程。但是，由于算法中使用了Trie數(shù)據(jù)結(jié)構(gòu)，因此該算法的內(nèi)存消耗和雙數(shù)組AC自動(dòng)機(jī)具有相當(dāng)?shù)牧考?jí)，限制了該算法的應(yīng)用。文獻(xiàn)[5]以“/”和“”將URL分塊，在此基礎(chǔ)上設(shè)計(jì)基于URL過(guò)濾的算法能夠取得較高的匹配性能，但是這種方法只支持分塊URL前綴匹配，并不支持子串匹配，限制了其應(yīng)用范圍。

綜上所述，目前針對(duì)多模串匹配研究主要圍繞通用串匹配方面，針對(duì)大規(guī)模URL匹配方面近年來(lái)已有學(xué)者開(kāi)始關(guān)注，但還少見(jiàn)推出有效的算法。本文在Wu-Manber算法的基礎(chǔ)上，針對(duì)URL的特點(diǎn)，從降低哈希沖突和減少精確比對(duì)次數(shù)的角度出發(fā)，采用窗口選擇、兩階段哈希和關(guān)聯(lián)容器組織沖突鏈表等多種優(yōu)化技術(shù)，提高了算法的匹配性能。

[BT4]2本文算法設(shè)計(jì)研究

本節(jié)提出一種面向大規(guī)模URL模式串匹配的串匹配算法，該算法在經(jīng)典的串匹配算法Wu-Manber的基礎(chǔ)上，針對(duì)URL數(shù)據(jù)的特點(diǎn)進(jìn)行優(yōu)化，以適應(yīng)大規(guī)模URL模式串匹配的需求。本文主要通過(guò)以下3種優(yōu)化方法提高匹配性能：

1）將文獻(xiàn)[4]中的模式串窗口選擇技術(shù)應(yīng)用在算法中。模式串窗口選擇技術(shù)能夠?yàn)槊總€(gè)模式串選擇出一個(gè)獨(dú)特且具有代表性的窗口來(lái)唯一代表每個(gè)模式串，因此在用哈希函數(shù)進(jìn)行哈希的時(shí)候能夠顯著降低各個(gè)模式串被放入同一個(gè)桶中的概率。

2）采用兩階段哈希。算法中使用了2個(gè)壓縮的哈希表來(lái)存儲(chǔ)匹配過(guò)程中的跳轉(zhuǎn)值。使用2個(gè)壓縮的哈希表能夠在保證哈希均勻的情況下大幅度降低內(nèi)存的使用。

3）使用關(guān)聯(lián)容器組織沖突模式串，并取消Wu-Manber算法中的prefix表。關(guān)聯(lián)容器具有根據(jù)鍵值快速查找的能力，能夠顯著減少校驗(yàn)時(shí)的比對(duì)次數(shù)。

本文在21節(jié)中分析了Wu-Manber算法在大規(guī)模URL匹配中的缺點(diǎn)和不足。針對(duì)Wu-Manber算法的缺點(diǎn)，在22～24節(jié)分別介紹了本文使用的3種優(yōu)化技術(shù)。在25節(jié)給出了本文提出的算法的預(yù)處理和匹配過(guò)程。

21Wu-Manber算法分析

Wu-Manber算法是Sun Wu[7]在1994年提出的經(jīng)典多模式串匹配算法，該算法利用“壞字符”跳轉(zhuǎn)的思想。在預(yù)處理階段建立3張哈希表，分別為shift表、hash表和prefix表。在掃描文本串的時(shí)候，shift表根據(jù)讀入字符串決定向后跳轉(zhuǎn)的字符數(shù)。hash表用來(lái)存儲(chǔ)尾塊字符散列值相同的模式串。prefix表用于存儲(chǔ)尾塊字符散列值相同的模式串的首塊字符散列值。在匹配的過(guò)程中，如果當(dāng)前文本串的shift值為0，則說(shuō)明可能產(chǎn)生了匹配，需要進(jìn)一步驗(yàn)證；此時(shí)需要在prefix表中驗(yàn)證尾塊相同模式串的前綴是否也相同，如果相同則在尾塊相同的hash表中逐一驗(yàn)證來(lái)查找是否有匹配發(fā)生。

當(dāng)將Wu-Manber算法直接應(yīng)用于大規(guī)模URL匹配的時(shí)候，匹配性能低下，主要有2方面的原因，具體表述如下：

1）哈希沖突嚴(yán)重。一方面，Wu-Manber算法采用2～3個(gè)字節(jié)作為哈希時(shí)的字符塊，這在中小規(guī)模模式串匹配中沒(méi)有問(wèn)題，當(dāng)模式串規(guī)模增大時(shí)哈希沖突將會(huì)非常嚴(yán)重；另一方面，URL數(shù)據(jù)本身是一類帶有語(yǔ)義的數(shù)據(jù)，因?yàn)榇罅康腢RL都具有相同的前綴和/或后綴[5]， Wu-Manber算法直接使用模式串最左邊m個(gè)字符串作為匹配窗口，這將導(dǎo)致很多模式串都具有相同的匹配窗口，因此哈希沖突將非常嚴(yán)重。

2）精確校驗(yàn)耗時(shí)嚴(yán)重。Wu-Manber算法在匹配的過(guò)程，當(dāng)shift值為0的時(shí)候，就要進(jìn)入精確校驗(yàn)階段。由于沖突的模式串在hash表中是以單鏈表的形式存儲(chǔ)的，在校驗(yàn)的時(shí)候就要遍歷單鏈表來(lái)逐一檢查是否有匹配發(fā)生。而URL數(shù)據(jù)經(jīng)常具有相同的前綴，導(dǎo)致具有相同前綴的沖突鏈表很長(zhǎng)，所以當(dāng)遍歷沖突鏈表查找精確匹配的模式串的時(shí)候?qū)⑾拇罅康腃PU時(shí)間。

[BT5]22模式串窗口選擇

模式串窗口選擇技術(shù)是劉燕兵[4]等人在優(yōu)化SOG算法的時(shí)候提出的，這種優(yōu)化技術(shù)不僅能夠用在SOG算法的優(yōu)化中，同樣也能用在Wu-Manber算法中。在原始的Wu-Manber算法中，會(huì)選取最短模式串的長(zhǎng)度m做為匹配窗口值，然后截取所有模式串的最左邊m個(gè)字符作為每個(gè)模式串的窗口。但是由于URL數(shù)據(jù)是一類字符分布極不均勻的數(shù)據(jù)，URL數(shù)據(jù)中存在大量的相同的前綴或相同的后綴[5]，導(dǎo)致大量的模式串具有相同的匹配窗口。模式串窗口選擇技術(shù)能夠?yàn)槊總€(gè)模式串選擇出一個(gè)獨(dú)特且具有代表性的窗口來(lái)唯一代表每個(gè)模式串，從而減少哈希沖突。本文提出的模式串匹配算法是在此基礎(chǔ)上設(shè)計(jì)得到的。endprint

例如，對(duì)于模式串集合P={googlecom， googlecomhk， googlecomtw， googlecomjp， googlecomtr}，如果用最左邊10個(gè)字符作為所有模式串的窗口，則所有的模式串集合都將具有相同的匹配窗口googlecom，因此在哈希的時(shí)候模式串集合中的5個(gè)模式串都將會(huì)哈希到同一個(gè)桶中，而且這種沖突不是使用更好的哈希函數(shù)就能解決的。使用窗口選擇技術(shù)處理模式串集合之后，每個(gè)模式串的匹配窗口如表1所示，可以看出每個(gè)模式串都具有不同的匹配窗口，因此這將降低不同模式串哈希到同一個(gè)桶中的概率。

為了解決內(nèi)存占用的問(wèn)題，本文使用2個(gè)壓縮的哈希表來(lái)提高算法的匹配性能，同時(shí)使算法的內(nèi)存消耗維持在一個(gè)較低水平。這里同樣稱這2個(gè)哈希表為shift表和hash表，并設(shè)置shift表和hash表分別具有2m和2n個(gè)條目，同時(shí)使用哈希函數(shù)h1和h2進(jìn)行映射，其中h1將長(zhǎng)度為B的字符塊映射成長(zhǎng)度為m個(gè)二進(jìn)制位的值，h2將長(zhǎng)度為B的字符塊映射成長(zhǎng)度為n個(gè)二進(jìn)制位的值。這里，shift表用于在掃描文本串的時(shí)候，根據(jù)讀入字符串決定可以跳過(guò)的字符數(shù)；hash表中每個(gè)條目用來(lái)組織存儲(chǔ)尾塊字符散列值相同的模式串。事實(shí)上，如果當(dāng)前驗(yàn)證的字符塊在其它模式串中從未出現(xiàn)或不在其它模式串匹配窗口的右端出現(xiàn)時(shí)，當(dāng)前匹配的滑動(dòng)窗口可以向后移動(dòng)更大的距離，為此本文提出的算法在hash表中添加一個(gè)skip值，用于精確驗(yàn)證后向后跳轉(zhuǎn)。在匹配的過(guò)程中對(duì)當(dāng)前匹配窗口中后B個(gè)字符串先用h1進(jìn)行計(jì)算，如果shift表項(xiàng)不為0，則向后跳轉(zhuǎn)；如果shift表項(xiàng)為0，則表示可能有匹配；這時(shí)用h2對(duì)當(dāng)前匹配窗口中的后B個(gè)字符塊計(jì)算哈希值并查看hash表中相應(yīng)的表項(xiàng)，如果有沖突的模式串，則進(jìn)行精確驗(yàn)證，并在驗(yàn)證之后使用skip值讓當(dāng)前文本的匹配窗口向后跳轉(zhuǎn)，否則，根據(jù)hash表項(xiàng)中的skip值讓當(dāng)前匹配窗口向后跳轉(zhuǎn)。

24使用關(guān)聯(lián)容器組織沖突節(jié)點(diǎn)

在Wu-Manber算法中，驗(yàn)證prefix表之后，每當(dāng)有可能產(chǎn)生匹配都要在hash表相應(yīng)的沖突鏈表中逐個(gè)驗(yàn)證是否有完全一致的模式串。逐一驗(yàn)證過(guò)程是一個(gè)非常耗時(shí)的操作，為了減少驗(yàn)證的次數(shù)并充分利用在22節(jié)中選擇出的窗口，本文提出的算法在hash表中為沖突的節(jié)點(diǎn)使用關(guān)聯(lián)容器來(lái)組織沖突鏈表，并取消了Wu-Manber算法中的prefix表。

關(guān)聯(lián)容器是一類可以通過(guò)鍵值高效地存儲(chǔ)和讀取元素的數(shù)據(jù)結(jié)構(gòu)，其底層實(shí)現(xiàn)通常是某種形式的平衡二叉樹(shù)或者哈希表，本文分別使用這2種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了XWM-Tree算法和XWM-Hash算法（eXtend Wu-Manber algorithm），算法性能對(duì)比在第3部分。使用關(guān)聯(lián)容器的關(guān)鍵是如何為給定的模式串構(gòu)造出鍵值。Wu-Manber算法中prefix表是用于存儲(chǔ)尾塊字符散列值相同的模式串的首塊字符散列值，這里為取代prefix表的功能，本文使用每個(gè)模式串匹配窗口的長(zhǎng)度為l=m-B的前綴哈希值作為每個(gè)模式串的鍵值。因此這種沖突模式串的組織形式完全可以替代prefix表的功能，而又不會(huì)影響算法的正確性。由于這里只需要驗(yàn)證具有相同鍵值的模式串，而鍵值的查找可以通過(guò)關(guān)聯(lián)容器的特性快速查找，因此在進(jìn)行校驗(yàn)的時(shí)候可以大幅減少校驗(yàn)次數(shù)。25算法描述

本文提出的算法分為預(yù)處理和掃描兩個(gè)階段。預(yù)處理主要包括使用窗口選擇技術(shù)為每個(gè)模式串選擇出具有代表性匹配窗口，然后根據(jù)每個(gè)模式串匹配窗口的后綴字符塊生成shift表和hash表，并根據(jù)匹配窗口的前綴字符串計(jì)算出鍵值，將每個(gè)模式串插入到hash表中相應(yīng)的關(guān)聯(lián)容器中。圖1是預(yù)處理的示意圖，其中灰色部分表示利用模式串窗口選擇技術(shù)為每個(gè)模式串選出的匹配窗口，淺灰色部分為用于計(jì)算shift表和hash表的模式串窗口的尾塊字符，深灰色部分是用于計(jì)算鍵值的模式串窗口的前綴串，hash表中的map字段存放指向關(guān)聯(lián)容器的指針，通過(guò)該指針和計(jì)算出的鍵值可以將模式串分別插入到hash表中相應(yīng)的條目中。

當(dāng)預(yù)處理結(jié)束后就可以進(jìn)入掃描匹配階段，算法1是掃描匹配的偽代碼描述。匹配的過(guò)程中需要維持一個(gè)大小為m的匹配窗口，其中3～12行是用當(dāng)前文本匹配窗口的后綴字符串計(jì)算shift值，如果shift值不為0則讓當(dāng)前文本向后跳轉(zhuǎn)；13～18行是處理shift值為0的情況，這時(shí)用當(dāng)前文本的匹配窗口的后綴字符串計(jì)算哈希值來(lái)索引hash表中相應(yīng)表項(xiàng)，如果關(guān)聯(lián)容器不為空則計(jì)算匹配窗口的前綴哈希值作為鍵值，通過(guò)該鍵值在關(guān)聯(lián)容器中查找并進(jìn)行比對(duì)。第19行是在進(jìn)行精確校驗(yàn)之后向后跳轉(zhuǎn)的過(guò)程。

3實(shí)驗(yàn)評(píng)估

本文從匹配速度和內(nèi)存消耗兩個(gè)方面分別將使用平衡二叉樹(shù)和哈希表組織沖突的XWM-Tree和XWM-Hash算法與SOGOPT算法（使用64位機(jī)器字長(zhǎng)）、TFD算法、雙數(shù)組AC算法（da_ac）進(jìn)行比較。此外，本文還討論了最短模式串長(zhǎng)度對(duì)算法的影響。在XWM-Tree和XWM-Hash算法中，α=075， m=28，n=24。

31實(shí)驗(yàn)數(shù)據(jù)和實(shí)驗(yàn)環(huán)境

本文使用的數(shù)據(jù)是從骨干路由器上采集去重后的8 000萬(wàn)條URL數(shù)據(jù)（約15 GB），并從這些URL數(shù)據(jù)中提取出1 000多萬(wàn)條模式串，最短模式串長(zhǎng)度為8，最長(zhǎng)模式串長(zhǎng)度為128。

實(shí)驗(yàn)的軟硬件環(huán)境如下：CPU為Intel Xeon E5-2650 v3 @23 GHz；內(nèi)存為32 GB；操作系統(tǒng)為Red Hat Enterprise Linux Server release 70 （Maipo），內(nèi)核版本為3100-123el7x86_64。所有代碼均使用C++語(yǔ)言編寫(xiě)，使用g++ 482編譯，在編譯的過(guò)程中開(kāi)啟-O3優(yōu)化。所有的程序都采用單線程運(yùn)行。

32實(shí)驗(yàn)結(jié)果及分析

從圖2～圖5可以看出無(wú)論是使用平衡二叉樹(shù)組織沖突模式串的XWM-Tree算法，還是使用哈希表組織沖突的XWM-Hash算法都比其它算法具有較高的匹配性能。當(dāng)最短模式串長(zhǎng)度為8時(shí)，XWM-Tree算法、XWM-Hash算法和SOGOPT算法在1 000萬(wàn)模式串的情況下具有相當(dāng)?shù)钠ヅ渌俣龋叶急入p數(shù)組AC算法和TFD算法具有更高的匹配速度。當(dāng)最短模式串的長(zhǎng)度較長(zhǎng)時(shí)本文提出的算法的優(yōu)勢(shì)逐漸顯現(xiàn)出來(lái)，無(wú)論是XWM-Tree算法，還是XWM-Hash算法在最短模式串長(zhǎng)度較長(zhǎng)的時(shí)候，匹配速度都是其它算法的2倍左右；而SOGOPT算法隨著最短模式串長(zhǎng)度的逐漸增長(zhǎng)，分組規(guī)約的組數(shù)逐漸減少，校驗(yàn)時(shí)的比較次數(shù)增加，因此算法性能逐漸下降。雙數(shù)組AC算法和TFD算法由于采用雙數(shù)組Trie數(shù)據(jù)結(jié)構(gòu)，受最短模式串長(zhǎng)度和模式串?dāng)?shù)量的影響較小，匹配性能比較穩(wěn)定。使用哈希表組織沖突的XWM-Hash算法比使用平衡二叉樹(shù)組織沖突的XWM-Tree算法匹配速度略低。endprint

從圖6～9中可以看出，在內(nèi)存消耗方面，XWM-Tee算法和XWM-Hash算法由于采用的是2個(gè)壓縮的哈希表，因此能夠維持內(nèi)存消耗在一個(gè)較低的水平。當(dāng)模式串?dāng)?shù)量在100～700萬(wàn)的時(shí)候，本文提出的算法內(nèi)存消耗要比SOGOPT算法略高，但當(dāng)模式串?dāng)?shù)量達(dá)到1 000萬(wàn)時(shí)，XWM算法和SOGOPT算法具有相當(dāng)?shù)膬?nèi)存消耗，且都明顯低于TFD算法和雙數(shù)組AC算法。而XWM-Hash算法由于是采用哈希表組織的沖突模式串，內(nèi)存消耗要比XWM-Tree算法嚴(yán)重，即便如此當(dāng)達(dá)到1 000萬(wàn)模式串的時(shí)候XWM-Hash算法消耗也還不到2 GB內(nèi)存，這大大低于雙數(shù)組AC算法和TFD算法近8 GB的內(nèi)存消耗。[JP]

4結(jié)束語(yǔ)

在網(wǎng)絡(luò)日益發(fā)展的今天，大規(guī)模URL匹配過(guò)濾是目前網(wǎng)絡(luò)安全系統(tǒng)中亟待解決的問(wèn)題，本文在經(jīng)典的多模式串匹配算法Wu-Manber的基礎(chǔ)上，針對(duì)URL數(shù)據(jù)的特點(diǎn)，從降低哈希沖突和減少精確比對(duì)次數(shù)的角度出發(fā)，利用多種優(yōu)化技術(shù)提高了匹配性能，并且使得算法的內(nèi)存消耗維持在較低的水平，真實(shí)數(shù)據(jù)上的測(cè)試表明，本文提出的算法與其它算法相比在大規(guī)模URL匹配方面能夠提高一倍以上的性能，適用于運(yùn)營(yíng)商級(jí)別的應(yīng)用環(huán)境中。

參考文獻(xiàn)：

張樹(shù)壯， 羅浩， 方濱興 大規(guī)模復(fù)雜規(guī)則匹配技術(shù)研究[J] 高技術(shù)通訊， 2010，20（12）： 1217-1223

[2] 郭莉， 譚建龍，劉萍，等 面向信息內(nèi)容安全的串匹配技術(shù)[C]// 2008年互聯(lián)網(wǎng)新媒體新技術(shù)研討會(huì)論文集 深圳： 國(guó)務(wù)院新聞辦公室網(wǎng)絡(luò)局，2008： 30-60

[3] 趙思遠(yuǎn) HTTP 協(xié)議頭及錯(cuò)誤碼詳解[J] 計(jì)算機(jī)與網(wǎng)絡(luò)， 2016， 42（11）： 40-43

[4] 劉燕兵， 邵妍， 王勇， 等 一種面向大規(guī)模URL過(guò)濾的多模式串匹配算法[J] 計(jì)算機(jī)學(xué)報(bào)， 2014，37（5）：1159-1169

[5] 徐東亮 高性能在線模式匹配算法研究[D] 哈爾濱：哈爾濱工業(yè)大學(xué)， 2015

[6] YUAN Zhenlong， YANG Baohua， REN Xiaoqi， et al TFD： A multipattern matching algorithm for largescale URL filtering[C]//Computing， Networking and Communications （ICNC）， 2013 International Conference onBeijing，China： IEEE， 2013： 359-363

[7] [JP4]Wu S， Manber U A fast algorithm for multipattern searching[R]Tucson， AZ： Department of Computer Science， University of Arizona， 1994 [JP]

[8] [JP4]AHO A V， CORASICK M J Efficient string matching： An aid to bibliographic search[J] Communications of the ACM， 1975， 18（6）： 333-340[JP]

[9] ALLAUZEN C， CROCHEMORE M， RAFFINOT M Factor oracle： A new structure for pattern matching[C]//International Conference on Current Trends in Theory and Practice of Computer Science Springer Berlin Heidelberg， 1999： 295-310

[10]熊剛， 何慧敏， 于靜， 等 HybridFA： 一種基于統(tǒng)計(jì)的 AC 自動(dòng)機(jī)空間優(yōu)化技術(shù)[J] 通信學(xué)報(bào)， 2015， 36（7）： 31-39

[11]張萍， 劉燕兵， 于靜， 等 HashTrie： 一種空間高效的多模式串匹配算法[J] 通信學(xué)報(bào)， 2015， 36（10）： 172-180

[12]SALMELA L， TARHIO J， KYTJOKI J Multipattern string matching with qgrams[J] Journal of Experimental Algorithmics （JEA）， 2006， 11（11）：1-19

[13]NAVARRO G， RAFFINOT M A bitparallel approach to suffix automata： Fast extended string matching[C]//Combinatorial Pattern Matching Berlin/Heidelberg：Springer ， 1998： 14-33

3結(jié)束語(yǔ)

本文首次將廣義拓?fù)潇貞?yīng)用于人類參考基因組片段復(fù)制的研究中。實(shí)驗(yàn)結(jié)果表明，片段復(fù)制區(qū)域序列的廣義拓?fù)潇氐陀趨⒖蓟蚪M中隨機(jī)選取區(qū)域的廣義拓?fù)潇?，這說(shuō)明廣義拓?fù)潇乜梢杂行У貙⑵螐?fù)制區(qū)域與其他DNA序列區(qū)域區(qū)分開(kāi)來(lái)。廣義拓?fù)潇乜蔀閰⒖蓟蚪M的片段復(fù)制區(qū)域識(shí)別及個(gè)人基因組拷貝數(shù)復(fù)制的精準(zhǔn)識(shí)別奠定基礎(chǔ)并提供新的解決思路。

廣義拓?fù)潇赜?個(gè)顯著的優(yōu)勢(shì)：

1）理論上，可以證明廣義拓?fù)潇厥峭負(fù)潇氐耐茝V，是拓?fù)潇氐耐暾磉_(dá)形式。廣義拓?fù)潇乜梢匀胬^承拓?fù)潇卦贒NA序列分析上的各項(xiàng)優(yōu)勢(shì)。

2）廣義拓?fù)潇爻浞挚紤]了子串本身的序列復(fù)雜度，可以更加全面地分析DNA序列的復(fù)雜性。通過(guò)廣義拓?fù)潇卦谌祟悈⒖蓟蚪M片段復(fù)制區(qū)域及隨機(jī)選取區(qū)域上的序列對(duì)照研究，實(shí)驗(yàn)結(jié)果表明：廣義拓?fù)潇乜梢詫⑵螐?fù)制區(qū)域與隨機(jī)選取區(qū)域進(jìn)行較好的區(qū)分，取得了顯著的實(shí)驗(yàn)效果。endprint

理論上，基因組拼接方法可以實(shí)現(xiàn)個(gè)人基因組變異的精準(zhǔn)識(shí)別。然而，拼接方法目前在拷貝數(shù)復(fù)制區(qū)域尚未取得突破性的進(jìn)展。雖然廣義拓?fù)潇卦趨⒖蓟蚪M片段復(fù)制的分類方面取得理想效果，但仍然期待更為成熟的測(cè)序技術(shù)以及更為先進(jìn)的基因組拼接算法來(lái)實(shí)現(xiàn)個(gè)人基因組在拷貝數(shù)復(fù)制區(qū)域的成功拼接[16-17]。屆時(shí)，隨著高通量測(cè)序技術(shù)的逐漸成熟以及拼接算法的不斷完善，利用廣義拓?fù)潇貙?duì)個(gè)人基因組拷貝數(shù)復(fù)制進(jìn)行精準(zhǔn)識(shí)別和預(yù)測(cè)將具有廣闊的應(yīng)用前景。

參考文獻(xiàn)：

A， EICHLER E E Primate segmental duplications： Crucibles of evolution， diversity and disease[J] Nature reviews Genetics， 2006， 7（7）： 552-564

[2] GIRIRAJAN S， CAMPBELL C D， EICHLER E E Human copy number variation and complex genetic disease[J] Annu Rev Genet， 2011， 45：203-226

[3] LORENTZ G G Metric entropy and approximation[J] Bulletin of the American Mathematical Society，1966，72： 903-937

[4] ADLER R L， KONHEIM A G， MCANDREW M H Topological Entropy[J] Transactions of the American Mathematical Society， 1965， 114（2）： 309-319

[5] YAKOV S Kolmogorov-Sinai entropy[J] Scholarpedia， 2009，4（3）：2034

[6] RENYI A On measures of entropy and information[C]// Procfourth Berkeley Sympon Mathstatist & Probunivof Calif Berkeley， Calif： California Press， 1961： 547-561

[7] [JP3]VINGA S， ALMEIDA J S R[KG-8]e[DD（-1]′[DD）]nyi continuous entropy of DNA sequences[J] Journal of theoretical biology， 2004， 231（3）： 377-388[JP]

[8] KIRILLOVA O V Entropy concepts and DNA investigations[J] Physics Letters A， 2000， 274（5/6）： 247-253

[9] FARACH M， NOORDEWIER M， SAVARI S， et al On the entropy of DNA： Algorithms and measurements based on memory and rapid convergence[J] Proceedings of the Sixth Annual Acm-Siam Symposium on Discrete AlgorithmsSan Francisco， California， USA：ACM， 1995： 48-57

[10]COLOSIMO A， DE LUCA A Special factors in biological strings[J] Journal of theoretical biology， 2000， 204（1）： 29-46

[11]TROYANSKAYA O G， ARBELL O， KOREN Y， et al Sequence complexity profiles of prokaryotic genomic sequences： A fast algorithm for calculating linguistic complexity[J] Bioinformatics， 2002， 18（5）： 679-688

[12]GABRIELIAN A， BOLSHOY A Sequence complexity and DNA curvature[J] Computers & chemistry， 1999， 23（3/4）： 263-274

[13]KOSLICKI D Topological entropy of DNA sequences[J] Bioinformatics， 2011， 27（8）： 1061-1067

[14]JIN S， TAN R， JIANG Q， et al A generalized topological entropy for analyzing the complexity of DNA sequences[J] PloS One， 2014， 9（2）： e88519

[15]JIN Shuilin， WANG Zhou， LIN Junyu， et al The complexity of promoter regions based on a vector topological entropy[J] Current Bioinformatics， 2016， 11：1-4

[16]MAGI A， TATTINI L， PIPPUCCI T， et al Read count approach for DNA copy number variants detection[J] Bioinformatics， 2012， 28（4）： 470-478

[17]ALKAN C， COE B P， EICHLER E E Genome structural variation discovery and genotyping[J] Nature reviews Genetics， 2011， 12（5）： 363-376endprint