concept · INFO-CS-ADS-199Boyer-Moore Algorithm
Understand how Boyer-Moore accelerates pattern searching by comparing characters from right to left and skipping unnecessary text positions using mismatch information.
Explanation
Overview
Boyer-Moore is an efficient string-searching algorithm that compares the pattern with the text from right to left. When a mismatch occurs, it uses preprocessing information to shift the pattern by multiple positions instead of moving it forward one character at a time.
Key concepts
Right-to-left comparison; Bad-character heuristic; Good-suffix heuristic; Pattern preprocessing; Safe pattern shifting; Search optimization
Variables
text: The larger string being searched.; pattern: The pattern being located.; n: The length of the text.; m: The length of the pattern.; i: The current alignment position of the pattern in the text.; j: The pattern index currently being compared.
Complexity
preprocessing: Typically O(m + alphabetSize) for common table-based implementations, with details depending on the heuristic implementation.; searchAverage: Often sublinear in practice because it can skip multiple text positions.; worstCase: Depends on the exact Boyer-Moore variant and implementation; classical variants have different worst-case guarantees, while optimized variants can achieve linear worst-case behavior.; space: Depends on the alphabet size and preprocessing tables.
Example
text: HERE IS A SIMPLE EXAMPLE; pattern: EXAMPLE; explanation: Boyer-Moore begins comparisons at the rightmost character of the pattern. When a mismatch occurs, its heuristics can skip several positions based on the character and the already matched suffix.; result: Pattern found at index 17 using zero-based indexing.
Pseudocode
function boyerMoore(text, pattern):
preprocessBadCharacter(pattern)
preprocessGoodSuffix(pattern)
shift = 0
while shift <= length(text) - length(pattern):
j = length(pattern) - 1
while j >= 0 and pattern[j] == text[shift + j]:
j -= 1
if j < 0:
report shift
shift += safeMatchShift()
else:
badShift = badCharacterShift(text[shift + j], j)
goodShift = goodSuffixShift(j)
shift += max(1, badShift, goodShift)
Applications
Text editors.; Document searching.; Large text-file processing.; Search utilities.; Information retrieval.
Variables
Text
The larger string being searched.
Pattern
The pattern being located.
M
The length of the pattern.
I
The current alignment position of the pattern in the text.
J
The pattern index currently being compared.
Shift
The number of positions by which the pattern moves after a mismatch.
Example or application
Text
HERE IS A SIMPLE EXAMPLE
Explanation
Boyer-Moore begins comparisons at the rightmost character of the pattern. When a mismatch occurs, its heuristics can skip several positions based on the character and the already matched suffix.
Result
Pattern found at index 17 using zero-based indexing.
Definition
Boyer-Moore is an efficient string-searching algorithm that compares the pattern with the text from right to left. When a mismatch occurs, it uses preprocessing information to shift the pattern by multiple positions instead of moving it forward one character at a time.
Fundamental Heuristics
Bad Character Rule
Uses the mismatching text character and its last occurrence in the pattern to determine a safe shift.
Good Suffix Rule
Uses the portion of the pattern that matched before the mismatch to find another compatible occurrence or matching prefix.
Combined Rules
The algorithm commonly chooses the larger safe shift suggested by the bad-character and good-suffix rules.
Algorithm Steps
Preprocess the pattern to construct the bad-character information.
Preprocess the pattern to construct the good-suffix information when using the full algorithm.
Align the pattern with the current text position.
Compare characters from right to left.
If all characters match, record the occurrence.
If a mismatch occurs, calculate safe shifts using the available heuristics.
Move the pattern by the largest valid shift.
Repeat until the pattern cannot fit within the remaining text.
Pseudocode
function boyerMoore(text, pattern):
preprocessBadCharacter(pattern)
preprocessGoodSuffix(pattern)
shift = 0
while shift <= length(text) - length(pattern):
j = length(pattern) - 1
while j >= 0 and pattern[j] == text[shift + j]:
j -= 1
if j < 0:
report shift
shift += safeMatchShift()
else:
badShift = badCharacterShift(text[shift + j], j)
goodShift = goodSuffixShift(j)
shift += max(1, badShift, goodShift)
Complexity
Preprocessing
Typically O(m + alphabetSize) for common table-based implementations, with details depending on the heuristic implementation.
Search Average
Often sublinear in practice because it can skip multiple text positions.
Worst Case
Depends on the exact Boyer-Moore variant and implementation; classical variants have different worst-case guarantees, while optimized variants can achieve linear worst-case behavior.
Space
Depends on the alphabet size and preprocessing tables.
Key Concepts
Right-to-left comparison
Bad-character heuristic
Good-suffix heuristic
Pattern preprocessing
Safe pattern shifting
Search optimization
Advantages
Can skip multiple positions after a mismatch.
Often performs very well for long patterns and large alphabets.
Reduces unnecessary character comparisons in many practical cases.
Uses information from both mismatches and previously matched suffixes.
Limitations
The full algorithm is more complicated than naive matching.
Preprocessing may be unnecessary for very short patterns.
Performance depends on the text, pattern, alphabet, and selected variant.
Different implementations provide different worst-case guarantees.
Related Topics
Naive Pattern Matching
KMP Algorithm
Rabin-Karp Algorithm
Pattern Matching
Practice Question
In which direction does Boyer-Moore compare pattern characters?
Practice Answer
From right to left, beginning with the last character of the pattern.
Learning Objectives
Explain the central idea and purpose of boyer-moore algorithm.
Identify the assumptions, inputs, and conditions relevant to boyer-moore algorithm.
Evaluate an application of boyer-moore algorithm for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- String Algorithms and Pattern Matching
Suggest a correction or source · More in Algorithms & Data Structures