Bitap

Bitap, also known as the Shift-Or or Shift-And algorithm, is a bit-parallel method for string matching that finds occurrences of a pattern within a text. It can perform exact matching and, with extensions, fuzzy matching that allows a limited number of errors, such as substitutions, insertions, or deletions. The algorithm encodes the pattern into bitmasks for each character in the alphabet and then scans the text from left to right, updating one or more bit vectors with inexpensive bitwise operations. Each vector represents the state of potential matches at the current position, enabling many comparisons to be done in parallel.

In the exact version, the bitmasks indicate where characters of the alphabet appear in the pattern, and a match is reported when a designated bit pattern is achieved at some text position. In the approximate version, additional bit vectors track matches with up to e errors, allowing the algorithm to accommodate small differences between the text and the pattern. The approach is especially efficient when the pattern length fits within a single machine word, yielding a time complexity roughly proportional to the text length times the pattern length divided by the word size. For longer patterns, implementations can use multiple words or block-based variants to maintain efficiency.

Bitap is widely used in software tools that require fast searching and fuzzy matching, including text editors, search utilities, and certain bioinformatics applications. It performs best with short patterns and small alphabets, while performance may decline for very long patterns or large alphabets. The method has multiple names and variants, and it has influenced many later bit-parallel approaches to approximate string matching.