4 ms·
I have always implemented the horspool algorithm instead. It is simpler to implement and generally performs just as good. When researching string search algori
by bjoli 6y ago
I have always implemented the horspool algorithm instead. It is simpler to implement and generally performs just as good.
When researching string search algorithms some time ago I came across max shift Boyer moore which seemed to be a very nice incremental improvement.
- dataflow 6y agoI've actually found Boost's Boyer-Moore-Horspool to be faster than its Boyer-Moore.
- bjoli 6y agoFor long needles it is, I agree. I am just too lazy to have a good heuristics between a naive search (which is surprisingly fast on modern hardware) and the horspool. With whatever implementations I have implemented have a sweet spot between naive and horspool wher BM is actually sliiightly faster. I think it is just that Horspool works better on modern hardware. BM isn't nearly as much of a gain over the naive search that it was 25 years ago. Edit: the max shift change I mentioned above can be done to Horspool as well!
- dataflow 6y agoOh I actually meant for (super) shorter needles. I'm not sure if this is a general statement or if it's just applicable to the Boost implementation though. And yeah I should really try out the max shift change, I came across it not too long ago but never got around to implementing it.
- MattPalmer1086 6y agoI find Horspool is almost always faster than Boyer Moore. For very short needles though (e.g. less than 8) it is hard to beat the SHIFT OR algorithm. Even though it is not sublinear, looking at every position, it tracks matches using a bitmask. In practice this is very fast and has very good cache hits. It easily beats BM or Horspool by quite a margin. They rely for speed in skips, and you don't get great skips with a short needle.
- ufo 6y agoOn the topic of string research, one excellent reference that someone recommended to me is the book "Flexible Pattern Matching in Strings" by Navarro and Raffinot. One of my favorite things about it is that it has a "phase change" graph at the end of each chapter, saying for each combination of alphabet size and pattern size, which algorithm fares better. It also favors algorithms that are simple to implement (such as Horspool instead of Boyer-Moore), because those also tend to be the fastest.
- MattPalmer1086 6y agoIt is indeed an excellent book, marrying theory with an eye for implementation and real world trade offs.