Bitap演算法

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'' < 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演算法在應用於查找較少字串時性能更好。

```c
 #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演算法執行（返回的第一個匹配值，錯誤率最高為「k」）。但是，它僅僅關注替換，而不關注插入或刪除 – 換句話說，是k的漢明距離。同上一個實例，0和1的含義與它們的常規含義相反。

```c
 #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;
 }
```

## 外部連結

- libbitap，一個自由的實例，它展示了如何輕鬆地將演算法擴展為大多數正則表達式。與上面的代碼不同，它對模式長度沒有限制。
- bitap.py - Python實現：Wu-Manber修改的Bitap演算法。