arXiv preprint ·
Boyer-Moore Variants for Indeterminate String Matching and Experimental Evaluation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A Deterministic Polynomial Kernel for Odd Cycle Transversal
$c$-Packedness versus $λ$-Low-Density in Geometric Graphs: Theory and Practice
Parameterized Complexity of Spanner Problems with Independent Weights and Lengths
Sampling Line-Graph Colorings with Constant Extra Colors
A Faster Algorithm for Fewer Vertex-Disjoint Paths Parameterized by Treewidth
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.