Bitap: my favorite string matching algorithm

# Bitap: my favorite string matching algorithm Source: [https://jo3-l.dev/posts/bitap/](https://jo3-l.dev/posts/bitap/) A classic problem is to find the first occurrence of a pattern $P$ in a string $T$\. There are various classic \(and very elegant\!\) algorithms to solve this problem efficiently, such as[Boyer\-Moore](https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm),[Knuth\-Morris\-Pratt](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm), and[two\-way](https://en.wikipedia.org/wiki/Two-way_string-matching_algorithm)\. In this post I want to provide an exposition of a less well\-known algorithm, the*bitap*or*shift\-and*algorithm[1](https://jo3-l.dev/posts/bitap/#fn:1), 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 very 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 on ourselves 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\. ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ``` ``` func matchOnepass(T, P string) int { type state struct { remaining string // suffix of P yet to be matched } var active []state for i := range len(T) { c := T[i] // Always attempt to start a new match. active = append(active, state{remaining: P}) var next []state for _, m := range active { if c == m.remaining[0] { // Advance this in-progress match by one position. remaining := m.remaining[1:] if remaining == "" { // Matched all of P, with the final character appearing at position i. // The first character appears |P| - 1 units to the left. return i - len(P) + 1 } next = append(next, state{remaining}) } } active = next } return -1 } ``` 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 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ``` ``` func matchOnepassInt(T, P string) int { var active []int // state is now an int for i := range len(T) { c := T[i] active = append(active, 0) // attempt to start a new match var next []int for _, j := range active { if c == P[j] { // advance j++ if j == len(P) { // matched all of P return i - len(P) + 1 } next = append(next, j) } } active = next } return -1 } ``` 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 \(implying $m$ is small\), 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\. ### Bit manipulation 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 ``` active_bitset = 0b1000_0110 ``` Let’s try this\! ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ``` ``` func matchOnepassBitset(T, P string) int { var active uint64 // bitset for i := range len(T) { c := T[i] active |= 1 << 0 // add 0 to the bitset (attempt to start a new match) var next uint64 for j := range 64 { if active&(1<<j) == 0 { continue } // for each state j in the active set... if c == P[j] { // advance j++ if j == len(P) { // matched all of P return i - len(P) + 1 } next |= 1 << j } } active = next } return -1 } ``` 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… It turns out that we indeed can, using some clever bit manipulation and a small change in perspective\. Observe that, in the above algorithm, we look at each match state, checking if it can continue \(by comparing`c`with`P\[j\]`\), and then advance by one position if so\. On the other hand, an alternative approach is to unconditionally advance*all*match states by one position, and then kill any states that arose from an invalid transition\. The key is that, unlike the previous approach, both of these steps can be implemented in a single bit operation operating on the entire bitset at once\. Indeed, to advance all match states by one position, it suffices to shift left by one:`active << 1`\. The only challenge that remains is to kill off states arising from an invalid transition: in other words, given`next = active << 1`, we want to only keep the states that should really have advanced after observing the character`c`\. The second and final insight is that we can accomplish this by precomputing a bitset of valid states that can arise after observing the character`c`for each character that appears in the pattern, and then intersecting with the appropriate bitset\. ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ``` ``` func matchBitap(T, P string) int { var validMask [256]uint64 // table of bitmasks, indexed by byte for j := range len(P) { // If we see c, then we are permitted to advance to state j+1 (assuming we were at state j before.) c := P[j] validMask[c] |= 1 << (j + 1) } var active uint64 for i := range len(T) { c := T[i] active |= 1 << 0 // attempt to start a new match next := (active << 1) & validMask[c] // advance states and mask off invalid transitions if next&(1<<len(P)) != 0 { // matched all of P! return i - len(P) + 1 } active = next } return -1 } ``` At last, we have arrived at the the*shift\-and*or*bitap*algorithm \(named since it shifts`<< 1`, then ands`& validMask\[c\]`\)\! I remark that the typical presentation has a slightly different index convention shifted by one, which is more appropriate in practice, but the spirit is the same and my convention allows for this blog to flow a bit more naturally\. There is also a more efficient variant*shift\-or*that inverts all the bit masks and uses bit\-OR instead of bit\-AND, which performs one less bit operation per input character\. ## So what? As mentioned at the start, the bitap algorithm only really shines when the pattern is relatively short: though it can theoretically be generalized to longer patterns \(by using multi\-word bitsets\), the performance gains start diminishing\. Asymptotically, when the length of the pattern is bounded by a constant, the runtime of bitap is identical to that of the naive brute\-force algorithm \(both are linear in the length of the text $T$\.\) Practically, it may even perform worse in a one\-off test due to the precomputation required\. In view of these limitations, why do I like bitap at all? I think that it is conceptually very elegant and simple to derive from the naive algorithm–as described above, it simply maintains a set of active states as it steps through the input string, using bit operations to go fast\. Though I’ve also studied Boyer\-Moore and KMP in detail, it takes me quite some time to derive them from scratch[2](https://jo3-l.dev/posts/bitap/#fn:2), whereas bitap is very easily derived, since to me it is just the naive algorithm dressed up differently\. It is my hope that you feel the same way after this blog post\.