PaperlayerView exact revision on arXiv

Source-linked AI summary

Boyer-Moore Variants for Indeterminate String Matching and Experimental Evaluation

Neerja Mhaskar, Nivetha Raj Pappuraj

arXiv:2609.27170v1cs.DS

TL;DR

Exact matching on indeterminate strings must handle positions that represent multiple possible symbols, including in genomic data. The paper introduces Boyer–Moore bad-character rules and a preprocessed good-suffix procedure, then evaluates sixteen algorithms. Its hybrids outperform existing KMP_Indet and BM_Indet, with practical variant choices depending on alphabet size and input.

  • Problem

    Indeterminate positions occur in genomic sequences, while systematic adaptation of the Boyer–Moore variant family remained an open direction.

    Source: §1 · p. 2

  • Method

    The paper adapts classical Boyer–Moore variants, proposes four bad-character rules and a good-suffix rule, and combines them into Fast_BM_Indet variants.

    Source: §4 · p. 4, §4.2 · pp. 6, 8

  • Results

    All four Fast_BM_Indet variants outperform KMP_Indet and BM_Indet and perform comparably to brute force; on σ = 4 and DNA, Zhu–Takaoka with Fast_GSR_Indet_Shift matches brute force.

    Source: §1 · p. 2, §5 · p. 12

  • Takeaways & Limitations

    Zhu–Takaoka is preferable on small alphabets, while BC Rule I is preferable on large alphabets because it uses an O(σ) table rather than Zhu–Takaoka’s O(σ²) pair table.

    Source: §5 · p. 12

    The paper assumes strings are over integer alphabets.

    Source: §2 · p. 3

Abstract

from arXiv · show

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.

1 Introduction

Indeterminate strings model ambiguous symbols at string positions, a feature found in genomic data. Earlier work developed several matching approaches, while systematic adaptation of Boyer–Moore variants remained open; this paper introduces new rules and evaluates them.

1 Introduction

  • Indeterminate positions arise in consensus sequences and SNP-annotated genomes, motivating evaluation on genomic data.Consensus sequences can be indeterminate where multiple bases occur at comparable frequency, and SNP-annotated references where individuals carry different bases.Source: §1 · p. 2
  • Prior work includes algorithms with O(mn), O(2^σ n log m), and output-sensitive FFT-based bounds; Dehghani et al. introduced prefix-array KMP- and BM-style algorithms.Systematically adapting the Boyer–Moore variant family remained an open direction.Source: §1 · p. 2
  • The Fast_BM_Indet variants outperform KMP_Indet and BM_Indet and perform comparably to brute force; BC Rule I is the strongest of the four hybrids.Among bad-character-only adaptations, Zhu–Takaoka performs best.Source: §1 · p. 2

2 Preliminaries

The preliminaries define indeterminate strings and their matching relation, then establish the prefix-array and alignment notation used by the algorithms. They also specify power-of-two encoding and an integer-alphabet assumption.

2 Preliminaries

  • An indeterminate string is a sequence of non-empty subsets of the alphabet with at least one position containing multiple symbols; two letters match when their sets intersect.A position is indeterminate when its letter has cardinality greater than one.Source: §2 · p. 3
  • The prefix array πx[i] gives the longest prefix matching a prefix of the suffix beginning at i; it takes O(n) time on solid strings and O(n√n) on indeterminate strings.The matching is defined using the paper’s indeterminate-letter relation.Source: §2 · p. 3
  • An alignment compares the pattern with a text window, and a shift advances that alignment by a positive number of positions.The alignment position ranges from 1 through n − m + 1.Source: §2 · p. 3
  • Power-of-two encoding represents each alphabet symbol by a distinct bit, so indeterminate letters are encoded by bitwise OR and match when their codes share a set bit.The strings are assumed to use integer alphabets.Source: §2 · p. 3

3 Boyer–Moore Algorithm and its Variants

The section characterizes Boyer–Moore variants by their bad-character and good-suffix rules, then compares the lookup strategies and their preprocessing and search costs. The classical algorithm combines both rules and applies the larger safe shift.

