GoKawiilA 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 algorithm, 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.
Deriving bitap#
The naive 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$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 // Returns the first index i such that T[i:] starts with the pattern P, // or -1 if no such index occurs. // // The pattern P is required to be nonempty. func match ( T , P string ) int { outer : // starting from each position i = 0, ... in the string T... for i := range len ( T ) - len ( P ) + 1 { // try to match the pattern P, one character at a time... for j := range len ( P ) { // moving onto the next start position if a mismatch occurs. if T [ i + j ] != P [ j ] { continue outer } } return i } return - 1 }
The naive algorithm, but make it streaming#
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.
... continue reading