// HACKER NEWS — CYBERSECURITY
Bitap: My favorite string matching algorithm
A classic problem is to find the first occurrence of a pattern $P$ in a string $T$. There are various classic algorithms to solve this problem efficiently, such as Boyer-Moore, Knuth-Morris-Pratt, and Two-Way. In this post I want to provide an exposition of a less well-known algorithm, the bitap or shift-and algorithm1, that runs efficiently when the pattern $P$ is relatively short (of length less than the width of a machine word.) Despite its constraints, I like it a lot because it is simple both to understand and to implement, relatively efficient for short strings, and uses bit operations in a particularly elegant fashion.
To show that the algorithm is as simple conceptually as claimed, let me try to derive it incrementally starting from the most naive string matching algorithm.
The simplest brute-force algorithm to solve the string matching problem just tries to match the pattern $P$ starting from each possible position in the string $T$.
Let’s now impose an additional constraint to motivate us to change the algorithm a little: instead of being given all the characters of the text $T$ at once, suppose that they are now provided in the form of a stream, one character at a time. (Perhaps $T$ is very long and we do not wish to load all its contents into memory at once.)
The simple algorithm presented above is not streaming: it needs to read up to $m = \texttt{len}(P)$ characters ahead starting from the current position in $T$ to detect a match of the pattern. How can we adapt it so that it only performs one pass through the data?
After a bit of thought, one comes up with the following variant of the brute-force algorithm. Instead of immediately trying to detect an occurrence of $P$ by reading ahead in the text $T$ starting from each start position $i = 0, \dots$, we can instead maintain a set of in-progress matches as we scan through the text $T$. Conceptually, an in-progress match consists of the prefix of the pattern $P$ that has already been matched just before the current position, along with the remaining suffix that has not been matched yet. When we read a new character $c$ in $T$, we advance the in-progress matches that are expecting the character $c$, and kill the rest. If any of the active matches progress to the end of the pattern $P$, we are done.
We can optimize matchOnepass a little by representing an in-progress match state by the index $j$ of the next character to match in the pattern $P$. (The suffix of $P$ yet to be matched then corresponds to P[j:].) This simplifcation yields
How can we improve this algorithm further? One observation we can make is that the in-progress states in active are now always integers between 0 and len(P), the length of the pattern. If $P$ is not too long, there may be a more efficient way to represent the active set instead of a list of integers. This idea is what leads us to our next modification, using bitsets and bit manipulation, from which the bitap algorithm arises.
Indeed, if $P$ is relatively short, say len(P) < 64, then we can pack the set of active states into a single integer (understood as a 64-bit bitset.) So, for instance, if active = {1, 2, 7}, then
Hm. That doesn’t seem like a major improvement. Although it is nice that active has a more compact encoding, there are still two nested loops, begging the question to whether we can eliminate the inner loop somehow…