fbpx
维基百科

Bitap算法

六月 19, 2023

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

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

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

搜索精确字符串的Bitap算法在1964年由BálintDömölki发明，并由R. K. Shyamasundar在1977年进行了扩充。随后，在1989年由Ricardo Baeza-Yates（英语：Ricardo Baeza-Yates）和Gaston 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.

外部链接

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

六月 19, 2023
bitap算法, 或称为shift, shift, baeza, yates, gonnet算法, 是一种字符串近似匹配算法, 该算法可判断给定的文本是否包含与定义模式, 近似相等, 的子字符串, 其中, 根据萊文斯坦距離, 如果子字符串和定义模式彼此在给定距离, 之内, 则该算法认为他们近似, 该算法预先计算一组位掩码, 其中每个位掩码的每一个元素都包含一个模式, 然后, 它可以通过按位操作以完成大部分工作, 可以将作为unix软件开发工具agrep的基础算法之一, 它由udi, manber, 英语, manb. Bitap算法 或称为shift or shift and Baeza Yates Gonnet算法 是一种字符串近似匹配算法 该算法可判断给定的文本是否包含与定义模式 近似相等 的子字符串 其中 根据萊文斯坦距離 如果子字符串和定义模式彼此在给定距离 K 之内 则该算法认为他们近似 该算法预先计算一组位掩码 其中每个位掩码的每一个元素都包含一个模式 然后 它可以通过按位操作以完成大部分工作 可以将Bitap算法作为Unix软件开发工具agrep的基础算法之一 它由Udi Manber 英语 Udi Manber Sun Wu和Burra Gopal开发 Udi Manber和Sun Wu的原始论文对算法进行了扩展 以处理一般正则表达式的模糊匹配 由于算法需要的数据结构 它在小于固定长度 通常是字长 的模式上表现最佳 但是 一旦针对给定的字长 m 进行定义 则其运行时间是完全可以预测的 无论文本的结构或模式如何 它的运行时间均为O mn 搜索精确字符串的Bitap算法在1964年由BalintDomolki发明 并由R K Shyamasundar在1977年进行了扩充 随后 在1989年由Ricardo Baeza Yates 英语 Ricardo Baeza Yates 和Gaston Gonnet 英语 Gaston Gonnet 开发 该算法也延伸到了处理字符 通配符和不匹配字符 1991年 Manber 英语 Udi Manber 和Sun Wu对其进行了扩展 以处理插入和删除操作 完全的模糊字符串搜索 此算法后来在1996年由 Baeza Yates和Navarro 英语 Gonzalo Navarro 改进 目录 1 精确搜寻 2 模糊搜寻 3 参考文献 4 外部链接精确搜寻 编辑完全通用的用于搜寻精确字符串的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 lt length text i 1 do Update the bit array for k m k 1 k 1 do R k R k 1 amp 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 lt string h gt include lt limits h gt 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 gt 31 return The pattern is too long 初始化位数组R R 1 初始化位掩码 for i 0 i lt CHAR MAX i pattern mask i 0 for i 0 i lt m i pattern mask pattern i amp 1UL lt lt i for i 0 text i 0 i 更新位数组 R pattern mask text i R lt lt 1 if 0 R amp 1UL lt lt 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 lt stdlib h gt include lt string h gt include lt limits h gt 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 gt 31 return The pattern is too long 初始化位数组R R malloc k 1 sizeof R for i 0 i lt k i R i 1 初始化位掩码 for i 0 i lt CHAR MAX i pattern mask i 0 for i 0 i lt m i pattern mask pattern i amp 1UL lt lt i for i 0 text i 0 i 更新位数组 unsigned long old Rd1 R 0 R 0 pattern mask text i R 0 lt lt 1 for d 1 d lt k d unsigned long tmp R d R d old Rd1 amp R d pattern mask text i lt lt 1 old Rd1 tmp if 0 R k amp 1UL lt lt m result text i m 1 break free R return result 参考文献 编辑 Balint Domolki An algorithm for syntactical analysis Computational Linguistics 3 Hungarian Academy of Science pp 29 46 1964 Balint Domolki A universal compiler system based on production rules BIT Numerical Mathematics 英语 BIT Numerical Mathematics 8 4 pp 262 275 1968 doi 10 1007 BF01933436 R K Shyamasundar Precedence parsing using Domolki s algorithm International Journal of Computer Mathematics 英语 International Journal of Computer Mathematics 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 gzipped PostScript 页面存档备份 存于互联网档案馆 Ricardo Baeza Yates Gaston 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 doi 10 1145 135239 135244 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 ISBN 0 201 39829 X 外部链接 编辑libbitap 一个自由的实例 它展示了如何轻松地将算法扩展为大多数正则表达式 与上面的代码不同 它对模式长度没有限制 bitap py 页面存档备份 存于互联网档案馆 Python实现 Wu Manber修改的Bitap算法 取自 https zh wikipedia org w index php title Bitap算法 amp oldid 71573255, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。