Bitap算法

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

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

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

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

精确搜寻

完全通用的用于搜寻精确字符串的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 < length(text); i += 1 do
        /* Update the bit array. */
        for k := m; k ≥ 1; k -= 1 do
          R[k] := R[k - 1] & (text[i] = pattern[k - 1])

        if R[m] then
            return (text + i - m) + 1

    return null

如上程序所示,Bitap在自然映射到简单的按位运算上与其他著名的字符串搜索算法不同。注意,在该实例中与多数人的直觉相反的是:值为0的每个位表示与其匹配,而值为1的每个位表示不匹配。可以使用0和1的直观含义编写相同的算法,但是在这种情况下,我们必须在内部循环中引入另一条指令来设置R |= 1

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

 #include <string.h>
 #include <limits.h>
 
 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 <= CHAR_MAX; ++i)
       pattern_mask[i] = ~0;
     for (i=0; i < m; ++i)
       pattern_mask[pattern[i]] &= ~(1UL << i);
 
     for (i=0; text[i] != '\0'; ++i) {
         /* 更新位数组 */
         R |= pattern_mask[text[i]];
         R <<= 1;
 
         if (0 == (R & (1UL << m)))
           return (text + i - m) + 1;
     }
 
     return NULL;
 }

模糊搜寻

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

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

 #include <stdlib.h>
 #include <string.h>
 #include <limits.h>
 
 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 <= k; ++i)
         R[i] = ~1;
 
     /* 初始化位掩码 */
     for (i=0; i <= CHAR_MAX; ++i)
         pattern_mask[i] = ~0;
     for (i=0; i < m; ++i)
         pattern_mask[pattern[i]] &= ~(1UL << i);
 
     for (i=0; text[i] != '\0'; ++i) {
         /* 更新位数组 */
         unsigned long old_Rd1 = R[0];
 
         R[0] |= pattern_mask[text[i]];
         R[0] <<= 1;
 
         for (d=1; d <= k; ++d) {
             unsigned long tmp = R[d];
             R[d] = (old_Rd1 & (R[d] | pattern_mask[text[i]])) << 1;
             old_Rd1 = tmp;
         }
 
         if (0 == (R[k] & (1UL << m))) {
             result = (text+i - m) + 1;
             break;
         }
     }
 
     free(R);
     return result;
 }

参考文献

  1. ^ Bálint Dömölki, An algorithm for syntactical analysis, Computational Linguistics 3, Hungarian Academy of Science pp. 29–46, 1964.
  2. ^ Bálint Dömölki, A universal compiler system based on production rules, BIT Numerical Mathematics英语BIT Numerical Mathematics, 8(4), pp 262–275, 1968. doi:10.1007/BF01933436
  3. ^ R. K. Shyamasundar, Precedence parsing using Dömölki's algorithm, International Journal of Computer Mathematics英语International Journal of Computer Mathematics, 6(2)pp 105–114, 1977.
  4. ^ Ricardo Baeza-Yates. "Efficient Text Searching." PhD Thesis, University of Waterloo, Canada, May 1989.
  5. ^ Udi Manber, Sun Wu. "Fast text searching with errors." Technical Report TR-91-11. Department of Computer Science, University of Arizona, Tucson, June 1991. (gzipped PostScript页面存档备份,存于互联网档案馆))
  6. ^ Ricardo Baeza-Yates, Gastón H. Gonnet. "A New Approach to Text Searching." Communications of the ACM, 35(10): pp. 74–82, October 1992.
  7. ^ Udi Manber, Sun Wu. "Fast text search allowing errors." Communications of the ACM, 35(10): pp. 83–91, October 1992, doi:10.1145/135239.135244.
  8. ^ 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.
  9. ^ 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.
  10. Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Modern Information Retrieval. 1999. ISBN 0-201-39829-X.

外部链接

  • libbitap,一个自由的实例,它展示了如何轻松地将算法扩展为大多数正则表达式。与上面的代码不同,它对模式长度没有限制。
  • bitap.py页面存档备份,存于互联网档案馆) - Python实现:Wu-Manber修改的Bitap算法。