The bitap algorithm (also known as the shiftor, shiftand or BaezaYatesGonnet algorithm) is a fuzzy string searching algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given pattern, where approximate equality is defined in terms of Levenshtein distance — if the substring and pattern are within a given distance k of each other, then the algorithm considers them equal. The algorithm begins by precomputing a set of bitmasks containing one bit for each element of the pattern. Then it is able to do most of the work with bitwise operations, which are extremely fast.
The bitap algorithm is perhaps best known as one of the underlying algorithms of the Unix utility agrep, written by Udi Manber, Sun Wu, and Burra Gopal. Manber and Wu's original paper gives extensions of the algorithm to deal with fuzzy matching of general regular expressions.
Due to the data structures required by the algorithm, it performs best on patterns less than a constant length (typically the word length of the machine in question), and also prefers inputs over a small alphabet. Once it has been implemented for a given alphabet and word length m, however, its running time is completely predictable — it runs in O(mn) operations, no matter the structure of the text or the pattern.
The bitap algorithm for exact string searching was invented by Balint Dömölki in 1964^{[1]} and extended by R. K. Shyamasundar in 1977^{[2]}, before being reinvented in the context of fuzzy string searching by Manber and Wu in 1991^{[3]}^{[4]} based on work done by Ricardo BaezaYates and Gaston Gonnet^{[5]}. The algorithm was improved by BaezaYates and Navarro in 1996^{[6]} and later by Gene Myers for long patterns in 1998^{[7]}.
The bitap algorithm for exact string searching, in full generality, looks like this when implemented in C:
#include <stdlib.h> #include <string.h> typedef char BIT; /* needs only to hold the values 0 and 1 */ const char *bitap_search(const char *text, const char *pattern) { const char *result = NULL; int m = strlen(pattern); BIT *R; int i, k; if (pattern[0] == '\0') return text; /* Initialize the bit array R */ R = malloc((m+1) * sizeof *R); R[0] = 1; for (k=1; k <= m; ++k) R[k] = 0; for (i=0; text[i] != '\0'; ++i) { /* Update the bit array. */ for (k=m; k >= 1; k) R[k] = R[k1] && (text[i] == pattern[k1]); if (R[m]) { result = (text+i  m) + 1; break; } } free(R); return result; }
Bitap distinguishes itself from other wellknown string
searching algorithms in its natural mapping onto simple bitwise
operations, as in the following modification of the above program.
Notice that in this implementation, counterintuitively, each bit
with value zero indicates a match, and each bit with
value 1 indicates a nonmatch. The same algorithm can be
written with the intuitive semantics for 0 and 1, but in that case
we must introduce another instruction into the inner loop to set R
= 1
. In this implementation, we take advantage of the fact
that leftshifting a value shifts in zeros on the right, which is
precisely the behavior we need.
Notice also that we require CHAR_MAX
additional
bitmasks in order to convert the (text[i] ==
pattern[k1])
condition in the general implementation into
bitwise operations. Therefore, the bitap algorithm performs better
when applied to inputs over smaller alphabets.
#include <string.h> #include <limits.h> const char *bitap_bitwise_search(const char *text, const char *pattern) { int m = strlen(pattern); unsigned long R; unsigned long pattern_mask[CHAR_MAX+1]; int i; if (pattern[0] == '\0') return text; if (m > 31) return "The pattern is too long!"; /* Initialize the bit array R */ R = ~1; /* Initialize the pattern bitmasks */ for (i=0; i <= CHAR_MAX; ++i) pattern_mask[i] = ~0; for (i=0; i < m; ++i) pattern_mask[pattern[i]] &= ~(1UL << i); for (i=0; text[i] != '\0'; ++i) { /* Update the bit array */ R <<= 1; R = pattern_mask[text[i]]; if (0 == (R & (1UL << (m  1)))) return (text + i  m) + 1; } return NULL; }
To perform fuzzy string searching using the bitap algorithm, it is necessary to extend the bit array R into a second dimension. Instead of having a single array R that changes over the length of the text, we now have k distinct arrays R_{1..k}. Array R_{i} holds a representation of the prefixes of pattern that match any suffix of the current string with i or fewer errors. In this context, an "error" may be an insertion, deletion, or substitution; see Levenshtein distance for more information on these operations.
The implementation below performs fuzzy matching (returning the first match with up to k errors) using the fuzzy bitap algorithm. However, it only pays attention to substitutions, not to insertions or deletions  in other words, a Hamming distance of k. As before, the semantics of 0 and 1 are reversed from their intuitive meanings.
#include <stdlib.h> #include <string.h> #include <limits.h> const char *bitap_fuzzy_bitwise_search(const char *text, const char *pattern, int k) { const char *result = NULL; int m = strlen(pattern); unsigned long *R; unsigned long pattern_mask[CHAR_MAX+1]; int i, d; if (pattern[0] == '\0') return text; if (m > 31) return "The pattern is too long!"; /* Initialize the bit array R */ R = malloc((k+1) * sizeof *R); for (i=0; i <= k; ++i) R[i] = ~1; /* Initialize the pattern bitmasks */ for (i=0; i <= CHAR_MAX; ++i) pattern_mask[i] = ~0; for (i=0; i < m; ++i) pattern_mask[pattern[i]] &= ~(1UL << i); for (i=0; text[i] != '\0'; ++i) { /* Update the bit arrays */ unsigned long old_Rd1 = R[0]; R[0] = pattern_mask[text[i]]; R[0] <<= 1; for (d=1; d <= k; ++d) { unsigned long tmp = R[d]; /* Substitution is all we care about */ R[d] = (old_Rd1 & (R[d]  pattern_mask[text[i]])) << 1; old_Rd1 = tmp; } if (0 == (R[k] & (1UL << m))) { result = (text+i  m) + 1; break; } } return result; }
