3 ms·

Any one know why the Turbo Boyer-Moore algorithm is not more popular. Any case when Boyer Moore would be better?

• MattPalmer1086 7y ago
  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/ 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!
  • rurban 7y ago
    Fastest and best is the latest, EPSM. For all cases, given you are on x86_64 or aarch64 with sse4.2 The cited implementation has only minor problems, which I fixed in my fork.
• bjoli 7y ago
  because BM or BM-horspool is generally very good over all and very few algorithms are always better.
• billyoneal 7y ago
  1. What empirical data we have suggests that the 'good suffix' rule engages fairly rarely; that's why the -Horspool variant wins most tests. (It isn't just that you don't have to build Delta2, it also saves a lot of comparisons in the algorithm itself for most inputs.) 2. Because the standard says this is the Boyer-Moore algorithm :D