一种改进的Sunday模式匹配算法

An Improved Sunday Pattern Matching Algorithm

字符匹配效率是很多计算机应用系统的性能瓶颈,研究设计高效的匹配算法有助于提高相应系统的应用性能。在分析典型Sunday匹配算法的基础上,对其进行了较为有效的改进。改进算法在字符串匹配前先计算模式串的倒序特征值,也就是以此计算出模式串的最后s个字符在本模式串中倒序除自己以外的下一次出现的位置。每一次字符匹配都采用倒序匹配并利用这种匹配的结果,匹配结果结合倒序特征值可以直接决定特征串的下一次位移数。在进行完一次字符匹配后,采用增加一个遍历字符的Sunday算法来遍历模式串以计算下一次位移数,以此尽可能地排除无效匹配。实验结果表明改进算法的效率比Sunday算法有一定提高。

The efficiency of character matches are the performance bottlenecks of many computer applications, an algo- rithm which improves the efficiency of the characters match can contribute to enhancing the application performance of the system. Based on the analysis of Sunday pattern mathching algorithm, many improvements have been done. This improved algorithm calculation the mode string＇s Reverse Eigenvalue before string matching so that it can calculate the reverse position beside themselves for characters of the last s mode string. Every character matching is the descending match and got by the result of it, in which combination the result of the descending match and the Reverse Eigenvalue can directly determine the next displacement number of the mode string. After once character matching, the mode string is traversed to calculate the next displacement number by Sunday algorithm（ it uses one character）, which can exclude many invalid match by simply increasing the number of traversal characters. Experimental results show that the efficiency improved algorithms to Sunday algorithm has definitely improved.