打破思维断层之Boyer-Moore

 

BM算法

 

目的：本博客以BM算法为载体，意图在减少思维断层情况下了解算法思想。

 

目录：

 

• BM算法的创新之处在于“跳跃式”思维方式
• BM算法VS KMP算法
• BM过程展示
• BM案例分析
• 代码实现
• 进一步思考

第一步：BM算法的创新：“跳跃式”思维方式

无论是BF算法、KMP算法或者Shift-And/Or算法，他们都是基于前缀，从前向后来进行匹配。BM算法和它们不同，它是基于后缀，从后向前进行匹配。

然而BM算法（由Robert S. Boyer和J Strother Moore两位共同完成）的创新并不是在于后缀匹配，而是在于通过后缀匹配产生了“跳跃式”的思想。跳跃式思想是来源于字符串的随机性，也就是说这种思维方式其实是利用了字符串本身的特性。

第二步：BM算法  VS  KMP算法

不得不说，KMP算法确实比较漂亮，它的厉害之处在于目标串指针不再进行回溯，使得整个算法效率是线性的。但是考虑到实际运行效果，实在是令人遗憾。

KMP的运行效果，别说和BM相比，恐怕大部分情况下就连最初的BF算法都可能无法抗衡，原因在于KMP算法是在假设单词的构造可以是任意的，甚至可以是abababa这样的，但是现实是我们执行文本搜索中的单词却并没有这样的。这算是一个实验室中理想的算法。

http://people.cs.pitt.edu/~kirk/cs1501/animations/String.html 

可以看一下两者效率的对比很有说服力的。下面我用几张图片说明下

KMP算法：图片中包含模式串和目标串 

 

 

 

 
 上述图片并不是全部，只是为了展示过程。实际上本例中KMP就是这样“一步一步”的走到了最后，由于模式串methods的中没有既是前缀又是后缀的字符串，使得结果和普通的BF算法还慢

BM算法

 

 

 

       BM算法是跳跃着前进的。

第三步：BM过程展示

BM算法实施方法是从后向前进行匹配。我们先来见证一下这种方法的威力。

 

此处采用作者论文中的例子：

 

从模式串最后一个字符开始匹配，发现F和T不匹配，除此之外，F在模式串AT-THAT中根本就不存在，这个意味着匹配的可能性为0.我们可以直接跳过前7个字符。

 我们只是添加了一个判断，效率瞬间提高很多。这个和BF、KMP有什么不同呢？这两种算法，目标串的指针i总是以一步一步的前进，而BM则并没有采用这种方式，它可以一下子增加7（本例），这就是跳跃式思维的表现形式，这个更接近人的思维方式。（下面会有更深入层次的分析前缀匹配和后缀的匹配差异）

BM算法采用了两种启发性的规则：坏字符规则和好后缀规则，决定跳跃的距离。

 

1) 坏字符规则（Bad Character）

 

  在BM算法从后向前扫描的过程中，若已经有m个字符匹配成功，第m+1个字符X（从后向前）匹配失败，则按下面两种情况讨论：

 

   a)如果字符x在模式P中没有出现，直接全部跳过该区域。

 

   b)如果字符x在模式P中出现，则以该字符进行对齐。

       我们其实已经见识过a)这个规则，就是上面的例子。

 

2）好后缀规则（Good Suffix）

 

在BM算法从后向前扫描的过程中，若已经有m个字符匹配成功，第m+1个字符X（从后向前）匹配失败，则按下面两种情况讨论：

 

 a) 如果已经匹配的m个字符，在模式串其他位置也出现过记为m’，则将m’和这m个字符对齐。


     b) 如果a)中所说情况没有出现，此时需要检查模式串P，若P存在最长前缀s 同时也是P的后缀，则将s和P对应的后缀对齐。

 

 上述两个好后缀规则中取最小的一个移动。

 

其实，在好后缀规则中，如果第一条成立其实就不用检查第二条，因为第二条如果存在，移动距离肯定比第一条大。但是如果第一条不成立，意味着移动距离是模式串P的长度，此时需要检查第二条，如果第二条成立，则安全移动的距离便变小了。

 

第四步：BM案例分析

 

 

 

 

  第五步：代码实现

 

 

 

