↩ back to Approximate Match

Bitap (Shift-And) String Matching

KMP, Aho-Corasick, and Rabin-Karp all answer the same question — does the pattern occur in the text, exactly — with three different mechanisms: a failure-function table, a failure-function trie, and a rolling hash. Bitap (also called Shift-And or Shift-Or) answers it with a fourth mechanism entirely: pack "which prefixes of the pattern could be mid-match right now" into the bits of a single machine word, and advance the whole word one shift, one AND, and one OR per text character — no explicit pointer into the pattern, no per-character loop over prefix lengths, just word-sized bit operations. That reframing turns out to matter beyond speed: because "prefix p is mid-match" is just a bit, it's cheap to keep several such words side by side, one per number of mistakes tolerated so far, and get typo-tolerant — approximate — matching almost for free. None of the three exact-match algorithms above extend this way without a fundamentally different structure.

Try it

Enter a text and a pattern (up to 40 and 10 characters), and choose how many substitution errors to tolerate, k. The default — "cat cot bat mad cot" searched for "cat" with k = 2 — is a real spread, not a cherry-picked edge case: cat matches exactly, cot and bat each match with one substituted letter, mad matches only once two substitutions are allowed, and no other 3-character window (including ones spanning a space) is close enough to qualify at any of these levels. Step through and watch every R row update together, one text character at a time.

Why it works

For a pattern of length m, build one bitmask per character of the alphabet: bit p−1 of mask[c] is set if pattern[p−1] == c. Then maintain a state word R where bit p−1 means "the pattern's first p characters match the text ending exactly at the current position." Each new text character updates every bit at once:

R = ((R << 1) | 1) & mask[text[i]]

Shifting left and OR-ing in a 1 says "a fresh length-1 match could start here"; every existing bit also slides up to mean "one character longer than before." AND-ing with the current character's mask keeps only the bits whose corresponding pattern position actually matches — everything else is zeroed in one operation, regardless of how long the pattern is. When bit m−1 comes on, the whole pattern just matched ending at this position. This is exact matching — equivalent to what KMP computes with a failure-function table, but with the "which prefixes are alive" bookkeeping packed into a single word instead of an explicit index.

Approximate matching keeps k + 1 such words, R⁰ through Rk, one per error budget. R⁰ is the exact-match word above. Each higher level adds a second way to extend a match — spend one of its errors to accept any character as a substitution, sourced from the level below:

R[j] = ( ((R[j] << 1) | 1) & mask[text[i]] )   // extend with 0 more errors, char must match
     | ( (R[j-1] << 1) | 1 )                   // extend with 1 more error, any char accepted

Because every level's bits are a superset of the level below's (anything reachable with j−1 errors is trivially reachable with j), it's always safe to report the smallest j whose bit m−1 is set as the true number of errors — which is exactly what the demo's match list does.

Reference implementation

This is the exact scheme the demo above steps through, generalized to substitution-only approximate matching:

function buildMasks(pat) {
  const mask = {};
  for (let p = 0; p < pat.length; p++) {
    const c = pat[p];
    mask[c] = (mask[c] || 0) | (1 << p);
  }
  return mask;
}

function bitapSearch(text, pat, k) {
  const m = pat.length;
  const mask = buildMasks(pat);
  const finalBit = 1 << (m - 1);
  let R = new Array(k + 1).fill(0);
  const matches = [];                         // {pos, errors}
  for (let i = 0; i < text.length; i++) {
    const charMask = mask[text[i]] || 0;
    const prev = R.slice();
    const next = [((prev[0] << 1) | 1) & charMask];
    for (let j = 1; j <= k; j++) {
      next.push((((prev[j] << 1) | 1) & charMask) | ((prev[j - 1] << 1) | 1));
    }
    R = next;
    for (let j = 0; j <= k; j++) {
      if (R[j] & finalBit) { matches.push({ pos: i - m + 1, errors: j }); break; }  // smallest j wins
    }
  }
  return matches;
}

Pitfalls

This variant only tolerates substitutions, not insertions or deletions. Every window bitap-with-substitutions compares is exactly m characters long, aligned one-to-one against the pattern — the demo's "mad" match works because it's the same length as "cat", just two letters off. A typo that inserts or drops a character (like searching for "cat" and expecting "caat" or "ct" to match) shifts every following character's alignment by one, and this recurrence has no mechanism for that — it would report those as unrelated to the pattern, at any k. Real fuzzy-search tools (agrep, and the algorithm generally credited to Wu and Manber) extend the same bit-parallel idea to true edit distance by tracking how R[j] derives from three neighbors instead of two — the substitution term above, plus a deletion term and an insertion term. See Bitap with Edit Distance (Wu–Manber) for that fourth mechanism, built out in full.

The whole state has to fit in one machine word, or the "one shift, one AND, one OR" cost stops being O(1). JavaScript's bitwise operators work on 32-bit integers, so this page's 1 << (m - 1) starts misbehaving once m exceeds 31 — which is why the demo caps the pattern at 10 characters, well under that ceiling, not because the algorithm itself has a small-pattern limit. A real implementation handles longer patterns by splitting R across ⌈m / w⌉ words (w = machine word width, typically 32 or 64) and paying that many times the per-character work — still bit-parallel, just no longer a single instruction per level.

Every error level has to be checked, and higher levels are strictly more expensive to reason about, not free. Try lowering k to 1 in the demo above and reloading: "mad" stops being reported (it genuinely needs 2 substitutions), while "cat", "cot", and "bat" still are — a real, checked demonstration that raising k only ever adds matches, never removes or changes existing ones, which is exactly the nesting property (R⁰'s bits are a subset of R¹'s, which are a subset of R²'s, and so on) the "report the smallest j" logic above depends on. But each extra level is another full word of state updated every character, so choosing k is a real cost/tolerance tradeoff, not a free dial — unlike Rabin-Karp's modulus, which only affects how often verification runs, not the shape of the main loop.

Complexity

Time: O(n) for exact matching (k = 0) when the pattern fits in one machine word — every text character costs one shift, one AND, one OR, regardless of m, which is a real advantage over KMP's unconditional but still per-character-comparison O(n + m). Approximate matching with up to k substitutions costs O(n · k) — one word-update per level per text character. If the pattern is longer than the machine word width w, both bounds pick up a further ⌈m / w⌉ factor, since R no longer fits in a single word. Space: O(σ) for the character masks (σ = alphabet size, capped at the number of distinct characters actually in the pattern) plus O(k) words for the R levels — independent of the text length either way.

A sixth entry, Jaro-Winkler Similarity, tackles a different flavor of approximate matching: instead of sliding a fixed pattern across a longer text looking for near-hits, it scores how alike two whole strings are, which is the shape a name or a short record actually needs, not a substring search. For a side-by-side comparison across all eleven approximate-match entries, see Choosing an Approximate String Matcher.