bitap算法

bitap算法（又稱shift-or、shift-and或Baeza-Yates–Gonnet算法）是一種字元串近似匹配算法。此算法可以計算一段給定的字元串是否含有“約等於”給定模式串的子串，其中的“約等於”是用萊文斯坦距離定義的——如果子串和模式串的距離小於等於給定的k，算法就認為它們是匹配的。該算法先進行預處理計算一個掩碼集，其中每個位代表一個字元是否在模式串中出現過。於是，幾乎所有的操作都是位操作，速度非常快。

基本介紹

• 中文名：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個不同的數組R_{1 ..k}，而不是讓單個數組R在文本的長度上發生變化。數組R_i保存模式前綴的表示，該前綴與當前字元串的任何後綴匹配，其中包含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;  }