A New Substring Searching Algorithm

Xiao Zhao, Sihui Li, Yun Yang, Yuyan Chao, Lifeng HeIEICE 2014 · DOI

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:

  1. 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]$).
  2. Suffix Shift (Deep Mismatches): If the mismatch occurs deeper in the pattern (further to the left), the algorithm automatically applies the "good-suffix" strategy.
Shift strategies used in the proposed algorithm to determine jump distances.

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.

Comparison of average search times for small-alphabet strings across various pattern lengths.

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

Abstract

This paper proposes a new algorithm for substring searching. Our algorithm is an improvement on the famous BM algorithm. When a mismatch happens while searching a substring (pattern), the BM algorithm will use two strategies to calculate shifting distances of the substring respectively and selects the larger one. In comparison, our algorithm uses each of the two strategies for their most suitable cases separately without a selection operation. Experimental results demonstrated that our algorithm is more efficient than the BM algorithm and the Quick Search algorithm, especially for binary strings and DNA strings.
BibTeX
@inproceedings{zhao2014new,
  author = {Xiao Zhao and Sihui Li and Yun Yang and Yuyan Chao and Lifeng He},
  title = {{A New Substring Searching Algorithm}},
  booktitle = {IEICE},
  year = {2014},
  doi = {10.1587/transinf.e97.d.1893},
}

Loading related content...

Figure