Boyer-Moore vs Boyer-Moore-Horspool Search Algorithms

Boyer-Moore and Boyer-Moore-Horspool are two efficient search algorithms provided by the C++ standard library.

Both are designed for substring searches and can be significantly faster than a simple linear search, especially for large texts.

Boyer-Moore Search Algorithm

The Boyer-Moore algorithm is known for its efficiency in practice. It preprocesses the pattern to create two tables that are used to skip sections of the text, making the search faster.

Benefits:

• Fast for Large Patterns: It can skip large sections of text, making it efficient for long patterns.
• Good Average Performance: Generally performs well across various types of text and patterns.

The following example shows how we can use std::boyer_moore_searcher:

1#include <algorithm>
2#include <functional>
3#include <iostream>
4#include <string>
5
6int main() {
7  std::string text = "Lorem ipsum dolor sit"
8    " amet, consectetur adipiscing elit.";
9  std::string pattern = "dolor";
10
11  std::boyer_moore_searcher searcher(
12    pattern.begin(), pattern.end());
13  auto result = std::search(
14    text.begin(), text.end(), searcher);
15
16  if (result != text.end()) {
17    std::cout << "Pattern found at position "
18      << std::distance(text.begin(), result);
19  } else {
20    std::cout << "Pattern not found";
21  }
22}

1Pattern found at position 12

Boyer-Moore-Horspool Search Algorithm

The Boyer-Moore-Horspool algorithm is a simplified version of the Boyer-Moore algorithm. It only uses one table for preprocessing, which makes it simpler and sometimes faster for certain types of input.

Benefits:

• Simpler Implementation: Easier to understand and implement compared to Boyer-Moore.
• Faster for Short Patterns: Can be faster when the pattern is relatively short.

The following example shows how we can use std::boyer_moore_horspool_searcher:

1#include <algorithm>
2#include <functional>
3#include <iostream>
4#include <string>
5
6int main() {
7  std::string text = "Lorem ipsum dolor sit amet,"
8    " consectetur adipiscing elit.";
9  std::string pattern = "dolor";
10
11  std::boyer_moore_horspool_searcher searcher(
12    pattern.begin(), pattern.end());
13  auto result = std::search(
14    text.begin(), text.end(), searcher);
15
16  if (result != text.end()) {
17    std::cout << "Pattern found at position "
18      << std::distance(text.begin(), result);
19  } else {
20    std::cout << "Pattern not found";
21  }
22}

1Pattern found at position 12

Key Differences

• Preprocessing: Boyer-Moore uses two tables (bad character and good suffix) for preprocessing, while Boyer-Moore-Horspool uses only the bad character table.
• Performance: Boyer-Moore can be faster for longer patterns and more complex texts due to its more sophisticated skipping mechanism. Boyer-Moore-Horspool might be faster for shorter patterns.

Choosing Between the Two

• Use Boyer-Moore: When dealing with longer patterns or when the search performance is critical across varied text data.
• Use Boyer-Moore-Horspool: For simpler and shorter patterns, where its simplicity and speed can be advantageous.

In summary, both algorithms are powerful tools for efficient substring searches. Your choice between them should depend on the specific requirements of your text data and pattern length.