Home arrow Development Cycles arrow More Pattern Matching Algorithms: B-M
DEVELOPMENT CYCLES

More Pattern Matching Algorithms: B-M


This is the second and final half of our two-part series on pattern matching, or string searching algorithms. In the first part, we covered the Knuth-Morris-Pratt (KMP) algorithm and in this segment, were going to present a new algorithm that originates from Boyer-Moore. It is currently considered the most efficient and practical algorithm, serving as a benchmark standard.

Author Info:
By: Barzan "Tony" Antal
Rating: 4 stars4 stars4 stars4 stars4 stars / 7
August 05, 2008
TABLE OF CONTENTS:
  1. · More Pattern Matching Algorithms: B-M
  2. · The Theory
  3. · Implementation
  4. · Final Words

print this article
SEARCH DEVARTICLES

More Pattern Matching Algorithms: B-M
(Page 1 of 4 )

Before we begin, Id like to suggest reading the first part of this series. You can find it published here on Dev Articles. It contains much of what you should know in order to fully grasp the new methodology of the Boyer-Moore exact pattern matching algorithm. This article will also follow the same scheme as the first one. Well start with the theory first.

It all started back in 1977, when Bob Boyer and J. Strother Moore published their work. You can find the scanned copy of the original published abstract here; kudos to the Univ. of Texas (host). This algorithm surprised most people at that time because it approached the theory of string searching differently in that it works backwards, from right to left. And unlike some other algorithms, it preprocesses the pattern, not the source.

Its preprocessing time is Θ(m + |Σ|) in complexity and its matching time is Ω(n / m) (best performance) or O(n) (worst). It performs 3n text comparisons on worst case. Worst case is limited only to non-periodic patterns. For a detailed overview of the asymptotic growth of functions and computational complexity theory, please check out this course from Jack Baskin School of Engineering, UC Santa Cruz.

The efficiency of this algorithm lies in the fact that it does not inspect the source string (in which we are searching for a pattern) in its entirety. The preprocessing phase analyzes the pattern and by using a heuristic approach, it is able to reduce the number of comparisons altogether. The longer the pattern becomes, the fewer comparisons are to be done. Using the preprocessed table(s), the algorithm performs large jumps, which saves time.

Compared to the Knuth-Morris-Pratt pattern matching algorithm, which we all know is a linear algorithm, Boyer-Moores variation is sub-linear. Usually, that is. This is mathematically proven in their official publication. Knuth also pointed out that the Boyer-Moore algorithm becomes linear in worst case. As a result, if it's efficiently implemented, it gives the best overall results considering complexity and resources.

Lets begin with the theory part first.


blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials