适合中文的双向比较模式匹配算法

Two-way Comparative Pattern Matching Algorithm Suitable for Chinese

分析了几种常用的模式匹配算法,提出一种适合于中文的基于KMP的改进算法,即双向比较模式匹配算法.该算法以KMP算法为基础,引入特征数组以记录模式串尾字符在模式串中出现的位置信息,从而获得模式串在匹配过程中的最大移动距离和最少比较次数.实验结果表明,双向比较模式匹配算法可有效降低匹配次数.

Some pattern matching algorithms were analyzed and,an algorithm,suitable for Chinese,based on KMP was proposed,that is two-way pattern matching algorithm.Based on KMP,characteristic-array was introduced into to record the positional information of end character which appears in the pattern string and further to get the maximum moving distance of the pattern and the least times of comparing during the process of pattern string＇s matching.Experimental results show that two-way pattern matching algorithm can effectively reduce the times of matching.