基于BM方法的字符串匹配复化算法

Composite string matching algorithm based on boyer-moore method

在分析经典的BM算法及其相关的改进算法的基础上,提出了一种基于BM算法的改进复化算法CBM.在字符串匹配过程中,CBM算法采用了与BM算法类似的字符比较方式,从模式的右端开始比较字符,但是,CBM算法利用前几轮的匹配信息生成了不同的模式前移距离表格,表格中的前移距离往往大于BM算法的相应前移距离,这样就可以使匹配过程中的模式前移速度加快,从而提高字符串匹配的效率.对于字母表较小的字符串匹配(如二进制搜索和DNA序列测试),CBM算法有较好的实际效果.

Classical Boyer-Moore （BM） algorithms and its improvements were analyzed. By compositing the main method of the BM algorithm, a new algorithm--the composite BM algorithm （CBM） is proposed. In the process of string matching, the CBM algorithm uses the charter comparing manner from right to left similar BM. But, the CBM algorithm takes full advantage of the historical matching information, generate different pattern forward table, usually, the pattern forward distance is more than of BM algorithm. In this way, CBM accelerates the forward speed of the pattern during the matching, and hence the whole string matching process was speeded up effectively. In the case of small alphabet （such as binary searching and DNA sequence test）, the CBM algorithm has the practical effect of better.