3 Boyer–Moore Algorithm and its Variants

  • Boyer–Moore compares the pattern against each window from right to left and shifts by the maximum of the bad-character and good-suffix shifts on mismatch.Its stated bounds are O(nm) worst-case and O(n/m) best-case search time.Source: §3 · p. 4
  • Bad-character-only variants differ in which text positions they examine, while BC+GS variants combine both rules and differ in how the good-suffix rule is realized.The variants include single-character and character-pair lookup strategies.Source: §3 · p. 4
  • Single-character bad-character variants require O(m + σ) preprocessing and O(σ) space; character-pair variants require O(m + σ²) preprocessing and O(σ²) space.Both families have O(nm) worst-case search time.Source: §3 · p. 4

4 Main Results

The section adapts classical Boyer–Moore bad-character-only variants to indeterminate strings and introduces four new bad-character rules paired with a fast good-suffix procedure. The resulting Fast_BM_Indet variants are correct and have worst-case bounds that improve on BM_Indet.

4.1 Bad Character Rule for Indeterminate Strings

  • The section adapts seven classical bad-character-only variants; for five single-character variants, indeterminate lookups use τ and cost O(σ), while the two character-pair variants replace τ with τcp.The adapted Horspool, Sunday, Raita, Smith, and Tuned Boyer–Moore algorithms have O(m + σ) preprocessing, O(σ) space, and O(nmσ) worst-case search time; Zhu–Takaoka and Berry–Ravindran have O(m + σ²), O(σ²), and O(nmσ) bounds, respectively.Source: §4 · p. 4, §4.1 · pp. 5–6

4.2 Faster Boyer–Moore Variants

  • BC Rule II takes the larger of Rule I’s fast solid-letter shift and BM_Indet’s shift, while Rule III uses solid letters at the matched suffix’s edges to select a shift.Rule III realigns an edge letter with its rightmost earlier occurrence, or moves it past the pattern.Source: §4.2 · p. 7
  • BC Rule IV selects the least-frequent solid letter in the matched suffix as its lookup character, breaking frequency ties by choosing the letter whose first occurrence is furthest right.Pattern-letter frequencies can be computed in O(mσ) time.Source: §4.2 · pp. 7–8
  • Fast_GSR_Indet_Shift computes good-suffix shifts from solid edge letters in the matched suffix and a preprocessed position-indexed table, avoiding per-alignment prefix-array construction.It checks earlier occurrences of the first edge letter for a second edge letter at the same distance; a suffix with no solid letters shifts by 1.Source: §4.2 · p. 8
  • Pairing each of BC Rules I–IV with Fast_GSR_Indet_Shift yields four Fast_BM_Indet variants, which correctly identify all occurrences of an indeterminate pattern in an indeterminate text.The proof relies on safe bad-character and good-suffix shifts and verifies all m characters at reported positions.Source: §4.2 · pp. 8–9
  • Fast_BM_Indet variants require at most O(nm + mσ^2) time and O(mσ) space, improving on BM_Indet by O(√m) in the worst case.Across tested inputs, they are faster than BM_Indet.Source: §4.2 · p. 9

5 Experimental Evaluation

The Fast_BM_Indet hybrids substantially outperform BM_Indet, while Zhu–Takaoka is the strongest bad-character-only variant on small alphabets and genomic data. Rule I offers comparable small-alphabet performance and is the fastest hybrid at σ = 20.

Experimental setup

  • Experiments compare sixteen algorithms on random strings over σ ∈ {4, 9, 20} and the E. coli K-12 MG1655 genome, with short and long text regimes.Text and pattern lengths scale as n = 1000i and m = 40i; each plotted point is the mean over 100 runs.Source: §5 · pp. 9–10

Combining Bad-Character Rules with the Good-Suffix Rule

  • At n = 10^6 on σ = 4, BM_Indet takes 2,333 ms versus 7 ms for the Zhu–Takaoka hybrid; every Fast_BM_Indet variant is dramatically faster than BM_Indet.The gap widens with text length, reaching two orders of magnitude on long texts.Source: §5 · p. 11, Figure 3 · p. 12

Scaling of the Bad-Character Rules

  • Zhu–Takaoka is the most dependable pair variant, lowest at every long-text size on small alphabets and ahead of or level with Berry–Ravindran elsewhere.Pair variants are fastest on σ = 4 and E. coli; their advantage shrinks as the alphabet grows, and at σ = 20 all Boyer–Moore variants lie in a narrow band.Source: §5 · pp. 10–11, Figure 1 · p. 10, Figure 2 · p. 11

