↩ back to Approximate Match

Bitap with Edit Distance (Wu–Manber)

Bitap's approximate-matching extension tolerates substitutions — a wrong character in an otherwise same-length window — by keeping one bitmask per error budget. It stops there because every window it checks is locked to exactly m characters, aligned one-to-one against the pattern. Real typos also insert and drop characters, shifting everything after them out of alignment — "cat" vs "ct" (a deletion) or "caat" (an insertion) can't be substitution matches at any error count, because they're the wrong length. The algorithm generally credited to Wu and Manber (the same bit-parallel idea behind agrep) extends the recurrence to true edit distance by tracking two more ways a match can grow: skip a text character (insertion) or skip a pattern character (deletion), each costing one error just like a substitution does. This is the exact same edit set — and the exact same recurrence — as Edit Distance's dynamic-programming table, just packed into bits instead of table cells, and with one changed base case that turns "distance between two whole strings" into "does the pattern occur, approximately, somewhere in this text."

Try it

Enter a text and a pattern (up to 45 and 10 characters), and choose how many errors to tolerate, k — now spent on any mix of substitutions, insertions, and deletions. The default — pattern "kitten" against text "kitten kiten kaitten sitten sittin hamster" — is a real, checked spread: the exact word matches at 0 errors; kiten (missing a t), kaitten (an extra a), and sitten (a substituted first letter) each need exactly 1; sittin needs 2 (two substitutions); and hamster never registers, even at k = 3, confirmed against a from-scratch edit-distance oracle, not assumed. Unlike the substitution-only demo, a match here is reported at a single end position, not a fixed-width window — edit distance doesn't pin down how long the matching substring actually was, so only the last character of each candidate is marked; read the log line underneath for the real extent.

Why it works

Start from the same table Edit Distance builds, but change one base case. There, dp[i][0] = i — turning i characters of the first string into nothing costs i deletes, because the whole first string has to be accounted for. Here, define D[i][j] as the smallest edit distance between the pattern's first j characters and some suffix of the text's first i characters — and matching the empty pattern prefix against nothing costs nothing, from any starting point: D[i][0] = 0 for every i. That single changed cell is what turns "edit distance between two fixed strings" into "search for the pattern anywhere in a longer text." Everything else is the familiar three-way recurrence: if pattern[j-1] == text[i-1], extend a prior match for free, D[i][j] = D[i-1][j-1]; otherwise pay one error for whichever is cheapest — substitute (D[i-1][j-1]), delete from the pattern (D[i][j-1], no text character consumed), or insert an extra text character (D[i-1][j]). A window ending at text position i is a k-error match once D[i][m] ≤ k.

