Bitap算法（或称为shift-or、shift-and、Baeza-Yates–Gonnet算法）是一种字符串近似匹配算法。该算法可判断给定的文本是否包含与定义模式“近似相等”的子字符串。其中，根据萊文斯坦距離如果子字符串和定义模式彼此在给定距离“K”之内，则该算法认为他们近似。该算法预先计算一组位掩码，其中每个位掩码的每一个元素都包含一个模式。然后，它可以通过按位操作以完成大部分工作。

可以将Bitap算法作为Unix软件开发工具agrep的基础算法之一，它由、Sun Wu和Burra Gopal开发。Udi Manber和Sun Wu的原始论文对算法进行了扩展，以处理一般正则表达式的模糊匹配。

由于算法需要的数据结构，它在小于固定长度（通常是字长）的模式上表现最佳。但是，一旦针对给定的字长“m”进行定义，则其运行时间是完全可以预测的——无论文本的结构或模式如何，它的运行时间均为O（"mn"）。

搜索精确字符串的Bitap算法在1964年由BálintDömölki发明，并由R. K. Shyamasundar在1977年进行了扩充。随后，在1989年由和开发，该算法也延伸到了处理字符、通配符和不匹配字符。1991年，和Sun Wu对其进行了扩展，以处理插入和删除操作（完全的模糊字符串搜索）。此算法后来在1996年由 Baeza-Yates和改进。

精确搜寻
完全通用的用于搜寻精确字符串的Bitap算法伪代码，如下所示：
algorithm bitap_search is
input: text as a string.
pattern as a string.
output: string
m := length(pattern)

if m = 0 then
return text

/ 初始化位数组R /
R := new array[m+1] of bit, initially all 0
R[0] := 1

for i := 0; i R |= 1。

为了将一般实例中的(text[i] == pattern[k-1])条件转换为按位运算，我们需要为CHAR_MAX附加位掩码。因此，Bitap算法在应用于查找较少字符串时性能更好。

#include
#include

const char bitap_bitwise_search(const char text, const char *pattern)
{
int m = strlen(pattern);
unsigned long R;
unsigned long pattern_mask[CHAR_MAX+1];
int i;

if (pattern[0] == '\0') return text;
if (m > 31) return "The pattern is too long!";

/ 初始化位数组R /
R = ~1;

/ 初始化位掩码 /
for (i=0; i

模糊搜寻
为了使用Bitap算法执行模糊字符串的查找，有必要将位数组“R”扩展到第二尺度。现在，我们有了“k”个不同的数组1..k数组 Ri，而不是具有随文本长度变化的单个数组“R”。“Ri”数组包含模式前缀的表示形式，该模式的前缀与“i”或拥有更少错误的当前字符串的任何后缀相匹配。在这种情况下，错误可以是插入、删除或替换的。有关这些操作的更多信息，请参见萊文斯坦距離。

下面的实例使用模糊Bitap算法执行（返回的第一个匹配值，错误率最高为“ k”）。但是，它仅仅关注替换，而不关注插入或删除换句话说，是[k]的汉明距离。同上一个实例，0和1的含义与它们的常规含义相反。

#include
#include
#include

const char bitap_fuzzy_bitwise_search(const char text, const char *pattern, int k)
{
const char *result = NULL;
int m = strlen(pattern);
unsigned long *R;
unsigned long pattern_mask[CHAR_MAX+1];
int i, d;

if (pattern[0] == '\0') return text;
if (m > 31) return "The pattern is too long!";

/ 初始化位数组R /
R = malloc((k+1) sizeof R);
for (i=0; i

参考文献

Bálint Dömölki, An algorithm for syntactical analysis, Computational Linguistics 3, Hungarian Academy of Science pp. 29–46, 1964.

Bálint Dömölki, A universal compiler system based on production rules, , 8(4), pp 262–275, 1968.

R. K. Shyamasundar, Precedence parsing using Dömölki's algorithm, , 6(2)pp 105–114, 1977.

Ricardo Baeza-Yates. "Efficient Text Searching." PhD Thesis, University of Waterloo, Canada, May 1989.

Udi Manber, Sun Wu. "Fast text searching with errors." Technical Report TR-91-11. Department of Computer Science, University of Arizona, Tucson, June 1991. ([ftp://ftp.cs.arizona.edu/agrep/agrep.ps.1.Z gzipped PostScript] )

Ricardo Baeza-Yates, Gastón H. Gonnet. "A New Approach to Text Searching." Communications of the ACM, 35(10): pp. 74–82, October 1992.

Udi Manber, Sun Wu. "Fast text search allowing errors." Communications of the ACM, 35(10): pp. 83–91, October 1992, .

R. Baeza-Yates and G. Navarro. A faster algorithm for approximate string matching. In Dan Hirchsberg and Gene Myers, editors, Combinatorial Pattern Matching (CPM'96), LNCS 1075, pages 1–23, Irvine, CA, June 1996.

G. Myers. "A fast bit-vector algorithm for approximate string matching based on dynamic programming." Journal of the ACM 46 (3), May 1999, 395–415.

#Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Modern Information Retrieval. 1999. .
外部链接
*[https://web.archive.org/web/20120122013152/http://www.cod5.ch/archive/l/libbitap.html libbitap]，一个自由的实例，它展示了如何轻松地将算法扩展为大多数正则表达式。与上面的代码不同，它对模式长度没有限制。
*[https://github.com/polovik/Algorithms/blob/master/bitap.py bitap.py] - Python实现：Wu-Manber修改的Bitap算法。

Bitap算法