Where the Bitap Algorithm Matters

Introduction

Imagine you are searching a dictionary for a word you can almost remember — say algorithm — but you might have typed algorythm or algoritm. Exact search fails. You need approximate matching: find every occurrence of the pattern within k edits (substitutions, insertions, deletions) of some substring of the text.

The Bitap algorithm (also called Shift-Or or Shift-And) cracks this with a beautiful trick: it encodes the entire pattern into one bitmask per character of the alphabet, then tracks all possible match positions simultaneously by shifting and OR-ing integers. Each character in the text costs exactly one bitwise shift, one OR and one AND — and modern CPUs do those in a single clock cycle.

The algorithm was invented by Udi Manber and Ricardo Baeza-Yates and published in 1992. It remains one of the fastest practical solutions for short-to-medium patterns, and is the engine inside grep -F, several spell-checkers and bioinformatics read-mappers. Its status: a solved algorithm with proven optimal worst-case complexity for its class.

Try Approximate Search

Type a pattern (up to 30 characters) and a text, then choose how many errors (substitutions, insertions, deletions) to allow. Bitap finds every position where the pattern matches within that many edits.

<div class="controls">
  <label>Pattern <input id="pat" value="algo" maxlength="30" spellcheck="false"></label>
  <label>Text <input id="txt" value="I tried to find the algorythm but the algoritm escaped me" spellcheck="false"></label>
  <label>Max errors (k) <input id="kerr" type="number" min="0" max="4" value="1"></label>
</div>
<div class="btns">
  <button id="btn-run" type="button">Run</button>
  <button id="btn-step" type="button">Step</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="status" class="status">Press Run to search, or Step to advance one character.</div>
<div class="panel">
  <div class="col">
    <div class="label">Text (current position highlighted)</div>
    <div id="txt-vis" class="txt-vis"></div>
  </div>
  <div class="col">
    <div class="label">Bitmask state <span class="hint-small">(row = error level, bit 0 = leftmost pattern char)</span></div>
    <div id="mask-vis" class="mask-vis"></div>
  </div>
