作者：gfree.wind@gmail.com博客：blog.focus-linux.net linuxfocus.blog.chinaunix.net
今天继续炒冷饭，白话分析一下BM算法——其实说分析是高抬了自己，我只是想通过学习算法的过程中，尽量的去体会如何从这些算法中获得更多思想性的东西，即除了算法本身，可以了解算法的设计者是通过何种手段，是如何去获得更好的性能。
BM的细节不说了，主要说一下它的设计思路：
1. BM是从右向左比较：（话说这种思路我以前也想过呵）从右比较有什么好处呢？相对于从左开始比较，从右比较有更大的可能做到更少的比较，更大的滑动。比如一个极端的例子，最右端的字母不匹配，且string中的字母根本不在pattern中存在。那么pattern可以直接向右滑动strlen(pattern)的个数。如果是从左比较呢，即使最左端的字母同样不在pattern中存在，而patter也只能像右滑动1位。但是有的朋友可能会说，有可能从右端开始的匹配字母个数要比从左端开始匹配的字母个数多怎么办？按照概率将，这个可能性也得占一半。这时BM会有其它方法去处理这些情况。请看下面的BM好后缀策略的设计思路；
2. BM的好后缀策略的思路：这个好后缀策略，跟KMP的思想很相近。都是通过已经匹配了的字符串获得除了当前位置不匹配这一信息外更多的信息——即可以向右滑动的位数。
请看下图：
这是当已匹配的字符串在pattern还有相同的重复字符串的情况。
这是已匹配的字符串在pattern中只存在后缀的重复字符串的情况。
还有一种情况，即连x不存在u中任何重复的后缀，那么可以直接向右滑动strelen(pattern)的位数了。
3. BM的坏字符策略：这个策略充分的利用了从右面匹配，可以滑动更远位数的特性。
这种情况为，不匹配的字符在前面的pattern中存在，那么可以将pattern直接向右滑动至该位置。
这种情况为不匹配的字符在前面的pattern中不存在，那么可以将pattern直接向右滑动至不匹配字符的右边1位。
当好后缀和坏字符两种策略各得到不同的滑动位数时，BM取两者之中最大者。
上面三种策略为BM高效的原因，其中好后缀的策略与KMP类似。那么如果我们将坏字符的策略引入到KMP，是否也可以生效呢？
abcdefgbcabc......
abcdefabcabc
如上面的匹配，当第7位d和a不匹配时，g作为坏字符，对于KMP算法来说，也只能移动7位，相对于原来的KMP算法，不过多移动了一位，效果有限。其原因就在于BM是从右开始匹配，而KMP是从左开始匹配，这一左一右的区别，就使BM可以滑动更多的位数。
参考：
2.
阅读(664) | 评论(0) | 转发(0) |
