基于位并行技术的特殊字符串匹配

Special String Matching Based on Bit-parallelism Technique

提出了2种采用位并行技术的算法:ISA算法和IBNDM算法。使用机器字来记录各种参数,通过位运算更新各机器字的取值,模拟非确定自动机(NFA)的状态转换过程,反映各种特殊字符对NFA状态转换的影响,实现特殊字符串的快速匹配。在模式串长度不超过机器字长(通常为32或64)时,2种算法都比正则表达式具有更优越的性能。

Two efficient approaches were proposed based on bit-parallelism technique. They are ISA algorithm and IBNDM algorithm. Both algorithms are based on machine words encoded parameters. We can pack many values in a single word and update them all in a single operation, via bit-operation simulating slate transitions of a Nondeterministic Finite Automaton （NFA）, which will reflect the influences of constructing NFA made by various special characters. Under the circumstances that pattern is not longer than the number of bits in the machine word W （in current architectures W is 32 or 64）, both algorithms performed better than regular expression.