Boyer-Moore 算法是一種非常高效的字符串搜索算法，被廣泛的應(yīng)用于多種字符串搜索場(chǎng)景：

• 文本搜索（尤其是大篇幅的文本搜索）
• 文檔編輯器以及 IDE 工具中的字符串搜索/替換
• 編譯器中搜索源代碼中的關(guān)鍵字/符號(hào)
• 文件系統(tǒng)中搜索給定的文件名

通常，在字符串搜索過(guò)程中，我們期望盡快得到結(jié)果（提高算法運(yùn)行速度，降低時(shí)間復(fù)雜度），為此我們需要對(duì)字符串（文本以及搜索的子串）進(jìn)行一些預(yù)處理。對(duì)于大文本，該預(yù)處理過(guò)程會(huì)消耗可觀的內(nèi)存空間，而如果在搜索過(guò)程中該預(yù)處理過(guò)程需要反復(fù)進(jìn)行，則又會(huì)消耗相當(dāng)?shù)?CPU 資源。

Boyer-Moore 算法只需要對(duì)被搜索的子串進(jìn)行一次預(yù)處理，通過(guò)在本次預(yù)處理過(guò)程中收集到的信息來(lái)提升算法的運(yùn)行效率，使得算法的時(shí)間復(fù)雜度盡量趨近于 O(n)。Boyer-Moore 算法的一個(gè)顯著特征是匹配過(guò)程從子串的末尾開(kāi)始向前，如果遇到不匹配的字符，則根據(jù)在預(yù)處理過(guò)程中收集到的信息進(jìn)行跳躍/移動(dòng)，避免逐個(gè)字符進(jìn)行比較。而具體的跳躍/移動(dòng)規(guī)則，則同時(shí)使用兩種策略實(shí)現(xiàn)：

• 壞字符啟發(fā)
• 好后綴啟發(fā)

⒈ 壞字符啟發(fā)

在將子串中的字符與文本中的字符進(jìn)行比較時(shí)，如果文本中的字符與子串中的字符不匹配，我們稱文本中的當(dāng)前字符為壞字符。對(duì)于壞字符，通常有兩種處理方式：

壞字符在子串中的其他位置存在

當(dāng)壞字符在子串中存在時(shí)，如果壞字符在子串中的位置位于當(dāng)前索引位置之前，則將子串中的壞字符與文本中的壞字符對(duì)齊，然后重新從子串的最后開(kāi)始向前與文本中的字符進(jìn)行匹配；如果壞字符在子串中的位置位于當(dāng)前索引位置之后，則將子串向后移動(dòng)一個(gè)字符的位置，然后重新開(kāi)始從子串的最后開(kāi)始向前與文本中的字符進(jìn)行匹配。

如上圖所示，從后往前將子串中的字符與文本中的字符進(jìn)行比較，子串中的字符 C 與文本中的 R 不匹配。但文本中的字符 R 在子串中的其他位置存在，此時(shí)將子串中的 R 與文本中的 R 對(duì)齊，然后重新從后往前進(jìn)行匹配。

在對(duì)子串進(jìn)行預(yù)處理時(shí)，由于子串中 R 出現(xiàn)了兩次，所以實(shí)際預(yù)處理完成之后收集到的信息中記錄的是位于 C 之后的 R 的位置信息。所以，實(shí)際在代碼中，遇到這種情況，子串只能向后移動(dòng)一個(gè)字符的位置。

壞字符在子串中不存在

如果壞字符在子串中不存在，那么移動(dòng)子串，將子串的第一個(gè)字符與文本中壞字符之后的字符對(duì)齊，然后重新從后往前將子串中的字符與文本中的字符進(jìn)行匹配。

如上圖所示，壞字符 G 與子串中的字符 Q 不匹配，并且壞字符 G 在子串中并不存在，此時(shí)將子串移動(dòng)到與壞字符 G 后的字符對(duì)齊，然后重新從后往前開(kāi)始匹配。

package main

import (
	"fmt"
)

func main() {
	text := "AYRRQMGRPCRQ"
	subStr := "RPCRQ"
	fmt.Printf("text = %+v\n", text)
	fmt.Printf("subStr = %+v\n", subStr)

	// 構(gòu)建子字符串中各個(gè)字符及相應(yīng)的索引的映射
	m := make(map[byte]int, len(subStr))
	for i := 0; i < len(subStr); i ++ {
		m[subStr[i]] = i
	}
	fmt.Printf("m = %+v\n", m)

	shiftLength := 0
	subIndex := len(subStr) - 1
	for shiftLength <= len(text) - len(subStr) {
		// 每次比較都從子字符串的末尾開(kāi)始向前，逐個(gè)字符進(jìn)行比較
		for subIndex >= 0 && text[shiftLength + subIndex] == subStr[subIndex] {
			subIndex --
		}

		if subIndex == -1 {
			// 子字符串在文本中出現(xiàn)，跳過(guò)文本中的子字符串繼續(xù)向后查找
			fmt.Printf("subStr found in text at index %+v\n", shiftLength)
			shiftLength += len(subStr)
		} else if v, ok := m[text[shiftLength + subIndex]]; ok {
			// 文本中的字符與子字符串中相應(yīng)位置的字符不匹配，但該字符在子字符串中存在
			if subIndex > v {
				// 如果該字符在子字符串中的位置在當(dāng)前索引位置之前，則將二者位置對(duì)齊，然后重新查找
				shiftLength += subIndex - v
			} else {
				// 文本中的索引位置向前移動(dòng)一個(gè)字符（考慮子字符串中同一個(gè)字符重復(fù)出現(xiàn)的情況）
				shiftLength += 1
			}
		} else {
			// 文本中的字符在子字符串中不存在
			shiftLength += subIndex
		}

		subIndex = len(subStr) - 1
	}
}

