Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Bitap algorithm
open-in-new
<p>The bitap algorithm (also known as the shift-or, shift-and or Baeza-Yates–Gonnet algorithm) is an <a href="/facts/Approximate_string_matching/aotktvNI">approximate string matching</a> algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given pattern, where approximate equality is defined in terms of <a href="/facts/Levenshtein_distance/F0otyNSl">Levenshtein distance</a> – if the substring and pattern are within a given distance <i>k</i> of each other, then the algorithm considers them equal. The algorithm begins by precomputing a set of <a href="/facts/Bitmask/d9Cu1A1Y">bitmasks</a> containing one bit for each element of the pattern. Then it is able to do most of the work with <a href="/facts/Bitwise_operation/0gkqnUda">bitwise operations</a>, which are extremely fast. </p><p>The bitap algorithm is perhaps best known as one of the underlying algorithms of the <a href="/facts/Unix/0pNL2seI">Unix</a> <a href="/facts/Programming_tool/wWaFqCFw">utility</a> <a href="/facts/Agrep/QWARW3jS">agrep</a>, written by <a href="/facts/Udi_Manber/XWfScQzc">Udi Manber</a>, Sun Wu, and Burra Gopal. Manber and Wu's original paper gives extensions of the algorithm to deal with fuzzy matching of general <a href="/facts/Regular_expression/KFL3veHX">regular expressions</a>. </p><p>Due to the data structures required by the algorithm, it performs best on patterns less than a constant length (typically the <a href="/facts/Word_length/2e5umRaj">word length</a> of the machine in question), and also prefers inputs over a small alphabet. Once it has been implemented for a given alphabet and word length <i>m</i>, however, its <a href="/facts/Running_time/77T62gmf">running time</a> is completely predictable – it runs in <a href="/facts/Big_O_notation/weFFjSWg">O</a>(<i>mn</i>) operations, no matter the structure of the text or the pattern. </p><p>The bitap algorithm for exact string searching was invented by Bálint Dömölki in 1964<a href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_Domolki64">[1]</a><a href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_Domolki68">[2]</a> and extended by R. K. Shyamasundar in 1977<a href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_shyamasundar77">[3]</a>, before being reinvented by <a href="/facts/Ricardo_Baeza-Yates/65fUMxgX">Ricardo Baeza-Yates</a> and <a href="/facts/Gaston_Gonnet/L2HhgeVo">Gaston Gonnet</a><a href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_BYG92">[4]</a> in 1989 (one chapter of first author's PhD thesis<a href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_BY89">[5]</a>) which also extended it to handle classes of characters, wildcards, and mismatches. In 1991, it was extended by <a href="/facts/Udi_Manber/XWfScQzc">Manber</a> and Wu <a href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_Manber91">[6]</a><a href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_Manber92">[7]</a> to handle also insertions and deletions (full fuzzy string searching). This algorithm was later improved by Baeza-Yates and <a href="/facts/Gonzalo_Navarro/uUp5dX9m">Navarro</a> in 1996.<a href="https://en.wikipedia.org/wiki/Bitap_algorithm#endnote_BN96">[8]</a> </p>