算法07:Golang字符串搜索BM算法

算法07:Golang字符串搜索BM算法

1. 什么是BM算法

1977 年,德克萨斯大学的 Robert S. Boyer 教授和 J Strother Moore 教授发明了一种新的字符串匹配算法:Boyer-Moore 算法,简称 BM 算法。 该算法 从模式串的尾部开始匹配,且拥有在最坏情况下 O(N) 的时间复杂度。有数据表明,在实践中,比 KMP 算法的实际效能高,可以快大概 3-5 倍。

BM算法的一个特点是当不匹配的时候一次性可以跳过不止一个字符。 即它不需要对被搜索的字符串中的字符进行逐一比较,而会跳过其中某些部分。通常搜索关键字越长算法速度越快。 它的效率来自于这样的事实:对于每一次失败的匹配尝试,算法都能够使用这些信息来排除尽可能多的无法匹配的位置。

2. 坏字符规则(bad-character shift)

在 BM 算法中,模式串中的字符跟主串进行匹配的时候是由后向前进行匹配,对于上图来说最先比对的是模式串中的 d 发现和主串中的 c 不相等,那么此时主串中的 c 就叫做坏字符

2.1 坏字符

坏字符:模式串中第一个跟主串不相等的字符(模式串倒序匹配),叫做坏字符(主串字符) 此时坏字符就是主串中的 c

此时我们将坏字符对应模式串的字符的位置,记作 i,那么此时 i = 2

虽然我们将模式串倒序匹配,但是模式串本身的位置不做更改即 a b d 分别对应下标 0 1 2

2.2 模式串移动

那么此时模式串该向后移动几位呢,做法是这样的,从模式串中查找坏字符的位置(从后向前找到第一个匹配的就停下来)记作 k 默认值为 -1 表示没有找到,然后将模式串向后移动i - k位 此时通过坏字符 c模式串 abd 中查找发现没有找到,那么 k = -1,此时移动 2 - (-1) = 3 位,如下

此时坏字符是 a 对应的模式串中字符的位置仍然是 2,继续从模式串中查找坏字符,找到了 k = 0

此时模式串需要向后移动 i - k 位 2 - 0 = 2 位,匹配成功

3. 好后缀规则(good-suffix shift)

3.1 好后缀

对于主串模式串来说存在相等的串就是好后缀(从后向前)

3.2 模式串的移动(第1种情况)

模式串中寻找(从后向前),是否还有与好后缀一样的字符串,如果有的话将其向后移动到之前好后缀的位置,如下

那么如果说模式串中没有与好后缀一样的字符串该怎么办呢?

在讲述之前需要先了解几个概念帮助后续的理解分别是

  • 好后缀的后缀子串:

    假设模式串为 bccabc 此时的好后缀为 abc 那么它的后缀子串分别是 bc,b

  • 模式串的前缀子串:

    假设模式串为 bccabc 此时的好后缀为 abc 那么它的前缀子串分别是 bc,b

3.3 模式串的移动(第2种情况)

在计算好后缀的子串模式串的前缀子串的时候,长度保存一致才有意义,比如好后缀为 abc 三位,好后缀子串最多为 2 位,那么求模式串前缀的时候也只需要至多取前 2 位就可以了。 因为取 3 位的话就是 模式串的移动(第1种情况)模式串中还有另外的好后缀相等的情况了。如果超过 3 位的话匹配就没有意义了 此时好后缀 abc 的好后缀子串 bc 正好跟模式串的前缀子串 bc 一致,那么就将模式串中前缀子串移动到好后缀的 bc 处,如下

此时在模式串 bccabc 中找到了 bc ,然后将其移动到当前位置最终匹配成功,如果最后一个字符还不相等意味着匹配失败,没有找到。

4. 坏字符规则 & 好后缀规则 使用原则

在进行匹配算法的时候,可以将二者结合使用,算出坏字符规则的移动位数,再算出好后缀规则的移动位数取较大的作为真正的向后移动位数,能够保证更高效的匹配.

5. Golang BM 算法代码实现

Go语言标准库中里在 strings/search.go 里使用了Boyer-Moore字符串搜索算法