Bit-parallelism packs one row of this table — fixed i, varying j — into a word R, the same reframing Bitap uses: bit j−1 of Rd means D[i][j] ≤ d. Writing shift(x) = ((x << 1) | 1) (slide every bit up one position and set bit 0 — the bit-vector's way of encoding the trivial D[i][0] ≤ d base case at every step), the recurrence becomes four terms instead of two:

R0[i] = shift(R0[i-1]) & mask[text[i]]                       // exact extension only

Rd[i] = ( shift(Rd[i-1])   & mask[text[i]] )   // no new error: characters must match
      |   shift(Rd-1[i-1])                     // substitution: any character, spend 1 error
      |         Rd-1[i-1]                      // insertion: consume a text char, pattern position stays put
      |   shift(Rd-1[i])                       // deletion: consume a pattern char, same text position

The first two terms are exactly Bitap's substitution-only recurrence, unchanged. The third term (insertion) reads from the previous text step without shifting — the pattern position it represents hasn't advanced, because the extra character in the text doesn't correspond to any pattern character. The fourth term (deletion) reads from Rd-1 at the same text position i, not i-1 — skipping a pattern character costs an error but consumes no text, so it has to be resolved before moving to the next character at all. That's why every level d from 0 up to k has to be computed in order for a given i: level d depends on level d-1 at the very same text position, a dependency substitution-only Bitap never had (there, every level for a given i could be computed independently). One more wrinkle at the very start: before any text is read, Rd is initialized with its bottom d bits already set (value (1 << d) - 1), encoding D[-1][j] = j — matching the pattern's first d characters against zero text costs d free deletions, mirroring the DP table's D[0][j] = j base case (Edit Distance's own dp[0][j] = j, just reindexed).

Reference implementation

This is the exact scheme the demo above steps through:

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 bitapEditDistance(text, pat, k) {
  const m = pat.length;
  const mask = buildMasks(pat);
  const fullMask = (1 << m) - 1;
  const finalBit = 1 << (m - 1);
  const shift = x => ((x << 1) | 1) & fullMask;

  // R[d] starts with its bottom d bits set: D[-1][j] = j, matched via d free deletions.
  let R = new Array(k + 1);
  for (let d = 0; d <= k; d++) R[d] = ((1 << d) - 1) & fullMask;

  const matches = [];                          // {pos, errors}, one entry per qualifying end position
  for (let i = 0; i < text.length; i++) {
    const charMask = mask[text[i]] || 0;
    const prev = R.slice();
    const next = [shift(prev[0]) & charMask];
    for (let d = 1; d <= k; d++) {
      next.push(
        (shift(prev[d]) & charMask) | shift(prev[d - 1]) | prev[d - 1] | shift(next[d - 1])
      );
    }
    R = next;
    for (let d = 0; d <= k; d++) {
      if (R[d] & finalBit) { matches.push({ pos: i, errors: d }); break; }  // smallest d wins
    }
  }
  return matches;
}

Pitfalls

A genuine match floods its own neighborhood with more "matches." Load the default demo at k = 0: exactly one position registers, the real kitten at 0 errors. Raise it to k = 1 and the count jumps from 1 to 6 raw end-positions — not because 5 new typos appeared, but because trimming or extending a 0-error window by a single character is always a 1-error window (delete or insert that one character back). At k = 2 it's 15 positions; every real occurrence in the text carries a small halo of near-miss neighbors that also clear the threshold, and the halo grows with k. This is real, checked behavior of the algorithm as specified above, not a bug in this demo — production fuzzy-search tools like agrep add an extra layer on top (report only the locally-smallest-error position within each cluster of qualifying end-positions, suppressing the rest) that is not implemented on this page, to keep the demo showing the recurrence itself rather than a second algorithm layered on it.

Every error level costs more per character than in substitution-only Bitap, and the per-level dependency is real. Each Rd above needs two shifts, one AND, and two ORs — versus one shift, one AND, one OR for Bitap's substitution-only version. Same O(n·k) asymptotic class, larger constant per level. And because the deletion term reads Rd-1 at the current text position, the k+1 levels for one character can't be updated independently or in parallel the way substitution-only Bitap's could — level d has to wait for level d-1 to finish first, every single character.

The one-machine-word ceiling is unchanged from Bitap. R still has to fit in a single JavaScript 32-bit integer, so the pattern is still capped at 31 characters in principle — this demo caps it at 10, same margin Bitap uses, well under that ceiling rather than at it.

Complexity

Time: O(n·k) — one word update per error level per text character, same asymptotic shape as substitution-only Bitap, with roughly double the per-level constant (four bit operations instead of two). Both stay within a single machine word only while m is at most the word width; beyond that, both need a further ⌈m / w⌉ factor. Space: O(σ + k) — one mask per distinct pattern character, plus one word per error level — independent of the text length, same as before.

The same "only a bounded budget matters" idea shows up again on Banded Edit Distance (Ukkonen's Algorithm), applied to a plain dynamic-programming table instead of a bit-parallel word: it restricts which cells of the table get filled rather than how many error levels get tracked, the same |i − j| ≤ k bound enforced a different way. A sixth entry, Jaro-Winkler Similarity, drops bit-parallelism and edit counting altogether — a bounded window still limits how far a character can move, but the output is a 0-to-1 similarity score, not a number of allowed errors. For a side-by-side comparison across all eleven approximate-match entries, see Choosing an Approximate String Matcher.