So there is potentially a simpler fix than the Rytter correction, is that also yet to discover in published papers somewhere, or do we need to ask Knuth himself?
Fix Boyer-Moore searcher with the Rytter correction
11–20 of 56 posts
Re: Fix Boyer-Moore searcher with the Rytter correction
#12Nice fix! It's been a while since I've done c++ so does the following code
const auto elapsed = steady_clock::now() - start;
if (elapsed > 10s) {
Re: Fix Boyer-Moore searcher with the Rytter correction
#13What I find most interesting about this bugfix is simply how terrible of a source Wikipedia is and, at the same time, how valuable professional insight can be (e.g. someone that knows what they're talking about). And to add insult to injury, someone quickly edited Wikipedia (for the "street cred" I'm sure): > The original paper contained errors for computing the table of pattern shifts which was corrected by Wojciech…
dude, instead of bitching, fix it
Re: Fix Boyer-Moore searcher with the Rytter correction
#14What is a minimal test case (needle + haystack) for which the old code yields a different result than the new code?
Re: Fix Boyer-Moore searcher with the Rytter correction
#15What is a minimal test case (needle + haystack) for which the old code yields a different result than the new code?
There are a bunch of test cases here:
https://github.com/microsoft/STL/pull/724/commits/a7da5cce8c...
Looks like it can happen with quite small needles, eg. "aa".
Re: Fix Boyer-Moore searcher with the Rytter correction
#16Nice fix! It's been a while since I've done c++ so does the following code const auto elapsed = steady_clock::now() - start; if (elapsed > 10s) { actually use a units quantifier on the 10, i.e. does 10s mean 10 seconds? Is that a library thing? Cool if so.
It’s called user-defined literal suffix in C++11.
https://en.cppreference.com/w/cpp/language/user_literal The “s” suffix come with C++14 https://en.cppreference.com/w/cpp/chrono/operator%22%22s
Re: Fix Boyer-Moore searcher with the Rytter correction
#17Nice fix! It's been a while since I've done c++ so does the following code const auto elapsed = steady_clock::now() - start; if (elapsed > 10s) { actually use a units quantifier on the 10, i.e. does 10s mean 10 seconds? Is that a library thing? Cool if so.
that's a user defined literal, a language feature: https://en.cppreference.com/w/cpp/language/user_literal
the std::chrono library reserved some suffixes (under std::literals::chrono_literals) for time units https://en.cppreference.com/w/cpp/symbol_index/chrono_litera...
Re: Fix Boyer-Moore searcher with the Rytter correction
#18What I find most interesting about this bugfix is simply how terrible of a source Wikipedia is and, at the same time, how valuable professional insight can be (e.g. someone that knows what they're talking about). And to add insult to injury, someone quickly edited Wikipedia (for the "street cred" I'm sure): > The original paper contained errors for computing the table of pattern shifts which was corrected by Wojciech…
dude, instead of bitching, fix it
Downvote what you want, the man is right. Don't complain, fix it. If you're so wise in the way of things please shine a small strip of your diamondlike awareness on us pedestrians by editing the community owned wiki.
Re: Fix Boyer-Moore searcher with the Rytter correction
#19Any one know why the Turbo Boyer-Moore algorithm is not more popular. Any case when Boyer Moore would be better?
There are literally hundreds of string search algorithms published now (including a large number of Boyer Moore variants).
There's a great resource called SMART for those interested in exploring this, with implementations of many of them and a simple benchmarking tool.
https://smart-tool.github.io/smart/
Although Boyer Moore is well known, there are generally faster algorithms available these days.
For short patterns, SHIFTOR will tend to be a lot faster than BM. Even the much simpler variant of BM, Horspool is usually faster than BM.
This highlights an interesting tension in search algorithm design. Often a simpler algorithm outperforms one with theoretically higher performance, but not always!
Re: Fix Boyer-Moore searcher with the Rytter correction
#20I remember Dr Dobbs, way back when, having an article on the search algorithm. I think they had C code for it.
I did a version in 68K on the Mac (MPW Shell days) for a SGML editor I was working on.