</div>
<div id="matches" class="matches"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .6rem; }
label { display: flex; align-items: center; gap: .5rem; font-weight: 600; font-size: .85rem; }
input[type=text], input:not([type]) { flex: 1; font: 13px ui-monospace,monospace; padding: .3rem .5rem;
  border: 1px solid #b0b8c4; border-radius: 6px; }
input[type=number] { width: 3.5rem; padding: .3rem .4rem; border: 1px solid #b0b8c4; border-radius: 6px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui,sans-serif; padding: .38rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin-bottom: .5rem; color: #444; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.panel { display: flex; gap: 1rem; flex-wrap: wrap; margin-bottom: .6rem; }
.col { flex: 1; min-width: 160px; }
.label { font-size: .78rem; font-weight: 700; color: #666; margin-bottom: .25rem; text-transform: uppercase; letter-spacing: .04em; }
.hint-small { font-weight: 400; text-transform: none; letter-spacing: 0; }
.txt-vis { font: 14px ui-monospace,monospace; letter-spacing: .05em; line-height: 1.9;
           word-break: break-all; }
.txt-vis span { padding: 1px 2px; border-radius: 3px; }
.txt-vis span.cur { background: #ffd700; color: #000; font-weight: 700; }
.txt-vis span.match { background: #b7f0c8; color: #0a5e28; }
.txt-vis span.cur.match { background: #52c88a; }
.mask-vis { font: 12px ui-monospace,monospace; }
.mask-row { display: flex; align-items: center; gap: .3rem; margin-bottom: .2rem; }
.mask-row .row-label { width: 2.4rem; color: #888; font-size: .75rem; flex-shrink: 0; }
.mask-bit { width: 16px; height: 16px; display: inline-flex; align-items: center; justify-content: center;
            border-radius: 3px; font-size: 10px; font-weight: 700; border: 1px solid #cdd6e0; }
.mask-bit.one { background: #1d3557; color: #fff; border-color: #1d3557; }
.mask-bit.zero { background: #f0f2f5; color: #aaa; }
.matches { font-size: .85rem; min-height: 1.4em; }
.match-chip { display: inline-block; background: #b7f0c8; color: #0a5e28; border-radius: 5px;
              padding: .15rem .5rem; margin: .2rem .2rem 0 0; font-weight: 600; font-size: .8rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Bitap (Shift-Or / Wu-Manber) approximate string matching.
// State: for each error level e in 0..k, maintain a bitmask R[e] where
// bit j (0-indexed from LSB) is 1 if the first (j+1) pattern characters match a suffix of the text ending at the current position, with exactly e errors.
//
// Transition per text character c:
//   D[e] = (R[e] << 1 | 1) & PM[c]          -- exact match extension
//   + insertions: R[e-1] << 1 | 1            -- insert text char (skip text)
//   + deletions:  R[e-1]                     -- delete pattern char (skip pattern)
//   + substitutions: (R[e-1] << 1 | 1) & ~PM[c]   wait... simplest form:
//   R'[e] = (D_e) | ((R[e-1] << 1 | 1)) | ((R[e-1]) << 1) with PM modulation
//
// Classic Wu-Manber formulation (1-indexed bits, using unsigned int):
//   R[0] = (R[0] << 1 | 1) & PM[c]
//   R[e] = ((R[e] << 1 | 1) & PM[c])         // exact
//           | (R[e-1] << 1 | 1)               // insertion into pattern
//           | R[e-1]                           // deletion from pattern
//           | (R[e-1] << 1)                   // substitution
//   Match at position i if bit m-1 of R[k] is set (0-indexed: bit m-1).

const MAX_PAT = 30;
let state = null; // { txt, pat, k, m, n, PM, R, pos, matchPositions }

function buildPM(pat) {
  const PM = {};
  for (let j = 0; j < pat.length; j++) {
    const c = pat[j];
    if (!PM[c]) PM[c] = 0;
    PM[c] |= (1 << j);
  }
  return PM;
}

function initState() {
  const pat = document.getElementById('pat').value.slice(0, MAX_PAT);
  const txt = document.getElementById('txt').value;
  const k   = Math.max(0, Math.min(4, parseInt(document.getElementById('kerr').value) || 0));
  const m   = pat.length;
  const n   = txt.length;
  if (m === 0) { setStatus('Pattern is empty.', ''); return null; }
  const PM  = buildPM(pat);
  // R[e] = bitmask; bit j set means first j+1 chars of pattern match ending here with e errors
  const R   = new Array(k + 1).fill(0);
  // Initialize R[e] = (1<<e)-1 would allow leading insertions… but standard init is R[e]=0
  // and we let the first few chars absorb the "free" insertions naturally.
  return { txt, pat, k, m, n, PM, R, pos: 0, matchPositions: new Set() };
}

function stepBitap(s) {
  if (s.pos >= s.n) return false;
  const c = s.txt[s.pos];
  const pm = s.PM[c] || 0;
  const { k, m } = s;
  const MASK = (m < 32) ? ((1 << m) - 1) : 0xFFFFFFFF; // keep only m bits
  const newR = new Array(k + 1);
  // e=0: exact only
  newR[0] = ((s.R[0] << 1) | 1) & pm & MASK;
  for (let e = 1; e <= k; e++) {
    const ins  = ((s.R[e-1] << 1) | 1) & MASK;          // insertion
    const del_ = (s.R[e-1] << 1) & MASK;                // deletion
    const sub  = ((s.R[e-1] << 1) | 1) & pm & MASK;     // substitution
    const exact= ((s.R[e]   << 1) | 1) & pm & MASK;     // exact extension
    newR[e] = (exact | ins | del_ | sub) & MASK;
  }
  const matchBit = 1 << (m - 1);
  if (newR[k] & matchBit) {
    s.matchPositions.add(s.pos);
  }
  s.R = newR;
  s.pos++;
  return true;
}

function renderAll(s) {
  // Text visualization
  const tv = document.getElementById('txt-vis');
  if (!s) { tv.innerHTML = ''; document.getElementById('mask-vis').innerHTML = ''; return; }
  let html = '';
  for (let i = 0; i < s.n; i++) {
    const isCur   = i === s.pos - 1;
    const isMatch = s.matchPositions.has(i);
    let cls = isCur && isMatch ? 'cur match' : isCur ? 'cur' : isMatch ? 'match' : '';
    html += `<span class="${cls}">${s.txt[i] === ' ' ? '&nbsp;' : s.txt[i]}</span>`;
  }
  tv.innerHTML = html;

  // Mask visualization
  const mv = document.getElementById('mask-vis');
  let mhtml = '';
  for (let e = 0; e <= s.k; e++) {
    mhtml += `<div class="mask-row"><span class="row-label">k=${e}</span>`;
    for (let j = 0; j < s.m; j++) {
      const bit = (s.R[e] >> j) & 1;
      mhtml += `<span class="mask-bit ${bit ? 'one' : 'zero'}">${bit}</span>`;
    }
    mhtml += '</div>';
  }
  mv.innerHTML = mhtml;

  // Matches
  const mc = document.getElementById('matches');
  if (s.matchPositions.size > 0) {
    let chips = '';
    s.matchPositions.forEach(p => {
      // Match ends at position p; show end position (1-indexed)
      chips += fmt('<span class="match-chip">pos %v%</span>', { v: p + 1 });
    });
    mc.innerHTML = fmt('Matches ending at: %chips%', { chips: chips });
  } else {
    mc.innerHTML = s.pos === s.n ? 'No matches found.' : '';
  }
}

function setStatus(t, cls) {
  const el = document.getElementById('status');
  el.textContent = t;
  el.className = 'status ' + cls;
}

document.getElementById('btn-run').addEventListener('click', () => {
  state = initState();
  if (!state) return;
  while (stepBitap(state)) {}
  renderAll(state);
  const cnt = state.matchPositions.size;
  setStatus(
    cnt > 0
      ? (cnt > 1 ? fmt('Found %cnt% matches (k ≤ %k% errors). Highlighted in green.', { cnt: cnt, k: state.k }) : fmt('Found %cnt% match (k ≤ %k% errors). Highlighted in green.', { cnt: cnt, k: state.k }))
      : fmt('No matches within k=%k% errors.', { k: state.k }),
    cnt > 0 ? 'ok' : 'info'
  );
});

document.getElementById('btn-step').addEventListener('click', () => {
  if (!state) state = initState();
  if (!state) return;
  if (state.pos >= state.n) {
    setStatus('End of text reached. Press Reset to start over.', 'info');
    return;
  }
  const before = state.pos;
  stepBitap(state);
  renderAll(state);
  const c = state.txt[before];
  setStatus(
    fmt('Processed character [%c%] at position %v%/%n%.%v2%', { c: c, v: before + 1, n: state.n, v2: state.matchPositions.has(before) ? ' Match here!' : '' }),
    state.matchPositions.has(before) ? 'ok' : 'info'
  );
});

document.getElementById('btn-reset').addEventListener('click', () => {
  state = null;
  document.getElementById('txt-vis').innerHTML = '';
  document.getElementById('mask-vis').innerHTML = '';
  document.getElementById('matches').innerHTML = '';
  setStatus('Press Run to search, or Step to advance one character.', '');
});

<div class="controls">
  <label>Pattern <input id="pat" value="algo" maxlength="30" spellcheck="false"></label>
  <label>Text <input id="txt" value="I tried to find the algorythm but the algoritm escaped me" spellcheck="false"></label>
  <label>Max errors (k) <input id="kerr" type="number" min="0" max="4" value="1"></label>
</div>
<div class="btns">
  <button id="btn-run" type="button">Run</button>
  <button id="btn-step" type="button">Step</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="status" class="status">Press Run to search, or Step to advance one character.</div>
<div class="panel">
  <div class="col">
    <div class="label">Text (current position highlighted)</div>
    <div id="txt-vis" class="txt-vis"></div>
  </div>
  <div class="col">
    <div class="label">Bitmask state <span class="hint-small">(row = error level, bit 0 = leftmost pattern char)</span></div>
    <div id="mask-vis" class="mask-vis"></div>
  </div>
</div>
<div id="matches" class="matches"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .6rem; }
label { display: flex; align-items: center; gap: .5rem; font-weight: 600; font-size: .85rem; }
input[type=text], input:not([type]) { flex: 1; font: 13px ui-monospace,monospace; padding: .3rem .5rem;
  border: 1px solid #b0b8c4; border-radius: 6px; }
input[type=number] { width: 3.5rem; padding: .3rem .4rem; border: 1px solid #b0b8c4; border-radius: 6px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui,sans-serif; padding: .38rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin-bottom: .5rem; color: #444; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.panel { display: flex; gap: 1rem; flex-wrap: wrap; margin-bottom: .6rem; }
.col { flex: 1; min-width: 160px; }
.label { font-size: .78rem; font-weight: 700; color: #666; margin-bottom: .25rem; text-transform: uppercase; letter-spacing: .04em; }
.hint-small { font-weight: 400; text-transform: none; letter-spacing: 0; }
.txt-vis { font: 14px ui-monospace,monospace; letter-spacing: .05em; line-height: 1.9;
           word-break: break-all; }
.txt-vis span { padding: 1px 2px; border-radius: 3px; }
.txt-vis span.cur { background: #ffd700; color: #000; font-weight: 700; }
.txt-vis span.match { background: #b7f0c8; color: #0a5e28; }
.txt-vis span.cur.match { background: #52c88a; }
.mask-vis { font: 12px ui-monospace,monospace; }
.mask-row { display: flex; align-items: center; gap: .3rem; margin-bottom: .2rem; }
.mask-row .row-label { width: 2.4rem; color: #888; font-size: .75rem; flex-shrink: 0; }
.mask-bit { width: 16px; height: 16px; display: inline-flex; align-items: center; justify-content: center;
            border-radius: 3px; font-size: 10px; font-weight: 700; border: 1px solid #cdd6e0; }
.mask-bit.one { background: #1d3557; color: #fff; border-color: #1d3557; }
.mask-bit.zero { background: #f0f2f5; color: #aaa; }
.matches { font-size: .85rem; min-height: 1.4em; }
.match-chip { display: inline-block; background: #b7f0c8; color: #0a5e28; border-radius: 5px;
              padding: .15rem .5rem; margin: .2rem .2rem 0 0; font-weight: 600; font-size: .8rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Bitap (Shift-Or / Wu-Manber) approximate string matching.
// State: for each error level e in 0..k, maintain a bitmask R[e] where
// bit j (0-indexed from LSB) is 1 if the first (j+1) pattern characters match a suffix of the text ending at the current position, with exactly e errors.
//
// Transition per text character c:
//   D[e] = (R[e] << 1 | 1) & PM[c]          -- exact match extension
//   + insertions: R[e-1] << 1 | 1            -- insert text char (skip text)
//   + deletions:  R[e-1]                     -- delete pattern char (skip pattern)
//   + substitutions: (R[e-1] << 1 | 1) & ~PM[c]   wait... simplest form:
//   R'[e] = (D_e) | ((R[e-1] << 1 | 1)) | ((R[e-1]) << 1) with PM modulation
//
// Classic Wu-Manber formulation (1-indexed bits, using unsigned int):
//   R[0] = (R[0] << 1 | 1) & PM[c]
//   R[e] = ((R[e] << 1 | 1) & PM[c])         // exact
//           | (R[e-1] << 1 | 1)               // insertion into pattern
//           | R[e-1]                           // deletion from pattern
//           | (R[e-1] << 1)                   // substitution
//   Match at position i if bit m-1 of R[k] is set (0-indexed: bit m-1).

const MAX_PAT = 30;
let state = null; // { txt, pat, k, m, n, PM, R, pos, matchPositions }

function buildPM(pat) {
  const PM = {};
  for (let j = 0; j < pat.length; j++) {
    const c = pat[j];
    if (!PM[c]) PM[c] = 0;
    PM[c] |= (1 << j);
  }
  return PM;
}

function initState() {
  const pat = document.getElementById('pat').value.slice(0, MAX_PAT);
  const txt = document.getElementById('txt').value;
  const k   = Math.max(0, Math.min(4, parseInt(document.getElementById('kerr').value) || 0));
  const m   = pat.length;
  const n   = txt.length;
  if (m === 0) { setStatus('Pattern is empty.', ''); return null; }
  const PM  = buildPM(pat);
  // R[e] = bitmask; bit j set means first j+1 chars of pattern match ending here with e errors
  const R   = new Array(k + 1).fill(0);
  // Initialize R[e] = (1<<e)-1 would allow leading insertions… but standard init is R[e]=0
  // and we let the first few chars absorb the "free" insertions naturally.
  return { txt, pat, k, m, n, PM, R, pos: 0, matchPositions: new Set() };
}

function stepBitap(s) {
  if (s.pos >= s.n) return false;
  const c = s.txt[s.pos];
  const pm = s.PM[c] || 0;
  const { k, m } = s;
  const MASK = (m < 32) ? ((1 << m) - 1) : 0xFFFFFFFF; // keep only m bits
  const newR = new Array(k + 1);
  // e=0: exact only
  newR[0] = ((s.R[0] << 1) | 1) & pm & MASK;
  for (let e = 1; e <= k; e++) {
    const ins  = ((s.R[e-1] << 1) | 1) & MASK;          // insertion
    const del_ = (s.R[e-1] << 1) & MASK;                // deletion
    const sub  = ((s.R[e-1] << 1) | 1) & pm & MASK;     // substitution
    const exact= ((s.R[e]   << 1) | 1) & pm & MASK;     // exact extension
    newR[e] = (exact | ins | del_ | sub) & MASK;
  }
  const matchBit = 1 << (m - 1);
  if (newR[k] & matchBit) {
    s.matchPositions.add(s.pos);
  }
  s.R = newR;
  s.pos++;
  return true;
}

function renderAll(s) {
  // Text visualization
  const tv = document.getElementById('txt-vis');
  if (!s) { tv.innerHTML = ''; document.getElementById('mask-vis').innerHTML = ''; return; }
  let html = '';
  for (let i = 0; i < s.n; i++) {
    const isCur   = i === s.pos - 1;
    const isMatch = s.matchPositions.has(i);
    let cls = isCur && isMatch ? 'cur match' : isCur ? 'cur' : isMatch ? 'match' : '';
    html += `<span class="${cls}">${s.txt[i] === ' ' ? '&nbsp;' : s.txt[i]}</span>`;
  }
  tv.innerHTML = html;

  // Mask visualization
  const mv = document.getElementById('mask-vis');
  let mhtml = '';
  for (let e = 0; e <= s.k; e++) {
    mhtml += `<div class="mask-row"><span class="row-label">k=${e}</span>`;
    for (let j = 0; j < s.m; j++) {
      const bit = (s.R[e] >> j) & 1;
      mhtml += `<span class="mask-bit ${bit ? 'one' : 'zero'}">${bit}</span>`;
    }
    mhtml += '</div>';
  }
  mv.innerHTML = mhtml;

  // Matches
  const mc = document.getElementById('matches');
  if (s.matchPositions.size > 0) {
    let chips = '';
    s.matchPositions.forEach(p => {
      // Match ends at position p; show end position (1-indexed)
      chips += fmt('<span class="match-chip">pos %v%</span>', { v: p + 1 });
    });
    mc.innerHTML = fmt('Matches ending at: %chips%', { chips: chips });
  } else {
    mc.innerHTML = s.pos === s.n ? 'No matches found.' : '';
  }
}

function setStatus(t, cls) {
  const el = document.getElementById('status');
  el.textContent = t;
  el.className = 'status ' + cls;
}

document.getElementById('btn-run').addEventListener('click', () => {
  state = initState();
  if (!state) return;
  while (stepBitap(state)) {}
  renderAll(state);
  const cnt = state.matchPositions.size;
  setStatus(
    cnt > 0
      ? (cnt > 1 ? fmt('Found %cnt% matches (k ≤ %k% errors). Highlighted in green.', { cnt: cnt, k: state.k }) : fmt('Found %cnt% match (k ≤ %k% errors). Highlighted in green.', { cnt: cnt, k: state.k }))
      : fmt('No matches within k=%k% errors.', { k: state.k }),
    cnt > 0 ? 'ok' : 'info'
  );
});

document.getElementById('btn-step').addEventListener('click', () => {
  if (!state) state = initState();
  if (!state) return;
  if (state.pos >= state.n) {
    setStatus('End of text reached. Press Reset to start over.', 'info');
    return;
  }
  const before = state.pos;
  stepBitap(state);
  renderAll(state);
  const c = state.txt[before];
  setStatus(
    fmt('Processed character [%c%] at position %v%/%n%.%v2%', { c: c, v: before + 1, n: state.n, v2: state.matchPositions.has(before) ? ' Match here!' : '' }),
    state.matchPositions.has(before) ? 'ok' : 'info'
  );
});

document.getElementById('btn-reset').addEventListener('click', () => {
  state = null;
  document.getElementById('txt-vis').innerHTML = '';
  document.getElementById('mask-vis').innerHTML = '';
  document.getElementById('matches').innerHTML = '';
  setStatus('Press Run to search, or Step to advance one character.', '');
});

Result

Console

Notice how the same bit machinery that finds exact matches also handles typos — you pay zero extra cost per kind of error: each additional error level adds just one more bitmask layer. Press Step to advance one character at a time and see how the bitmask shifts, or Run to scan the whole text at once.

The Real Complexity

Let $m$ be the pattern length, $n$ the text length, $w$ the machine word width (64 on a modern CPU) and $\sigma$ the alphabet size.

Exact Bitap (Shift-Or):

Time: $O(mn/w)$ . For patterns up to 64 characters the state is one 64-bit integer, so the loop is $O(n)$ — one shift + one OR per text character.
Space: $O(m\sigma/w)$ . One bitmask of length $m$ per distinct character.
Preprocessing: $O(m\sigma)$ to build the character masks.

Approximate Bitap (Wu–Manber extension):

Adds $k$ extra bitmask rows — one per allowed error level.
Time: $O(kmn/w)$ . Still linear in $n$ for fixed $k$ and $m \le w$ .
The hidden constant is tiny because all operations are register-level bitwise ops.

The key insight: Bitap simulates a non-deterministic finite automaton (NFA) over the pattern, but instead of explicitly stepping through every NFA state it packs all active states into the bits of an integer and advances all of them in parallel with one instruction. This is the bit-parallel trick.

Compare this with pattern matching algorithms like KMP or Boyer–Moore: those achieve $O(n)$ for exact search on larger alphabets but don't extend as gracefully to approximate matching without rebuilding the entire automaton.

Where It Matters

Anywhere a human (or a sequencing machine) can make a mistake in a string, Bitap is a candidate:

agrep and fuzzy grep: the agrep command-line tool is a direct implementation of Wu–Manber Bitap. It lets you write agrep -2 'pattern' file to find lines within 2 edits of the pattern.
Spell-checking and autocorrect: dictionary lookup with $k=1$ or $k=2$ errors finds the closest word to a typo without scanning every entry naively.
DNA short-read alignment: sequencers produce millions of short reads (50–150 bp). Approximate Bitap can map each read to a reference genome allowing a small number of sequencing errors — the pattern fits in one 64-bit register.
Intrusion detection and antivirus: signature scanners must allow for slight mutations in known exploit patterns; Bitap handles that in a single pass over incoming bytes.
Full-text search engines: for short user queries, Bitap often outperforms index-based approaches because there is no index build time and the constant is so small.

See also pattern matching for exact algorithms, and sequence alignment for the dynamic-programming approach to longer approximate matching.

Conclusion

The Bitap algorithm is a masterclass in what happens when you let the hardware think. By compressing the entire match state into the bits of an ordinary integer, it turns a problem that looks like it requires expensive character-by-character bookkeeping into a tight loop of three cheap instructions.

It is solved and optimal for its regime: patterns up to one machine word wide, with a small number of allowed errors. Beyond that regime — long patterns, large error budgets, richer edit models — dynamic-programming methods like sequence alignment take over. But for the common case of short patterns in streaming text, no approach beats the elegance of a bit shift.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bitap-algorithm/Content licensed under CC BY-NC 4.0.

Cookies & privacy

The Bitap Algorithm

Finding needles you can't quite spell