The Bitap Algorithm

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.

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>{{label_pattern}} <input id="pat" value="algo" maxlength="30" spellcheck="false"></label>
  <label>{{label_text}} <input id="txt" value="I tried to find the algorythm but the algoritm escaped me" spellcheck="false"></label>
  <label>{{label_max_errors}} <input id="kerr" type="number" min="0" max="4" value="1"></label>
</div>
<div class="btns">
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="status" class="status">{{status_initial}}</div>
<div class="panel">
  <div class="col">
    <div class="label">{{panel_text_label}}</div>
    <div id="txt-vis" class="txt-vis"></div>
  </div>
  <div class="col">
    <div class="label">{{panel_mask_label}} <span class="hint-small">{{panel_mask_hint}}</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; }

// Code not found

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.

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.

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.

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.