3 ms·
The Boyer–Moore algorithm is very well known. It's in the standard library of many languages such as C++: https://en.cppreference.com/w/cpp/utility/functional/b
by kccqzy 6y ago
The Boyer–Moore algorithm is very well known. It's in the standard library of many languages such as C++: https://en.cppreference.com/w/cpp/utility/functional/boyer_moore_searcher https://en.cppreference.com/w/cpp/utility/functional/boyer_m...
But TIL after reading this page that there's a new variation optimized for small alphabets such as DNA: https://www.cs.utexas.edu/users/moore/publications/sustik-moore.pdf https://www.cs.utexas.edu/users/moore/publications/sustik-mo...
- js2 6y agoI know the algorithm is well known, but I never really knew how it worked other than very hand wavy. This page also links to a demonstration of how the search works which I found easier to follow than the wiki page on the algorithm.
- MattPalmer1086 6y agoThere's a lot of different approaches to searching small alphabets. The one you linked to maintains state during the search loop to get bigger shifts, and complexity in search loops always slows it down, sometimes to the point there is a net loss. If the needle was reasonably long, which is not uncommon for low alphabet needles, I suspect a better approach would be to use a hash based Horspool style algorithm working on n-grams, say 4. This works by calculating shifts based on ngrams, rather than individual bytes. Since there are many more permutations, you effectively increase the alphabet and hence the shifts also increase. At the cost of always having to read an entire ngram before you can shift. Edit: you also hash the ngram into a smaller hash table of course, you don't maintain a shift position for each ngram. You can tune the size of the hash table for lower memory or higher performance. This is similar to the multi pattern Wu Manber search, but applied to a single needle. Edit 2: I have found this algorithm also beats Horspool most of the time, say for an ngram size of 2 or 3, on any alphabet, not just low ones.