Bitap: The String Matching Algorithm That Fits in a Single Word
Bitap: My favorite string matching algorithm
Bitap, or shift-and, finds a pattern in a text by packing active match states into a bitset and updating them with a shift and a mask. It only works when the pattern is shorter than a machine word, but it is simple to derive from the naive algorithm and elegant to implement. The post walks through that derivation step by step.
Though I’ve also studied Boyer-Moore and KMP in detail, it takes me quite some time to derive them from scratch, whereas bitap is very easily derived, since to me it is just the naive algorithm dressed up differently.
- Rendello
I also have a favourite string matching algorithm, the "Generic SIMD" from this post [1] by Wojciech Muła (I haven't really read the other two SIMD algorithms since I wasn't planning on working with intrinsics).
There were some good comments that post's thread [2], including from burntsushi of ripgrep.
- MattPalmer1086
Ah, last weekend I was just updating my own string search algorithm to use Bitap (Shift-OR variant) instead of KMP, when the pattern length is < 64. It is faster. It is a very lovely algorithm indeed.
My search algorithm, HashChain [1] is a very fast sublinear algorithm, but is uses KMP (and now Bitap) to verify matches so it has a linear worst case (instead of quadratic, like Boyer Moore Horspool).
- MattPalmer1086
It is a really nice derivation of Bitap from first principles. I had not seen that before. Good job!
One small nit: he says the naive algorithm is linear - maybe it is for the average case, but it has a quadratic worst case complexity. Bitap is linear even for worst case.