4 ms·
I'm actually more familiar with the KMP algorithm than BM. So I looked it up to see what the difference was: The classic Boyer-Moore algorithm suffers from the
by yelnatz 13y ago
I'm actually more familiar with the KMP algorithm than BM. So I looked it up to see what the difference was:
The classic Boyer-Moore algorithm suffers from the phenomenon that it tends not to work so efficiently on small alphabets like DNA.
The skip distance tends to stop growing with the pattern length because substrings re-occur frequently.
By remembering more of what has already been matched, one can get larger skips through the text.
One can even arrange 'perfect memory' and thus look at each character at most once, whereas the Boyer-Moore algorithm, while linear, may inspect a character from the text multiple times.
1: http://stackoverflow.com/questions/12656160/what-are-the-main-differences-between-the-knuth-morris-pratt-and-boyer-moore-sea http://stackoverflow.com/questions/12656160/what-are-the-mai...
- ahelwer 13y agoYou would inspect characters multiple times only in a very naive implementation of Boyer-Moore. The Galil Rule[0] fixes this and is also required for proving linear worst-case runtime. [0] https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm#The_Galil_Rule https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_sea...
- lubomir 13y agoThis page [1] nicely demonstrates differences between KMP and BM. [1]: http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/index.html http://www.cs.utexas.edu/users/moore/best-ideas/string-searc...
- mtdewcmu 13y agoI have a book called Flexible Pattern Matching in Strings[1], which covers all the algorithms that might go into a modern, state-of-the-art grep, with practical advice on performance (N.B.: Boyer-Moore is no longer state-of-the-art). The publication year is 2002. [1] http://www.dcc.uchile.cl/~gnavarro/FPMbook/ http://www.dcc.uchile.cl/~gnavarro/FPMbook/
- tetha 13y agoCouldn't you speed up a small-alphabet search by considering pairs or triplets of characters so you have N^2 or N^3 glyphs instead of N characters (so, going from 4 characters to 16 cgaracters to 64 characters)?
- mtdewcmu 13y agoI'm not sure exactly how your proposal might work, but, generally, the problem you would run into is that the group of characters can be shifted. So you'd end up having to compare every possible shift.