Abstract
This paper proposes a new algorithm for substring searching that improves upon the Boyer-Moore (BM) algorithm. By eliminating the selection operation typically used to choose between shift strategies at every mismatch, our algorithm applies specific rules based on mismatch depth. Experimental results demonstrate that this approach is more efficient than both the BM and Quick Search (QS) algorithms, particularly for binary and DNA strings.
Introduction
Substring searching is a fundamental operation in computing, used in applications ranging from text editing to bioinformatics. The Boyer-Moore (BM) algorithm, established in 1977, uses "bad-character" and "good-suffix" rules to determine shift distances upon a mismatch, selecting the maximum of the two. However, this selection process introduces computational overhead at every mismatch. Furthermore, while variants like Quick Search (QS) perform well on large alphabets (e.g., English text), they are less effective on small alphabets like DNA or binary data, where mismatches often occur deep within the pattern. This paper introduces an optimized algorithm designed to maintain high efficiency across diverse data types by streamlining the shift logic.
Methods
The core innovation of the proposed algorithm is a conditional strategy that replaces the standard max(skip1, skip2) selection operation. The algorithm uses a threshold $w$ to determine the appropriate shift rule:
- Quick Shift (Shallow Mismatches): If a mismatch occurs at the rightmost characters of the pattern, the algorithm employs a "bad-character" shift similar to the QS algorithm, looking at the character in the text immediately following the current window ($t[i+m]$).
- Suffix Shift (Deep Mismatches): If the mismatch occurs deeper in the pattern (further to the left), the algorithm automatically applies the "good-suffix" strategy.
This logic leverages the statistical observation that for small alphabets, the good-suffix rule is more likely to yield a larger jump for deep mismatches. Empirical testing identified $w = m - 2$ as an effective heuristic for binary and DNA data.
Experimental Setup
The algorithm was evaluated against BM and QS using three datasets from the SMART corpus:
- English Text: The Bible (4.0 MB).
- Binary String: A 5.0 MB file with two characters.
- DNA String: A 4.5 MB genetic sequence with four characters. Performance was measured across pattern lengths ranging from 3 to 100 characters.
Results
The proposed algorithm consistently outperformed both BM and QS across the tested datasets. The efficiency gain is most pronounced in binary and DNA strings, where deep mismatches are frequent.
In English text, the algorithm showed marginal improvements over QS and significant gains over BM. For a pattern length of 3, execution times were 16.53ms (BM), 9.32ms (QS), and 9.14ms (Ours). By replacing the max() comparison with a simple if-else check, the algorithm reduces per-iteration CPU cycles while maintaining or increasing shift distances.
Conclusion
The new algorithm offers a streamlined alternative to traditional substring searching methods. By tailoring shift strategies to mismatch depth and removing redundant selection logic, it achieves superior performance, especially for data with small alphabets. Future work will explore integrating Knuth-Morris-Pratt (KMP) strategies for $O(n)$ worst-case guarantees and applying the algorithm to large-scale virus signature detection.
Summary updated