// 匹配算法
	public static int indexOf(char[] ocean, char[] needle) {
		if (needle.length == 0) {
			return 0;
		}
		int charTable[] = makeCharTable(needle);
		int offsetTable[] = makeOffsetTable(needle);
		for (int i = needle.length - 1, j; i < ocean.length;) {
			for (j = needle.length - 1; needle[j] == ocean[i]; --i, --j) {
				if (j == 0) {
					return i;
				}
			}
			// offsetTable根据已经匹配的好后缀的长度取数据 charTable根据坏字符取数据
			i += Math.max(offsetTable[needle.length - 1 - j],
					charTable[ocean[i]]);
		}
		return -1;
	}

	/**
	 * 坏字符规则表
	 */
	private static int[] makeCharTable(char[] needle) {
		final int ALPHABET_SIZE = 256;
		int[] table = new int[ALPHABET_SIZE];
		// 初始化赋值
		for (int i = 0; i < table.length; ++i) {
			table[i] = needle.length;
		}
		// 重新赋值
		for (int i = 0; i < needle.length - 1; ++i) {
			table[needle[i]] = needle.length - 1 - i;
		}
		return table;
	}

	/**
	 * 好后缀规则表 ，
	 * 根据好后缀长度取需要移动的位置 
	 * 由于规则b的值>=规则a的值（始终）
	 *  先根据规则b进行赋值
	 *  再根据好后缀规则a重新赋值
	 */
	private static int[] makeOffsetTable(char[] needle) {
		int[] table = new int[needle.length];
		int lastPrefixPosition = needle.length;
		// 根据好后缀规则b)初始化好后缀表
		for (int i = needle.length - 1; i >= 0; --i) {
			if (isPrefix(needle, i + 1)) {
				lastPrefixPosition = i + 1;
			}
			table[needle.length - 1 - i] = lastPrefixPosition - i
					+ needle.length - 1;
		}
		// 再根据好后缀规则a)重新赋值
		for (int i = 0; i < needle.length - 1; ++i) {
			int slen = suffixLength(needle, i);
			table[slen] = needle.length - 1 - i + slen;
		}
		return table;
	}

	/**
	 * 判断从p开始到结束是否既是后缀同时是前缀 abacactttabac 例如p=9（从左到右，字符a处）结果是true（abac == abac）
	 */
	private static boolean isPrefix(char[] needle, int p) {
		for (int i = p, j = 0; i < needle.length; ++i, ++j) {
			if (needle[i] != needle[j]) {
				return false;
			}
		}
		return true;
	}

	/**
	 * 获取从p到0位置 的最大的是后缀的字串大小 ababactttabac 例如当p=5（c处），结果是abac的大小4
	 */
	private static int suffixLength(char[] needle, int p) {
		int len = 0;
		for (int i = p, j = needle.length - 1; i >= 0 && needle[i] == needle[j]; --i, --j) {
			len += 1;
		}
		return len;
	}

 第六步：进一步思考

 

如果你对BF或者KMP有了解，可以看一下下面的分析，如果没有可以直接跳过，该分析是为了增加对前缀、后缀匹配以及跳跃性分析的了解。

 

也许你可能有疑问，难道前缀匹配就不能这样吗？假设从第一个字符W和A开始匹配，W在模式串中也不存在，但是此时却只能跳过1个。

 

当然，BM也可能出现很差的情况。假设已经7个中已经匹配6个，最后一个不同，假设这个时候模式串向后移动1位，那么目标串指针i相当于在比较了次之后，也只是前进了1步。

 

而在前缀匹配中我们也可以实施这样一个检查，当匹配失败的时候，检查模式串前面几个字符是否包含目标串当前匹配失败的字符，如果没有，我们也可以直接跳过这几个已经匹配的字符。

 

那么BM算法为什么不使用前缀匹配呢？我们可以这样理解，在后缀匹配中第1个字符，像上个例子F在模式串中不存在，意味着可以直接跳过前7个字符，当然如果使用前缀匹配，也可以出现这种情况，当匹配了6个字符后，第7个不同，而且第7个字符很生僻如X，前6个中没有X，这个时候我们可以跳过，但是前提是我们已经进行了6次比较，而后缀匹配只是进行了1次，这就是差异。而平时使用的文本搜索更是将后缀匹配效果进行了放大，即平常文本搜索很少会出现共有7个字符，有6个一样，第7个不一样，即使是存在这样的单词，但是你见过这种单词在同一个文本中扎堆出现吗？也许有，那就算你倒霉了。这其实是基于概率的，对文本进行了粗略的概率估计。

 

实际上BM算法并非是最快的算法，但是它实现了思维方式的改变，Sunday和Horspool对该算法进行了简化，效率更高。