Bitap Algorithm

The bitap algorithm, also known as the shift-or, shift-and or Baeza-Yates-Gonnet algorithm, is an approximate string matching algorithm that tells whether a given text contains a substring approximately equal to a given pattern, where approximate equality is defined by a Levenshtein distance no greater than a chosen threshold. It precomputes a set of bitmasks, one bit per element of the pattern, and then does most of its work with fast bitwise operations, which makes it perform best on patterns shorter than the machine's word length and on inputs drawn from a small alphabet; once implemented for a given alphabet and pattern length it runs in completely predictable time regardless of the structure of the text or pattern. The algorithm for exact string searching was invented by Balint Domolki in 1964 and was reinvented and extended to fuzzy matching by Ricardo Baeza-Yates and Gaston Gonnet in 1989, with later extensions handling insertions and deletions.