[發(fā)明專利]基于散列的串匹配方法及其選擇模式串子窗口的方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201110162453.0
• 申請(qǐng)日: 2011-06-16
• 公開(kāi)（公告）號(hào): CN102243656A
• 公開(kāi)（公告）日: 2011-11-16
• 發(fā)明（設(shè)計(jì)）人: 邵妍;劉燕兵;王勇;劉慶云;郭莉;譚建龍;陳訓(xùn)遜;汪立東
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院計(jì)算技術(shù)研究所;國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)與信息安全管理中心
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京泛華偉業(yè)知識(shí)產(chǎn)權(quán)代理有限公司 11280
• 代理人: 王勇

技術(shù)領(lǐng)域

本發(fā)明涉及信息檢索領(lǐng)域。本發(fā)明尤其涉及串匹配方法。

背景技術(shù)

精確串匹配(后面簡(jiǎn)稱“串匹配”)問(wèn)題是計(jì)算機(jī)科學(xué)研究領(lǐng)域的一個(gè)經(jīng)典問(wèn)題。它指在文本T＝t₁t₂…t_n中找出某個(gè)給定的模式串集合P＝{p₁，p₂，…p_r}的所有出現(xiàn)位置，其中T和p_i(1≤i≤r)是在有限字符表∑上的字符序列。串匹配技術(shù)一直都是計(jì)算機(jī)科學(xué)的研究熱點(diǎn)之一，它在網(wǎng)絡(luò)入侵檢測(cè)、計(jì)算機(jī)病毒特征碼匹配、網(wǎng)絡(luò)信息內(nèi)容安全、信息檢索等多個(gè)領(lǐng)域中有著廣泛的應(yīng)用。

串匹配方法的分類有多種，按照其關(guān)鍵技術(shù)來(lái)分，可以分為以下三類：基于自動(dòng)機(jī)的匹配方法、基于散列的匹配方法和基于位并行的匹配方法。其中，基于散列的串匹配方法具有存儲(chǔ)空間小，匹配速度快的優(yōu)點(diǎn)，是實(shí)際系統(tǒng)中應(yīng)用最廣泛的方法之一，其中的典型代表包括Karp和Rabin在參考文獻(xiàn)1(Efficient?randomized?pattern-matching?algorithms.IBM?Journal?of?Research?and?Development?31(1987).1987，3：249-260.)中提出的方法(通常稱為Karp-Rabin方法)，以及Wu和Manber在參考文獻(xiàn)2(S.Wu，U.Manber.A?fast?algorithm?for?multi-pattern?searching.Technical?Report?Department?of?Computer?Science?Chung-Cheng?University.1994，5.)中提出的方法(通常稱為Wu-Manber方法)。

基于散列的串匹配方法的基本思想是：在預(yù)處理階段計(jì)算模式串的散列值，并以散列表的形式存儲(chǔ)起來(lái)；在匹配過(guò)程中，并不直接比較模式串及文本子串，而比較二者對(duì)應(yīng)的散列值，從而將匹配過(guò)程轉(zhuǎn)化為查表的過(guò)程。基于散列的串匹配方法的基本流程如圖1所示。在方法的預(yù)處理階段，首先，計(jì)算模式串集合中最短的模式串長(zhǎng)度，記為m。此后，截取各個(gè)模式串長(zhǎng)度為m的子串。上述過(guò)程實(shí)際上就是選擇模式串子窗口的過(guò)程。圖1所示的模式串子窗口選擇方法是直接截取模式串長(zhǎng)度為m的前綴。最后，通過(guò)散列函數(shù)，計(jì)算所截取的模式串子串的散列值，建立散列表。在匹配階段，首先計(jì)算文本子串的散列值，然后查找散列表，如果存在散列值相同的模式串，再進(jìn)一步比對(duì)文本和模式串本身。

現(xiàn)有的基于散列的串匹配方法只是簡(jiǎn)單地將模式串的子窗口選擇為模式串的前綴或后綴。這樣，如果在模式串間存在大量的前綴、后綴或子串的情況下，就會(huì)出現(xiàn)不同的模式串截取出相同子串的情況，進(jìn)而造成大量的模式串散列到散列表的同一位置，使散列表中某些鏈表過(guò)長(zhǎng)，極大地影響了散列表的均勻性。使得串匹配方法在校驗(yàn)階段的時(shí)間代價(jià)會(huì)大幅提高，顯著影響方法的整體性能。

發(fā)明內(nèi)容

因此，本發(fā)明的目的在于克服上述現(xiàn)有技術(shù)的缺陷，通過(guò)合理地選擇模式串子窗口來(lái)提高基于散列的串匹配方法的性能。

一方面，在本發(fā)明的一個(gè)實(shí)施例中提供了一種用于基于散列的串匹配中的選擇模式串子窗口的方法，所述方法包括以下步驟：

步驟1)求得模式串集合中最短模式串長(zhǎng)度m；

步驟2)對(duì)于模式串集合中的每個(gè)模式串，計(jì)算其所有長(zhǎng)度為m的子串的散列值，組成散列值集合；

步驟3)確定所述模式串集合與所述散列值集合中的元素的一一對(duì)應(yīng)關(guān)系，所述對(duì)應(yīng)關(guān)系應(yīng)滿足模式串所對(duì)應(yīng)的散列值是根據(jù)該模式串的一個(gè)長(zhǎng)度為m的子串計(jì)算出散列值，同時(shí)將這個(gè)子串設(shè)置為該模式串的子窗口。

根據(jù)本發(fā)明實(shí)施例的選擇模式串子窗口的方法，所述步驟3)包括：統(tǒng)計(jì)各模式串長(zhǎng)度為m的子串的散列值的出現(xiàn)次數(shù)；對(duì)于每個(gè)模式串，選擇出現(xiàn)次數(shù)最少的其子串的散列值與該模式串相對(duì)應(yīng)并將該子串設(shè)置為該模式串的子窗口。

根據(jù)本發(fā)明實(shí)施例的選擇模式串子窗口的方法，所述步驟3)包括：用數(shù)組Count[h_i]來(lái)記錄模式串集合中各模式串長(zhǎng)度為m的子串的散列值h_i的出現(xiàn)次數(shù)；對(duì)于每個(gè)模式串，逐個(gè)掃描其長(zhǎng)度為m的子串p_i，子串p_i的散列值表示為h_i，選取Count[h_i]最小的子串p_i來(lái)作為該模式串的子窗口。