Improved Boyer-Moore methods speed up matching in complex string patterns
Boyer-Moore Variants for Indeterminate String Matching and Experimental Evaluation
Data Structures and Algorithms
Summary
Sometimes, matching patterns in text is tricky because parts can represent multiple letters instead of just one. The authors studied ways to improve a popular method called Boyer-Moore, creating faster rules and new techniques for handling these multi-letter positions. They tested many algorithm versions using synthetic data and genome sequences, finding some that are much faster than existing methods. Their results can help anyone who needs to search complex string data more efficiently.
What this means in practice
- •For bioinformatics teams: Search DNA sequences containing ambiguous bases more quickly using improved string-matching algorithms tailored for indeterminate data.
- •For software developers: Build faster text searching tools that handle uncertain or multi-symbol patterns in large datasets using the new Boyer-Moore variants.
Authors
Neerja Mhaskar, Nivetha Raj Pappuraj
Abstract
We study exact pattern matching on indeterminate strings, where a text or pattern position may represent a set of symbols rather than a single letter. Focusing on Boyer-Moore-style methods, we present new bad-character rules (BC Rules I-IV) and a new good-suffix procedure, computed by Fast_GSR_Indet_Shift, which avoids the per alignment recomputation used in BM_Indet [12] by shifting with a single preprocessed position-indexed table. We conduct a systematic experimental evaluation of sixteen algorithms, including classical bad-character adaptations (e.g., Horspool, Sunday, and Zhu-Takaoka) and hybrids that combine these bad-character rules with Fast_GSR_Indet_Shift. Across synthetic scaling experiments and a case study on the E. coli K-12 MG1655 genome, the Fast_BM_Indet hybrids consistently outperform BM_Indet and KMP_Indet [12], in some settings by up to two orders of magnitude. We also find that Zhu-Takaoka is the strongest bad-character-only adaptation on small alphabets and genomic data, while the Fast_BM_Indet variant using BC Rule I offers comparable performance, making it attractive for larger alphabets. We conclude with practical guidance on choosing among these variants for indeterminate string applications.