[發明專利]一種按字長匹配的多模式串匹配方法

有效

• 申請號: 201210006598.6
• 申請日: 2012-01-10
• 公開（公告）號: CN102609450A
• 公開（公告）日: 2012-07-25
• 發明（設計）人: 顧乃杰;汪永進;郭利財;任開新
• 申請（專利權）人: 顧乃杰
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 安徽省合肥新安專利代理有限責任公司 34101
• 代理人: 汪祥虬

技術領域

本發明屬于計算機中字符串匹配技術領域，具體涉及按字長匹配的多模式串匹配方法。

背景技術

多模式串匹配方法現已被廣泛的用于信息檢索、網絡內容過濾、病毒檢測和生物計算學等方面。所謂多模式串匹配，就是從文本中搜索出模式串集合中所有模式串的所有出現的位置。經典的多模式匹配方法有基于前綴的匹配防范，基于后綴的匹配方法和基于子串的匹配方法。其中基于后綴的匹配方法，如1994年美國亞利桑那大學計算機學院報告《一種快速的多模式串匹配算法》中提出的Wu-Manber方法(報告編號為TR-94-17)，是目前實際中平均性能最好的一個方法，被應用于操作系統的搜索程序和入侵檢測系統中。該Wu-Manber方法采用哈希散列和跳躍式搜索的方式，具有很好的匹配效率，但Wu-Manber方法在模式集中最短模式串長度過小時，搜索時平均跳躍距離變小，需要頻繁的計算哈希值，驗證入口增多，匹配效率會嚴重下降。

發明內容

本發明提出一種按字長匹配的多模式串匹配方法，以克服現有技術的上述缺陷，使多模式串匹配達到比較高的效率。

本發明按字長匹配的多模式串匹配方法，包括預編譯過程和搜索過程，在字長為32位的計算機上進行如下操作：

所述預編譯過程和傳統的Wu-Manber方法相同，為構造3個表：一個跳轉表即SHIFT表，一個哈希表即HASH表，一個前綴表即PREFIX表；設B為字符塊的長度，m為最短模式串的長度，X為當前需要計算哈希值的字符塊；字符塊哈希值的計算公式為：

hash(X)＝(X[0]*256^B-1)+(X[1]*256^B-2)+...+(X[B-1]*256⁰)；

首先建立SHIFT表：先建立一個空表，表項值都初始化為最大跳轉距離m-B+1，在模式集中取每個模式串前m個字符，從后往前每次取相鄰B個字符組成字符塊，按上面給出的字符塊哈希值的計算公式計算該字符塊的哈希值，按字符塊跳轉值的計算公式修改表中索引值為該字符塊哈希值的表項值，即形成SHIFT表；

然后建立HASH表：先建立一個空表，表項值都初始化為空，在模式集中取每個模式串前m個字符的后B個字符組成字符塊，按字符塊哈希值的計算公式計算該字符塊的哈希值，把哈希值相等的模式串用鏈表鏈接起來，存儲在表中對應索引值為該哈希值的表項中，即形成HASH表；

再建立PREFIX表：先建立一個空表，表項值初始化為空，取模式集中每個模式串前B個字符，把哈希值相等的模式串用鏈表鏈接起來，存儲在表中對應索引值為該哈希值的表項中，即形成PREFIX表；

其特征在于：

將所述需要計算哈希值的字符塊的長度B取2，在搜索過程中，每次按字長讀取文本，即每次從文本中裝載一個整型值，字符塊的哈希值通過對該整型值的移位得到；具體操作如下：

設當前讀取機器字的內容是對應文本中的字符“abcd”，該機器字對應三個字符塊：前面字符塊“ab”、中間字符塊“bc”和后面字符塊“cd”，機器字對應整型值為變量var，整個搜索過程分為四個階段，用計算機語言描述如下：

第一階段：

由計算前面字符塊哈希值的公式hash(″ab″)＝(var<<16)>>16得到前面字符塊的哈希值V1，查SHIFT表得到表中索引值為前面字符塊的哈希值V1的表項值：

switch(SHIFT[V1])

{

case?0：查找HASH表中索引值為前面字符塊的哈希值V1的表項值，即為符合的模式串鏈表，對鏈表中每一個模式串，首先查找PREFIX表中索引值為V1的表項值，驗證前綴是否匹配，最后再進行模式串其余部分的驗證，之后進入第二階段；

case?1：直接進入第二階段；

case?2，3，4：直接進入第三階段；

default：若文本結束，則整個搜索過程結束；若文本沒有結束，進入下一個機器字長的讀取，重新進入第一階段；

}；

第二階段：

由計算中間字符塊哈希值的公式hash(″bc″)＝(var<<8)>>16得到中間字符塊的哈希值V2，查SHIFT表：

switch(SHIFT[V2])

{