主权项 |
一种按字长匹配的多模式串匹配方法,包括预编译过程和搜索过程,在字长为32位的计算机上进行如下操作:所述预编译过程为构造3个表:一个跳转表即SHIFT表,一个哈希表即HASH表,一个前缀表即PREFIX表;设B为字符块的长度,m为最短模式串的长度,X为当前需要计算哈希值的字符块;字符块哈希值的计算公式为:hash(X)=(X[0]*256<sup>B‑1</sup>)+(X[1]*256<sup>B‑2</sup>)+...+(X[B‑1]*256<sup>0</sup>);首先建立SHIFT表:先建立一个空表,表项值都初始化为最大跳转距离m‑B+1,在模式集中取每个模式串前m个字符,从后往前每次取相邻B个字符组成字符块,按上面给出的字符块哈希值的计算公式计算该字符块的哈希值,按字符块跳转值的计算公式<img file="FDA0000459155380000011.GIF" wi="1154" he="167" />修改表中索引值为该字符块哈希值的表项值,即形成SHIFT表;然后建立HASH表:先建立一个空表,表项值都初始化为空,在模式集中取每个模式串前m个字符的后B个字符组成字符块,按字符块哈希值的计算公式计算该字符块的哈希值,把哈希值相等的模式串用链表链接起来,存储在表中对应索引值为该哈希值的表项中,即形成HASH表;再建立PREFIX表:先建立一个空表,表项值初始化为空,取模式集中每个模式串前B个字符,把哈希值相等的模式串用链表链接起来,存储在表中对应索引值为该哈希值的表项中,即形成PREFIX表;其特征在于:将所述需要计算哈希值的字符块的长度B取2,在搜索过程中,每次按字长读取文本,即每次从文本中装载一个整型值,字符块的哈希值通过对该整型值的移位得到;具体操作如下:设当前读取机器字的内容是对应文本中的字符“abcd”,其中“abcd”四个字符均泛指任意字符,则该机器字对应三个字符块:前面字符块“ab”、中间字符块“bc”和后面字符块“cd”,机器字对应整型值为变量var,整个搜索过程分为四个阶段,用计算机语言描述如下:第一阶段:由计算前面字符块哈希值的公式hash("ab")=(var<<16)>>16得到前面字符块的哈希值V1,查SHIFT表得到表中索引值为前面字符块的哈希值V1的表项值:switch(SHIFT[V1]){case0:查找HASH表中索引值为前面字符块的哈希值V1的表项值,即为符合的模式串链表,对链表中每一个模式串,首先查找PREFIX表中索引值为V1的表项值,验证前缀是否匹配,最后再进行模式串其余部分的验证,之后进入第二阶段;case1:直接进入第二阶段;case2,3,4:直接进入第三阶段;default:若文本结束,则整个搜索过程结束;若文本没有结束,进入下一个机器字长的读取,重新进入第一阶段;};第二阶段:由计算中间字符块哈希值的公式hash("bc")=(var<<8)>>16得到中间字符块的哈希值V2,查SHIFT表:switch(SHIFT[V2]){case0:查找HASH表中索引值为中间字符块的哈希值V2的表项值,即为符合的模式串链表,对链表中每一个模式串,首先查找PREFIX表中索引值为V2的表项值,验证前缀是否匹配,最后再进行模式串其余部分的验证,之后进入第三阶段;case1,2:直接进入第三阶段;default:若文本结束,则整个搜索过程结束;若文本没有结束,进入下一个机器字长的读取,重新进入第一阶段;};第三阶段:由计算后面字符块哈希值的公式hash("cd")=var>>16得到后面字符块的哈希值V3,查SHIFT表:switch(SHIFT[V3]){case0:查找HASH表中索引值为后面字符块的哈希值V3的表项值,即为符合的模式串链表,对链表中每一个模式串,首先查找PREFIX表中索引值为V3的表项值,验证前缀是否匹配,最后再进行模式串其余部分的验证,之后进入第四阶段;case1:直接进入第一阶段;default:若文本结束,则整个搜索过程结束;若文本没有结束,进入下一个机器字长的读取,重新进入第一阶段;};第四阶段:取下一个字长中与该字长中相邻的字符,由计算哈希值的公式计算得到相邻字长字符块的哈希值V4,查SHIFT表:switch(SHIFT[V4]){case0:查找HASH表中索引值为字长字符块的哈希值V4的表项值,即为符合的模式串链表,对链表中每一个模式串,首先查找PREFIX表中索引值为V4的表项值,验证前缀是否匹配,最后再进行模式串其余部分的验证,之后进入第四阶段;default:若文本结束,则整个搜索过程结束;若文本没有结束,进入下一个机器字长的读取,重新进入第一阶段;}。 |