Boyer–Moore string search algorithm

BOYER–MOORE STRING SEARCH ALGORITHM SeyedHamid Shekarforoush Bowling Green State University

SEARCHING A SPECIFIC PATTERN IN A TARGET TEXT THE NAÏVE METHOD G T T T A C G G T C T T C T T G G C C G A T T A # comparisons 0 C G A T

BOYER–MOORE STRING SEARCH ALGORITHM  developed by Robert S. Boyer and J Strother Moore in 1977  Smart naïve method  tries to match the pattern with target text  Use two rules to skip unnecessary matches  Match from the end of pattern

FIRST RULE: THE BAD CHARACTER RULE (BCR)  Text : bowling green state university computer science department  Pattern : science Letter s c i e n * BCR 6 1 4 1 2 7

FIRST RULE: THE BAD CHARACTER RULE (BCR) B OW L I NG G R E E N S T A T E U N I V E R S I T Y C OMP U T E R S C I E N C E Letter s c i e n * BCR 6 1 4 1 2 7 S C I E N C E

FIRST RULE: THE BAD CHARACTER RULE (BCR) B OW L I NG G R E E N S T A T E U N I V E R S I T Y C OMP U T E R S C I E N C E Letter s c i e n * BCR 6 1 4 1 2 7 S C I E N C E 7 shifts

FIRST RULE: THE BAD CHARACTER RULE (BCR) B OW L I NG G R E E N S T A T E U N I V E R S I T Y C OMP U T E R S C I E N C E Letter s c i e n * BCR 6 1 4 1 2 7 S C I E N C E 4 shifts

FIRST RULE: THE BAD CHARACTER RULE (BCR) B OW L I NG G R E E N S T A T E U N I V E R S I T Y C OMP U T E R S C I E N C E Letter s c i e n * BCR 6 1 4 1 2 7 S C I E N C E1 shifts

BUILDING BCR TABLE • Length – index – 1 • The BCR value can’t be less than 1 • If we have repeated letters we count the minimum BCR value, because it should be the rightmost occurrence of the letter • We use symbol “*” for any other letter that is not in the pattern and the BC value is the length of the pattern, because we can skip the whole pattern knowing that character “*” is not in the pattern.

BUILDING BCR TABLE • Length – index – 1 • Length = 7 index 0 1 2 3 4 5 6 7 pattern s c i e n c e * BCR 6 5 4 3 2 1 0>>>1 7 •Length – index – 1 •7-0-1 =6 •The BCR value can’t be less than 1 •Why?

BUILDING BCR TABLE • Length – index – 1 • Length = 7 index 0 1 2 3 4 5 6 7 pattern s c i e n c e * BCR 6 5 4 3 2 1 0>>>1 7 •Minimum BCR for repeated letters Letter s c i e n * BCR 6 1 4 1 2 7

SECOND RULE: GOOD SUFFIX RULE (GSR)  It used when we have some successful matches  Reusing the already matched string

SECOND RULE: GOOD SUFFIX RULE (GSR) 6 shifts

BOTH RULES TOGETHER  At each step when we get a mismatch and we want to shift, the algorithm use both rules and use the bigger shift

BOTH RULES TOGETHER Letter T C G * BCR 2 3 1 10  BCR = 2 shifts  GSR = 6 shifts

PERFORMANCE  The Boyer–Moore is work faster and better with longer pattern with less repeated characters  Most of the time the BCR win over the GSR  many implementation don’t use the GSR at all Algorithm Preprocessing time Matching time Naïve 0 (no preprocessing) Θ((n−m)m) Rabin–Karp Θ(m) average Θ(n + m), worst Θ((n−m)m) Finite-state Θ(mk) Θ(n) Knuth–Morris–Pratt Θ(m) Θ(n) Boyer–Moore Θ(m + k) best Ω(n/m), worst O(n) Bitap Θ(m + k) O(mn)

REFRENCES  [1] Robert S. Boyer and J. Strother Moore. 1977. A fast string searching algorithm. Commun. ACM 20, 10 (October 1977), 762-772. DOI=http://dx.doi.org/10.1145/359842.359859  [2] Wikipedia contributors, "Boyer–Moore string search algorithm," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/w/index.php?title=Boyer%E2%80%93Moore_string_sear ch_algorithm&oldid=688111014 (accessed November 20, 2015).

Boyer–Moore string search algorithm

More Related Content

What's hot

Viewers also liked

Similar to Boyer–Moore string search algorithm

Recently uploaded

In this document

Boyer–Moore string search algorithm