bitap算法（外文名：Baeza-Yates–Gonnet，又稱shift-or、shift-and算法）是一種字元串近似匹配算法，屬於計算機技術領域。該算法通過編輯距離判定字元串匹配，預處理階段生成字元掩碼集，利用移位運算實現快速查找，時間複雜度為O(n + m)。
算法分為精確匹配與模糊匹配兩種模式：精確匹配通過二進制掩碼預處理和位操作實現字元比對；模糊匹配擴展為k個位陣列結構，支持最多k次錯誤匹配，其編輯距離計算涵蓋字元插入、刪除和替換操作。所有操作基於位運算實現，包含模式長度校驗、記憶體分配及錯誤處理邏輯。
該算法基礎框架由Bálint Dömölki於1964年在句法分析研究中提出，其偽代碼實現體現了位操作的運算特性。
基本介紹
- 中文名：bitap算法
- 外文名：Baeza-Yates–Gonnet
- 學科：計算機技術
精確匹配,模糊匹配,
精確匹配
完全通用的精確字元串搜尋的bitap算法在偽代碼中看起來像這樣：
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 < length(text); i += 1: /* Update the bit array. */
for k = m; k >= 1; k -= 1:
R[k] = R[k-1] & (text[i] == pattern[k-1])
if R[m]:
return (text+i - m) + 1
return nil
Bitap在其自然映射到簡單的按位運算方面與其他眾所周知的字元串搜尋算法不同，如上述程式的以下修改。請注意，在此實現中，違反直覺，每個值為零的位表示匹配，值為1的每個位表示不匹配。可以使用0和1的直觀語義編寫相同的算法，但在這種情況下，我們必須在內部循環中引入另一條指令進行設定R |= 1。在這個實現中，我們利用左移一個值在右邊移動零的事實，這正是我們需要的行為。
模糊匹配
為了使用bitap算法執行模糊字元串搜尋，有必要將位陣列R擴展為第二維。我們現在有k個不同的數組R1 ..k，而不是讓單個數組R在文本的長度上發生變化。數組Ri保存模式前綴的表示，該前綴與當前字元串的任何後綴匹配，其中包含i或更少的錯誤。在這種情況下，“錯誤”可以是插入，刪除或替換;有關這些操作的更多信息，請參閱萊文斯坦距離。
下面的實現使用模糊比特算法執行模糊匹配（使用最多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!";
/* Initialize the bit array R */
R = malloc((k+1) * sizeof *R);
for (i=0; i <= k; ++i)
R[i] = ~1;
/* Initialize the pattern bitmasks */
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) {
/* Update the bit arrays */
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];
/* Substitution is all we care about */
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; }
