Bitap Algorithm, in depth: Shift-And state words, a hand trace, k-error matching and where it breaks

The problem: exact and approximate matching

The task: given a pattern p of length m and a text t of length n, report every position where p occurs in t, or where something within k edits of p occurs. An edit is one substitution, one inserted character or one deleted character, the Levenshtein model.

The naive method compares p against every alignment and costs O(nm). Knuth-Morris-Pratt builds a deterministic automaton that never re-reads a character and runs in O(n + m), but its automaton is built around exact matching; making it tolerate errors blows up the number of states. Dynamic programming (Sellers' algorithm) handles errors directly with an m-row column of edit distances per text character, costing O(nm) again. Bitap sits between them: it simulates a nondeterministic automaton, where many states can be active at once, and it represents the set of active states as bits so the whole set moves in O(1) word operations as long as m fits in a word.

Every prefix in one word

Think of the pattern's prefixes. After reading text position j, define bit i of the state word R to be 1 exactly when the prefix p[0..i] ends at position j, that is, when the last i + 1 characters of the text read so far equal the first i + 1 characters of the pattern. If bit m - 1 is 1, the whole pattern ends at j and a match starts at j - m + 1.

Now ask how bit i can become true when character c arrives. Prefix p[0..i] ends at j only if prefix p[0..i-1] ended at j - 1 and p[i] equals c. For i = 0 there is no earlier prefix; the empty prefix always matches, so bit 0 depends only on whether p[0] equals c. That gives the whole algorithm:

• Shift R left by one, so the bit for prefix i - 1 moves into position i (prefix i is now a candidate).
• OR in 1 at bit 0, because a new match attempt can start at every position.
• AND with a precomputed mask B[c] whose bit i is 1 exactly when p[i] equals c, killing every candidate whose next pattern character is not c.

The mask table is built once in O(m + sigma) for an alphabet of size sigma; characters not in the pattern map to 0, which clears every candidate. The update is R = ((R << 1) | 1) & B[c]. Every partial match advances or dies in the same three instructions. That is the bit-parallelism the whole family is built on.

Worked trace: abab in aababab

Search for p = abab in t = aababab. The masks, written with bit 0 on the left so they read in pattern order, are B[a] = 1010 (positions 0 and 2 hold a) and B[b] = 0101. Start with R = 0000.

Overlapping occurrences need no special handling, unlike KMP's failure function; Bitap never forgets a live prefix, and the cost per character is the same whether one prefix or all m are alive.

Shift-Or and the word-size limit

The original paper uses the complement, Shift-Or: 0 means alive and 1 means dead. Masks are inverted (bit i is 0 when p[i] equals c) and the update becomes R = (R << 1) | B[c]. Shifting a 0 into bit 0 seeds the new attempt for free, which saves the OR with 1. A match is a 0 in bit m - 1. The saving is one instruction; pick one convention and use it everywhere. This page uses Shift-And.

The real constraint is word size. One word holds w bits, so a single-word implementation supports m up to w: 64 on mainstream CPUs, or wider with SIMD registers. Python's integers are arbitrary precision, so a Python Bitap silently keeps working for long patterns but each shift becomes a multi-word operation and the constant-time claim no longer holds. For patterns longer than w you either chain words and carry the top bit between them, which makes the cost O(n * ceil(m / w)), or filter with a short piece of the pattern and verify candidates with something else.

Allowing k errors

For approximate matching, keep k + 1 state words. R_d has bit i set when p[0..i] ends at the current position with at most d edits. R_0 is the exact-match word from before. For d of 1 or more, a prefix can reach the current position with at most d edits in four ways, and the new R_d is their OR:

• Match: it extended an R_d prefix with a matching character, ((R_d_old << 1) | 1) & B[c].
• Substitution: it extended an R_(d-1) prefix with any character, spending one edit, (R_(d-1)_old << 1) | 1.
• Deletion from the pattern: it skips pattern character i without consuming text, using the new value of the row below, (R_(d-1)_new << 1) | 1.
• Insertion into the text: it consumes c without advancing in the pattern, R_(d-1)_old.

Initialise R_d with its low d bits set, since the first d pattern characters can be deleted before any text is read. Report a match at the smallest d whose bit m - 1 is set. The cost per character is O(k) word operations, so the total is O(kn) for patterns that fit in a word, against O(mn) for the dynamic programming baseline. The code below was checked against Sellers' DP on thousands of random inputs.

Implementation

A reference implementation in Python, with the exact case falling out as k = 0:

def build_masks(pattern):
    masks = {}
    for i, ch in enumerate(pattern):
        masks[ch] = masks.get(ch, 0) | (1 << i)
    return masks

def bitap(pattern, text, k=0):
    """Yield (end_index, errors) for every text position where some
    substring ending there is within k edits of pattern."""
    m = len(pattern)
    if m == 0:
        raise ValueError("empty pattern")
    masks = build_masks(pattern)
    hit = 1 << (m - 1)
    full = (1 << m) - 1                    # keep words m bits wide
    R = [(1 << d) - 1 for d in range(k + 1)]
    for j, ch in enumerate(text):
        b = masks.get(ch, 0)
        prev_old = R[0]                    # R_(d-1) before this step
        R[0] = ((R[0] << 1) | 1) & b
        for d in range(1, k + 1):
            cur_old = R[d]
            R[d] = (((cur_old << 1) | 1) & b    # match
                    | ((prev_old << 1) | 1)     # substitution
                    | ((R[d - 1] << 1) | 1)     # deletion (uses new row)
                    | prev_old) & full          # insertion
            prev_old = cur_old
        for d in range(k + 1):
            if R[d] & hit:
                yield j, d
                break

print(list(bitap("abab", "aababab")))          # [(4, 0), (6, 0)]
print(list(bitap("match", "a mtch, a matsh", 1)))  # [(5, 1), (14, 1)]

The second call finds mtch (one deletion) ending at index 5 and matsh (one substitution) ending at index 14. Note that the function reports end positions. A k-error match has no single start position, because insertions and deletions change its length; if you need the span, run the same automaton backwards from the end over the reversed pattern, or run a small DP over the window of length m + k ending there.

As a C sketch (declarations and reporting omitted), the inner loop for a 64-bit pattern is a handful of instructions per error level, with the mask table as a 256-entry array for byte alphabets:

uint64_t B[256] = {0}, R[K + 1];
for (int i = 0; i < m; i++) B[(uint8_t)p[i]] |= 1ULL << i;
for (int d = 0; d <= K; d++) R[d] = (1ULL << d) - 1;
uint64_t hit = 1ULL << (m - 1);
for (size_t j = 0; j < n; j++) {
    uint64_t b = B[(uint8_t)t[j]], prev = R[0];
    R[0] = ((R[0] << 1) | 1) & b;
    for (int d = 1; d <= K; d++) {
        uint64_t cur = R[d];
        R[d] = (((cur << 1) | 1) & b) | ((prev << 1) | 1)
             | ((R[d - 1] << 1) | 1) | prev;
        prev = cur;
    }
    if (R[K] & hit) report(j);
}

Where Bitap is used and how to extend it

Bitap shines where patterns are short, errors are few and the text streams past once. agrep used it for approximate grep over files. Fuse.js runs a Bitap variant over each searchable field and turns the error count and match location into a relevance score. diff-match-patch's match function uses it to locate a patch's context near an expected position even after the document has drifted, weighting errors against distance from that position.

Character classes are free: to let pattern position i accept any digit, set bit i in the mask of every digit. Case-insensitive search sets the bit in both cases' masks. None of this changes the inner loop. For many patterns at once, Rabin-Karp hashing or an Aho-Corasick automaton is usually the better tool; for repeated queries over a fixed large text, index it first with a suffix array.

Failure modes

The bugs that show up in real Bitap code are mostly bookkeeping:

• Pattern longer than the word. In C, shifting a 64-bit word by 64 or more is undefined behaviour, and a pattern of length 65 silently loses its top bit so it never matches. Check m against w and fail loudly or switch to a multi-word version.
• Unbounded growth in big-integer languages. Without the & full mask, Python state words grow by one bit per character and a long stream turns each step into an O(n) operation. The search still returns correct results while getting slower and slower.
• Using the new row where the old one is required. Substitution and insertion read R_(d-1) from before the step; deletion reads it after. Swap them and the code matches a different, wrong error model. Test against a brute-force edit-distance DP on random small inputs, as the reference code above was.
• k close to m. When k is at least m, every position matches, because you can delete the whole pattern. Fuzzy search with k = 2 on a three-letter query returns noise. Cap k relative to m, for example one error per four or five characters.
• Unicode. A byte-indexed mask table on UTF-8 text treats a multi-byte character as several characters, so one accented-letter typo costs two or three edits. Decode to code points and use a hash map for masks.

Trade-offs against other matchers

Myers' 1999 bit-vector algorithm is the natural next step when k grows: it encodes the DP column's vertical differences in bit vectors, so its cost does not depend on k at all. Bitap's advantage is simplicity and the ease of adding character classes.

What to do next

• Implement the exact Shift-And loop and reproduce the abab trace above by printing R at every step.
• Add the k-error rows and test them against a brute-force edit-distance DP on random strings over a two-letter alphabet, where bugs show up fastest.
• Decide your alphabet handling up front: case folding, Unicode normalisation and code points versus bytes.
• Enforce m <= 64, or whatever your word width is, and choose a fallback for longer patterns.
• Cap k as a fraction of pattern length so short queries do not match everything.
• If you need k-independent cost, read up on Myers' bit-vector algorithm next.