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

栏目: Swift · 发布时间: 6年前

内容简介：本文是对:octopus:

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

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

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

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

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

这个主题已经有教程 here

目标：在纯Swift中编写字符串搜索算法，而无需导入 Foundation 或使用 NSString 的 rangeOfString() 方法。

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

例子：

// Input:
let s = "Hello, World"
s.indexOf(pattern: "World")

// Output:
<String.Index?> 7

// Input:
let animals = ":dog::chicken::pig::cow::cat:"
animals.indexOf(pattern: ":cow:")

// Output:
<String.Index?> 6

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

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

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

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

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
    }
}

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

source string:  Hello, World
search pattern: World
                    ^

有三种可能性：

这两个字符是相同的。你找到了可能的匹配。
字符不相等，但源字符确实有出现在搜索模式其他位置中。
源字符完全没有出现在搜索模式中。

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

source string:  Hello, World
search pattern:    World
                       ^

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

source string:  Hello, World
search pattern:        World
                           ^

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

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

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算法的一个实现：

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算法讲的比较清晰。

以上所述就是小编给大家介绍的《【译】Swift算法俱乐部-Boyer-Moore字符串搜索》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对码农网的支持！

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

Programming in Haskell

Graham Hutton / Cambridge University Press / 2007-1-18 / GBP 34.99

Haskell is one of the leading languages for teaching functional programming, enabling students to write simpler and cleaner code, and to learn how to structure and reason about programs. This introduc......一起来看看《Programming in Haskell》这本书的介绍吧!

码农工具