[科普中国]-bitap算法

bitap算法（又称shift-or、shift-and或Baeza-Yates–Gonnet算法）是一种字符串近似匹配算法。此算法可以计算一段给定的字符串是否含有“约等于”给定模式串的子串，其中的“约等于”是用莱文斯坦距离定义的——如果子串和模式串的距离小于等于给定的k，算法就认为它们是匹配的。该算法先进行预处理计算一个掩码集，其中每个位代表一个字符是否在模式串中出现过。于是，几乎所有的操作都是位操作，速度非常快。

精确匹配完全通用的精确字符串搜索的bitap算法在伪代码中看起来像这样1：

algorithm bitap_search(text : string, pattern : string) returns string m := length(pattern) if m == 0 return text /* Initialize the bit array R. */ R := new array[m+1] of bit, initially all 0 R[0] = 1 for i = 0; i = 1; k -= 1: R[k] = R[k-1] & (text[i] == pattern[k-1]) if R[m]: return (text+i - m) + 1 return nilBitap在其自然映射到简单的按位运算方面与其他众所周知的字符串搜索算法不同，如上述程序的以下修改。请注意，在此实现中，违反直觉，每个值为零的位表示匹配，值为1的每个位表示不匹配。可以使用0和1的直观语义编写相同的算法，但在这种情况下，我们必须在内部循环中引入另一条指令进行设置R |= 1。在这个实现中，我们利用左移一个值在右边移动零的事实，这正是我们需要的行为。

模糊匹配为了使用bitap算法执行模糊字符串搜索，有必要将位阵列R扩展为第二维。我们现在有k个不同的数组R1 ..k，而不是让单个数组R在文本的长度上发生变化。数组Ri保存模式前缀的表示，该前缀与当前字符串的任何后缀匹配，其中包含i或更少的错误。在这种情况下，“错误”可以是插入，删除或替换;有关这些操作的更多信息，请参阅莱文斯坦距离。

下面的实现使用模糊比特算法执行模糊匹配（使用最多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!"; /* Initialize the bit array R */ R = malloc((k+1) * sizeof *R); for (i=0; i