Combining Bad-Character Rules with the Good-Suffix Rule

  • Rule I is within 10% of Zhu–Takaoka on small alphabets and is the fastest hybrid at σ = 20.Rule I uses one O(σ) table and one O(1) lookup per alignment, whereas Zhu–Takaoka requires an O(σ^2) pair table.Source: §5 · pp. 11–12
  • The Zhu–Takaoka hybrid matches brute force on σ = 4 and DNA, but is slower by factors of 1.5 at σ = 9 and 4 at σ = 20.The hybrids beat KMP_Indet on small alphabets and short texts; on DNA at n = 10^6, they are about 5× faster, while KMP_Indet catches up on long texts only at σ = 20.Source: §5 · pp. 11–12

A.1 Boyer Algorithm

Classical Boyer–Moore computes shifts from a bad-character table and good-suffix tables. The bad-character shift uses the mismatching text character, while the good-suffix tables track pattern occurrences and prefix-suffix matches.

Bad Character Rule

  • The bad-character table τ maps each alphabet character to its rightmost occurrence in the pattern, or 0 if absent.At a mismatch at pattern position j against lookup character c, the shift is max(1, j − τ[c]).Source: §A.1 · p. 15

Good Suffix Rule

  • For a matched suffix p[j + 1..m], L[j + 1] records the rightmost occurrence's start in the unmatched prefix, when one exists.The occurrence must match the suffix across the corresponding pattern positions.Source: §A.1 · p. 15
  • The table ℓ at position j + 1 stores the longest pattern prefix that is also a suffix of p[j + 1..m].The supplied shift rule uses j + 1 − L[j + 1] when L[j + 1] > 0.Source: §A.1 · p. 15

A.2 Summary of classical Boyer–Moore Variants

Classical Boyer–Moore variants are grouped by how they compute a shift. Bad-character-only methods differ in which text letters they inspect, while full Boyer–Moore combines bad-character and good-suffix rules.

Bad-character-only variants

  • Single-character variants inspect one letter: the window's last letter for Horspool, Raita, and Tuned BM, or the first letter past it for Sunday.Raita and Tuned BM also apply cheap tests on the window before scanning; Smith takes the larger of Horspool's and Sunday's shifts.Source: §A.2 · p. 15
  • Zhu–Takaoka looks up the last two letters of the window, while Berry–Ravindran looks up the two letters past it, using a table of size σ^2.Pair lookups can produce larger shifts than single-character lookups.Source: §A.2 · p. 16

Full Boyer–Moore

  • Full Boyer–Moore combines a bad-character rule with a good-suffix rule, using both the mismatching letter and the matched suffix.Table 1 summarizes the classical variants by their shift-computation approach.Source: §A.2 · pp. 15–16, Table 1 · p. 16

A.3 Fast_BM_Indet Algorithm

Fast_BM_Indet replaces BM_Indet's per-alignment good-suffix recomputation with Fast_GSR_Indet_Shift and pairs it with one of four new bad-character rules. The algorithm records solid positions in the matched suffix to supply the new procedure.

Fast_BM_Indet algorithm

  • Fast_BM_Indet replaces BM_Indet's indet_gsr_shift, which rebuilds a prefix array at each indeterminate alignment, with Fast_GSR_Indet_Shift.It also substitutes one of BC Rules I–IV for BM_Indet's bad-character shift; the other steps remain unchanged.Source: §A.3 · p. 16
  • During the right-to-left scan, the algorithm records j1 and j2, the first and last solid positions of the matched suffix, for the good-suffix procedure.This recording costs O(1) per position and does not add to the algorithm's complexity.Source: §A.3 · pp. 16–17
  • At a mismatch or after a full match, the algorithm shifts by the maximum of the applicable bad-character and good-suffix shifts.For indeterminate patterns or when the matched text suffix is indeterminate, it calls Fast_GSR_Indet_Shift; otherwise it uses the classical good-suffix shift.Source: §A.3 · p. 17
Loading 2609.27170v1…