Swift Algorithm Club: Boyer Moore String Search Algorithm

The Swift Algorithm Club is an open source project on implementing data structures and algorithms in Swift.

Every month, Vincent Ngo, Ross O’Brien and I feature a cool data structure or algorithm from the club in a tutorial on this site. If you want to learn more about algorithms and data structures, follow along with us!

In this tutorial, you’ll analyze 2 algorithms:

• Brute Force string search by Matthijs Hollemans
• Boyer Moore string search by Matthijs Hollemans

Getting Started

It’s fairly simple to illustrate just how important string searching algorithms are in the world. Press CMD + F and try to search for the letter c. You get the results almost instantly. Now imagine if that took 10 seconds to compute… you might as well retire!

Brute Force It!

The brute force method is relatively straightforward. To understand the brute force string method, consider the string "HELLO WORLD":

For the purposes of this tutorial, there are a few things to keep in mind.

1. Your search algorithm should be case sensitive.
2. The algorithm should return the index of the first match.
3. Partial matches should work. For example:

   let text = "HELLO WORLD"
   text.index(of: "ELLO") // returns 1
   text.index(of: "LD") // returns 9
   

let text = "HELLO WORLD"
text.index(of: "ELLO") // returns 1
text.index(of: "LD") // returns 9

The algorithm is fairly straightforward. For example, assume you are looking for the pattern "LO". You’ll begin by iterating through the source string. As soon as you reach a character that matches the first character of your lookup string, you’ll try to match the rest of the characters. Otherwise, you’ll move on through the rest of the string:

Implementation

You’ll write this method as an extension of String. Using Xcode 9 beta 2 or later, create a new Swift playground. Delete the boilerplate code so you have a blank playground page. You’ll start by creating a stub of the implementation inside a String extension. Write the following at the top of your playground:

extension String {
  func index(of pattern: String) -> Index? {
    // more to come
    return nil
  }
}

This purpose of this function is simple: Given a string (hereby referred to as the source string), you check to see if another string is within it (hereby referred to as the pattern). If a match can be made, it’ll return the index of the first character of the match. If this method can’t find a match, it’ll return nil.

As of Swift 4, String exposes the indices property, which contains all the indexes that is used to subscript the string. You’ll use this to iterate through your source string. Update the function to the following:

func index(of pattern: String) -> Index? {
  // 1
  for i in indices {

    // 2
    var j = i
    var found = true
    for p in pattern.indices {
      guard j != endIndex && self[j] == pattern[p] else { found = false; break }
      j = index(after: j)
    }
    if found {
      return i
    }
  }
  return nil
}

This does exactly what you wanted:

1. You loop over the indices of the source string
2. You attempt to match the pattern string with the source string.

As soon as you find a match, you’ll return the index. It’s time to test it out. Write the following at the bottom of your playground:

let text = "Hello World"
text.index(of: "lo") // returns 3
text.index(of: "ld") // returns 9

The brute force approach works, but it’s relatively inefficient. In the next section, you’ll look at how you can make use of a clever technique to optimize your algorithm.

Boyer Moore String Search

As it turns out, you don’t need to look at every character from the source string — you can often skip ahead multiple characters. The skip-ahead algorithm is called Boyer Moore and it’s been around for some time. It is considered the benchmark for all string search algorithms.

This technique builds upon the brute force method, with 2 key differences:

1. Pattern matching is done backwards.
2. Uses a skip table to perform aggressive skips during traversal

Here’s what it looks like:

The Boyer Moore technique makes use of a skip table. The idea is fairly straightforward. You create a table based on the word you’d like to match. The table is responsible for holding the number of steps you may skip for a given letter of the word. Here’s a skip table for the word "HELLO":

You’ll use the skip table to decide how many traversals you should skip forward. You’ll consult the skip table before each traversal in the source string. To illustrate the usage, take a look at this specific example:

In this situation, you’re comparing the "H" character in the source string. Since this doesn’t match the last character in the pattern, you’ll want to move down the source string. Before that, you would consult the skip table to see if there’s an opportunity to do some skips. In this case, "H" is in the skip table and you’re able to perform a 4 index skip.

Back in your Swift playground, delete the implementation of index(of:), except for return nil:

func index(of pattern: String) -> Index? {
  return nil 
}

The Skipping Table

You’ll start by dealing with the skip table. Write the following inside the String extension:

fileprivate var skipTable: [Character: Int] {
  var skipTable: [Character: Int] = [:]
  for (i, c) in enumerated() {
    skipTable[c] = count - i - 1
  }
  return skipTable
}

This will enumerate over a string and return a dictionary with it’s characters as keys and an integer representing the amount it should skip by. Verify that it works. At the bottom of your playground write the following:

let helloText = "Hello"
helloText.skipTable.forEach { print($0) }

You should see the following in the console:

(key: "H", value: 4)
(key: "L", value: 1)
(key: "O", value: 0)
(key: "E", value: 3)

This matches the table diagram from earlier.