⒉ 好后綴啟發(fā)

在將子串按照從后往前的順序與文本中的字符進(jìn)行比較時(shí)，遇到不匹配的字符時(shí)，子串末尾已經(jīng)匹配得字符即為好后綴。此時(shí)根據(jù)好后綴在子串中其他位置是否存在，重新確定子串在文本中開(kāi)始匹配的位置。

好后綴或好后綴的后綴在子串中的其他位置存在

如上圖所示，從后往前將子串中的字符與文本進(jìn)行匹配，文本中字符 Y 與子串中相應(yīng)位置的字符 Q 不匹配，此時(shí)出現(xiàn)好后綴 CRQ。雖然好后綴 CRQ 在子串中只出現(xiàn)了一次，但好后綴的后綴 RQ 卻在子串的頭部再次出現(xiàn)，此時(shí)將子串頭部的 RQ 與文本中的 RQ 對(duì)齊，然后重新從后往前匹配。

好后綴在子串中不存在

如上圖所示，子串中不存在好后綴，此時(shí)只要將文本中的起始匹配位置向后移動(dòng)一個(gè)字符，然后重新從后往前匹配。

起始匹配位置移動(dòng)之后，子串中出現(xiàn)了好后綴 RQ，并且 RQ 在子串的頭部也存在。此時(shí)，將子串頭部的 RQ 與文本中的 RQ 對(duì)齊，確定新的匹配開(kāi)始位置，重新匹配。

好后綴啟發(fā)的關(guān)鍵在于對(duì)子串的預(yù)處理。

在對(duì)子串進(jìn)行預(yù)處理的過(guò)程中，需要確定子串中單個(gè)字符以及多個(gè)連續(xù)字符出現(xiàn)的頻次以及相應(yīng)的位置。當(dāng)匹配過(guò)程中出現(xiàn)好后綴時(shí)，會(huì)根據(jù)預(yù)處理過(guò)程中收集到的信息確定文本中新的開(kāi)始匹配的位置。

package main

import (
	"fmt"
)

func main() {
	text := "AYCRQMGRQCRQ"
	subStr := "RQCRQ"
	fmt.Printf("text = %+v\n", text)
	fmt.Printf("subStr = %+v\n", subStr)

	shifts := make([]int, len(subStr) + 1)
	borderPosition := make([]int, len(subStr) + 1)

	// 確定搜索字符串中各個(gè)子串的邊界
	i, j := len(subStr), len(subStr) + 1
	borderPosition[i] = j

	for i > 0 {
		for j >= 0 && j <= len(subStr) && subStr[i - 1] != subStr[j - 1] {
			if shifts[j] == 0 {
				shifts[j] = j - i
			}

			j = borderPosition[j]
		}

		i --
		j --
		borderPosition[i] = j
	}

	fmt.Printf("shifts = %+v\n", shifts)
	fmt.Printf("borderPosition = %+v\n", borderPosition)

	// 確定搜索字符串中各個(gè)字符與文本中的字符不匹配時(shí)應(yīng)該移動(dòng)的距離
	j = borderPosition[0]
	for i := 0; i <= len(subStr); i ++ {
		if shifts[i] == 0 {
			shifts[i] = j
		}

		if i == j {
			j = borderPosition[j]
		}
	}

	fmt.Printf("shifts = %+v\n", shifts)
	fmt.Printf("borderPosition = %+v\n", borderPosition)

	// 在文本中搜索字符串
	shiftLength := 0
	for shiftLength <= len(text) - len(subStr) {
		j = len(subStr) - 1
		for j >= 0 && subStr[j] == text[shiftLength + j] {
			j --
		}

		if j == -1 {
			fmt.Printf("subStr find in text at position %+v\n", shiftLength)
			shiftLength += shifts[0]
		} else {
			shiftLength += shifts[j + 1]
		}
	}
}

以上就是Go語(yǔ)言實(shí)現(xiàn)字符串搜索算法Boyer-Moore的詳細(xì)內(nèi)容，更多關(guān)于Go字符串搜索算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論