Information AboutBitap Algorithm |
| CATEGORIES ABOUT BITAP ALGORITHM | |
| algorithms on strings | |
| search algorithms | |
| articles with example c code | |
|
The bitap algorithm is perhaps best known as one of the underlying algorithms of the Unix Utility Agrep , written by Manber, Wu, and Burra Gopal . Manber and Wu's original paper gives extensions of the algorithm to deal with fuzzy matching of general Regular Expression s. Due to the data structures required by the algorithm, it performs best on patterns less than a constant length (typically the Word Length of the machine in question), and also prefers inputs over a small alphabet. Once it has been implemented for a given alphabet and word length ''m'', however, its Running Time is completely predictable — it runs in O (''mn'') operations, no matter the structure of the text or the pattern. This algorithm was improved by Baeza-Yates and Navarro in 1996 and later by Gene Myers for long patterns in 1998. EXACT SEARCHING The bitap algorithm for exact String Searching , in full generality, looks like this when implemented in C : |
|
|