Bitap算法

**Bitap 算法**（或稱為 **shift-or**、**shift-and**、**Baeza-Yates–Gonnet** 算法）是一種字符串近似匹配算法。該算法可判斷給定的文本是否包含與定義模式「近似相等」的子字符串。其中，根據萊文斯坦距離 – 如果子字符串和定義模式彼此在給定距離「K」之內，則該算法認為他們近似。該算法預先計算一組位掩碼，其中每個位掩碼的每一個元素都包含一個模式。然後，它可以通過按位操作以完成大部分工作。

可以將 Bitap 算法作為 Unix 軟體開發工具 agrep 的基礎算法之一，它由 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 和 Gaston Gonnet 開發，該算法也延伸到了處理字符、通配符和不匹配字符。1991 年，Manber 和 Sun Wu 對其進行了擴展，以處理插入和刪除操作（完全的模糊字符串搜索）。此算法後來在 1996 年由 Baeza-Yates 和 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 算法在應用於查找較少字符串時性能更好。

## 模糊搜尋

為了使用 Bitap 算法執行模糊字符串的查找，有必要將位數組「R」擴展到第二尺度。現在，我們有了「k」個不同的數組 1.._k_– 數組 _Ri_，而不是具有隨文本長度變化的單個數組「R」。「Ri」數組包含模式前綴的表示形式，該模式的前綴與「i」或擁有更少錯誤的當前字符串的任何後綴相匹配。在這種情況下，錯誤可以是插入、刪除或替換的。有關這些操作的更多信息，請參見萊文斯坦距離。

下面的實例使用模糊 Bitap 算法執行模糊匹配（返回的第一個匹配值，錯誤率最高為「 k」）。但是，它僅僅關注替換，而不關注插入或刪除 – 換句話說，是 [k] 的漢明距離。同上一個實例，0 和 1 的含義與它們的常規含義相反。

## 參考文獻

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, 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, 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 算法。