Bitap Algorithm: Bit-Parallel NFA Fuzzy Search

The Bitap algorithm—also known as the Shift-Or, Shift-And, or Baeza-Yates–Gonnet algorithm—is an approximate string matching technique that simulates a Non-deterministic Finite Automaton (NFA) using bitwise operations. By encoding the states of an NFA as individual bits within standard binary computer words, the algorithm evaluates multiple potential match states simultaneously. This article explains how bit-parallel NFA simulation operates at the binary level to perform fast, efficient fuzzy text searches capable of handling substitutions, insertions, and deletions.

The NFA Model for Approximate Matching

In string searching, an NFA can be designed to recognize a pattern of length \(m\) along with up to \(k\) allowable errors (Levenshtein distance). The automaton contains a grid of states: * Horizontal axis (\(m\)): Represents matching successive characters of the target pattern. * Vertical axis (\(k\)): Represents the number of accumulated edit errors (0 errors, 1 error, …, up to \(k\) errors).

Transitioning across states depends on the next input character (an exact match), while moving diagonally or vertically models an error: * Substitution: Advances the pattern and increases the error count by 1. * Insertion: Consumes a character from the text, remains at the current pattern position, and increments the error count. * Deletion: Advances the pattern position without consuming a text character, incrementing the error count.

The Bit-Parallel Concept

Standard NFA simulations can be computationally expensive because maintaining sets of active states requires tracking many pointers or graph nodes. The Bitap algorithm eliminates this overhead using bit-parallelism.

Instead of tracking states with complex data structures, a state vector of length \(m\) is packed directly into an integer (a binary word, such as a 32-bit or 64-bit integer). Each bit position corresponds to an active or inactive state in the NFA: * A 0 (or 1, depending on whether the implementation uses Shift-Or or Shift-And) indicates that the state is active. * Transitioning all active states simultaneously across the entire pattern requires only a few native CPU bitwise instructions: shifts (<<), bitwise OR (|), bitwise AND (&), and bitwise NOT (~).

How the Algorithm Executes in the Binary Number System

  1. Precomputing Pattern Masks: Before scanning the text, a bitmask table \(B[c]\) is created for every unique character \(c\) in the alphabet. Each bitmask is an \(m\)-bit binary word where the \(i\)-th bit indicates whether character \(c\) matches the \(i\)-th character of the pattern.

  2. Exact Matching State Transitions (0 Errors): For an exact match search (Shift-And variation), a single binary word \(R\) tracks the active states. For each incoming character \(T[j]\) from the text: \[R = ((R \ll 1) \mid 1) \ \& \ B[T[j]]\]

    • (R << 1) | 1: Propagates active states forward by one position and sets the initial state active.
    • & B[T[j]]: Filters out any states where the current pattern character does not match the incoming text character.
    • A match is found when the \(m\)-th bit of \(R\) becomes active.

  3. Handling Errors (\(k > 0\)): To support fuzzy search up to \(k\) errors, the algorithm maintains an array of \(k + 1\) binary state vectors: \(R_0, R_1, \dots, R_k\).

    • \(R_0\) tracks matches with 0 errors.
    • \(R_d\) tracks matches with \(d\) errors.

    For each text character \(T[j]\), the states update using bitwise logic that combines exact transitions with all possible edit operations: \[R_d' = \underbrace{((R_d \ll 1) \ \& \ B[T[j]])}_{\text{Exact Match}} \ \mid \ \underbrace{(R_{d-1} \ll 1)}_{\text{Substitution}} \ \mid \ \underbrace{R_{d-1}'}_{\text{Insertion}} \ \mid \ \underbrace{(R_{d-1}' \ll 1)}_{\text{Deletion}}\]

    Because these operations occur directly on binary words, all possible branches of the non-deterministic search tree for up to \(k\) errors are evaluated in parallel in constant time \(O(1)\) per character.

Performance and Trade-Offs