type stringFinder struct {
	// pattern is the string that we are searching for in the text.
	pattern string

	// badCharSkip[b] contains the distance between the last byte of pattern
	// and the rightmost occurrence of b in pattern. If b is not in pattern,
	// badCharSkip[b] is len(pattern).
	//
	// Whenever a mismatch is found with byte b in the text, we can safely
	// shift the matching frame at least badCharSkip[b] until the next time
	// the matching char could be in alignment.
	badCharSkip [256]int

	// goodSuffixSkip[i] defines how far we can shift the matching frame given
	// that the suffix pattern[i+1:] matches, but the byte pattern[i] does
	// not. There are two cases to consider:
	//
	// 1. The matched suffix occurs elsewhere in pattern (with a different
	// byte preceding it that we might possibly match). In this case, we can
	// shift the matching frame to align with the next suffix chunk. For
	// example, the pattern "mississi" has the suffix "issi" next occurring
	// (in right-to-left order) at index 1, so goodSuffixSkip[3] ==
	// shift+len(suffix) == 3+4 == 7.
	//
	// 2. If the matched suffix does not occur elsewhere in pattern, then the
	// matching frame may share part of its prefix with the end of the
	// matching suffix. In this case, goodSuffixSkip[i] will contain how far
	// to shift the frame to align this portion of the prefix to the
	// suffix. For example, in the pattern "abcxxxabc", when the first
	// mismatch from the back is found to be in position 3, the matching
	// suffix "xxabc" is not found elsewhere in the pattern. However, its
	// rightmost "abc" (at position 6) is a prefix of the whole pattern, so
	// goodSuffixSkip[3] == shift+len(suffix) == 6+5 == 11.
	goodSuffixSkip []int
}

func makeStringFinder(pattern string) *stringFinder {
	f := &stringFinder{
		pattern:        pattern,
		goodSuffixSkip: make([]int, len(pattern)),
	}
	// last is the index of the last character in the pattern.
	last := len(pattern) - 1

	// Build bad character table.
	// Bytes not in the pattern can skip one pattern's length.
	for i := range f.badCharSkip {
		f.badCharSkip[i] = len(pattern)
	}
	// The loop condition is < instead of <= so that the last byte does not
	// have a zero distance to itself. Finding this byte out of place implies
	// that it is not in the last position.
	for i := 0; i < last; i++ {
		f.badCharSkip[pattern[i]] = last - i
	}

	// Build good suffix table.
	// First pass: set each value to the next index which starts a prefix of
	// pattern.
	lastPrefix := last
	for i := last; i >= 0; i-- {
		if HasPrefix(pattern, pattern[i+1:]) {
			lastPrefix = i + 1
		}
		// lastPrefix is the shift, and (last-i) is len(suffix).
		f.goodSuffixSkip[i] = lastPrefix + last - i
	}
	// Second pass: find repeats of pattern's suffix starting from the front.
	for i := 0; i < last; i++ {
		lenSuffix := longestCommonSuffix(pattern, pattern[1:i+1])
		if pattern[i-lenSuffix] != pattern[last-lenSuffix] {
			// (last-i) is the shift, and lenSuffix is len(suffix).
			f.goodSuffixSkip[last-lenSuffix] = lenSuffix + last - i
		}
	}

	return f
}

func longestCommonSuffix(a, b string) (i int) {
	for ; i < len(a) && i < len(b); i++ {
		if a[len(a)-1-i] != b[len(b)-1-i] {
			break
		}
	}
	return
}

// next returns the index in text of the first occurrence of the pattern. If
// the pattern is not found, it returns -1.
func (f *stringFinder) next(text string) int {
	i := len(f.pattern) - 1
	for i < len(text) {
		// Compare backwards from the end until the first unmatching character.
		j := len(f.pattern) - 1
		for j >= 0 && text[i] == f.pattern[j] {
			i--
			j--
		}
		if j < 0 {
			return i + 1 // match
		}
		i += max(f.badCharSkip[text[i]], f.goodSuffixSkip[j])
	}
	return -1
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流, 谢谢大家对mojotv.cn的支持.喜欢这个网站麻烦帮忙添加到收藏夹,添加我的微信好友: felixarebest 微博账号: MojoTech向我提问.

目录