Fork me on GitHub

【译】Swift算法俱乐部-Boyer-Moore字符串搜索

本文是对 Swift Algorithm Club 翻译的一篇文章。

Swift Algorithm Clubraywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。

🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️,🤩🤩🤩🤨🤪。

本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Boyer-Moore String Search


Boyer-Moore字符串搜索(Boyer-Moore String Search)

这个主题已经有教程 here

目标:在纯Swift中编写字符串搜索算法,而无需导入Foundation或使用NSStringrangeOfString()方法。

换句话说,我们想在String上实现一个indexOf(pattern:String)扩展,它返回在字符串里面第一次出现搜索模式的String.Index,如果找不到模式则返回nil

例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
// Input:
let s = "Hello, World"
s.indexOf(pattern: "World")

// Output:
<String.Index?> 7

// Input:
let animals = "🐶🐔🐷🐮🐱"
animals.indexOf(pattern: "🐮")

// Output:
<String.Index?> 6

注意: 牛的索引是6,而不是你想象的3,因为字符串为表情符号使用更多的存储空间。String.Index的实际值并不那么重要,只是它指向字符串中的正确字符。

暴力方法工作正常,但效率不高,尤其是在大块文本上。 事实证明,您不需要从源字符串中查看 _每个_ 字符 —— 通常可以跳过多个字符。

这种跳过算法被称为Boyer-Moore算法,它已存在很长时间了。它被认为是所有字符串搜索算法的基准。

以下是您在Swift中编写它的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
extension String {
func index(of pattern: String) -> Index? {

let patternLength = pattern.count
guard patternLength > 0, patternLength <= self.count else { return nil }

var skipTable = [Character: Int]()
for (i, c) in pattern.enumerated() {
skipTable[c] = patternLength - i - 1
}

let p = pattern.index(before: pattern.endIndex)
let lastChar = pattern[p]

var i = index(startIndex, offsetBy: patternLength - 1)

func backwards() -> Index? {
var q = p
var j = i
while q > pattern.startIndex {
j = index(before: j)
q = index(before: q)
if self[j] != pattern[q] { return nil }
}
return j
}

while i < endIndex {
let c = self[i]

if c == lastChar {

if let k = backwards() { return k }

i = index(after: i)
} else {
i = index(i, offsetBy: skipTable[c] ?? patternLength, limitedBy: endIndex) ?? endIndex
}
}
return nil
}
}

该算法的工作原理如下。 让源字符与搜索模式字符头部对齐排列,并查看字符串中的哪个字符与搜索模式的 _最后_ 字符匹配:

1
2
3
source string:  Hello, World
search pattern: World
^

有三种可能性:

  1. 这两个字符是相同的。 你找到了可能的匹配。

  2. 字符不相等,但源字符确实有出现在搜索模式其他位置中。

  3. 源字符完全没有出现在搜索模式中。

在示例中,字符od不匹配,但o确实出现在搜索模式中。 这意味着我们可以跳过几个位置:

1
2
3
source string:  Hello, World
search pattern: World
^

注意两个o字符现在是如何对齐的。 再次,您将搜索模式的最后一个字符与搜索文本进行比较:W vsd。 它们是不相同的,但W确实出现在搜索模式中。 因此,再次跳过一个位置,让两个W字符在相同位置:

1
2
3
source string:  Hello, World
search pattern: World
^

这次两个字符相等并且可能匹配。 要验证匹配,您需要进行暴力搜索,但是从搜索模式的末尾开始向前搜索。 这就是它的全部。

在任何给定时间跳过的数量由“跳过表”确定,“跳过表”是搜索模式中所有字符的字典和跳过的数量。 示例中的跳过表如下所示:

1
2
3
4
5
W: 4
o: 3
r: 2
l: 1
d: 0

字符越接近模式的末尾,跳过量越小。 如果某个字符在模式中出现多次,则最接近该模式结尾的字符将确定该字符的跳过值。

注意: 如果搜索模式只包含几个字符,则执行暴力搜索会更快。 在构建跳过表与为短模式执行暴力搜索之间需要进行权衡。

致谢:此代码基于1989年7月Dr Dobb’s杂志发表的文章“Faster String Searches” by Costas Menico —— 对 ,1989年! 有时保留那些旧杂志是有用的。

扩展阅读:这个算法的详细分析

Boyer-Moore-Horspool 算法

上面算法的一个变体是Boyer-Moore-Horspool 算法

像常规的Boyer-Moore算法一样,它使用skipTable来跳过许多字符。 不同之处在于我们如何检查局部匹配。在上面的版本中,如果找到了部分匹配,但不是完全匹配,我们只跳过一个字符。在这个修订版本中,我们也在那种情况下使用跳过表。

这是Boyer-Moore-Horspool算法的一个实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
extension String {

func index(of pattern: String, usingHorspoolImprovement: Bool = false) -> Index? {

let patternLength = pattern.count
guard patternLength > 0, patternLength <= self.count else {
return nil
}

var skipTable = [Character: Int]()
for (i, c) in pattern.enumerated() {
skipTable[c] = patternLength - i - 1
}

let p = pattern.index(before: pattern.endIndex)
let lastChar = pattern[p]

var i = index(startIndex, offsetBy: patternLength - 1)

func backwards() -> Index? {
var q = p
var j = i
while q > pattern.startIndex {
j = index(before: j)
q = index(before: q)
if self[j] != pattern[q] { return nil }
}
return j
}

while i < endIndex {
let c = self[i]

if c == lastChar {

if let k = backwards() { return k }

if !usingHorspoolImprovement {
i = index(after: i)
} else {

let jumpOffset = max(skipTable[c] ?? patternLength, 1)
i = index(i, offsetBy: jumpOffset, limitedBy: endIndex) ?? endIndex
}
} else {
i = index(i, offsetBy: skipTable[c] ?? patternLength, limitedBy: endIndex) ?? endIndex
}
}
return nil
}
}

在实践中,Horspool版本的算法往往比原始版本略好一些。 但是,这取决于你愿意做出什么样的权衡。

致谢:此代码基于论文:R. N. Horspool (1980). “Practical fast searching in strings”. Software - Practice & Experience 10 (6): 501–506.

作者:Matthijs Hollemans,Andreas Neusüß,Matías Mazzei
翻译:Andy Ron
校对:Andy Ron

译注: 阮一峰老师的文章 字符串匹配的Boyer-Moore算法 讲的比较清晰。

坚持原创技术分享,您的支持将鼓励我继续创作!