BF模式匹配算法的改进

Improved of BF pattern matching algorithm

摘要:

文章分析经典的BF算法及其改进方法,根据字符串匹配的特点对BF算法提出了新的改进算法I_BF算法。I_BF算法根据模式串的首字符与匹配窗口之间的距离来确定右移距离,从而进行快速地匹配,匹配方式是从左往右进行。为了测试I_BF算法的性能,在相同条件下,从匹配字符个数、匹配次数、所花时间三方面对I_BF算法进行实验。结果表明,由于I_BF算法能够很大程序地跳过坏字符,减少匹配次数和字符比较个数,节约匹配时间,从而有效地提高匹配速度。

Abstract:

In this paper, the classical BF algorithm and its improved method are analyzed. According to the characteristics of string matching, a new improved algorithm I_BF algorithm for BF algorithm is proposed. The I_BF algorithm determines the right distance according to the first character of the pattern string and the distance between the matching windows, so it fasts matching. The matching way of I_BF algorithm is from left to right. In order to test the performance of the I_BF algorithm, the I_BF algorithm is tested under the same conditions from three aspects: the number of matches, the number of matches and the time spent. The experimental results show the I_BF algorithm is more quickly and more efficient because it reduces greatly the number of matching and character comparison for maximizing to skip the bad characters.