Boyer-Moore Algorithm (อัลกอริทึมบอยเออร์-มอร์) - Good Suffix Heuristic

Boyer-Moore Algorithm เป็นอัลกอริทึมค้นหา Pattern ใน String ที่เร็วที่สุดในทางปฏิบัติ ใช้ 2 Heuristics: Bad Character Rule และ Good Suffix Rule บทความนี้ครอบคลุม Good Suffix Heuristic

แนวคิด Good Suffix Heuristic

เมื่อพบการ Match บางส่วน (Suffix ของ Pattern ตรงกับ Substring ของ Text) ให้เลื่อน Pattern ให้ Suffix ที่ตรงกันนั้น ตรงกับ Prefix ของ Pattern หรือ Occurrence ถัดไปของ Suffix เดียวกันใน Pattern

ตัวอย่างข้อมูล

Text:    ABAAABCDBBABCDDEBCABC
Pattern: ABC

Output:
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

โครงสร้างข้อมูล

• shift[]: จำนวนตำแหน่งที่ควรเลื่อน Pattern สำหรับแต่ละตำแหน่ง
• border[]: Border array (Longest proper prefix that is also suffix)

อัลกอริทึม (Pseudocode)

fullSuffixMatch(shift, border, pattern)
  n = pattern.length
  i = n, j = n+1
  border[i] = j
  while i > 0:
    while j <= n AND pattern[i-1] != pattern[j-1]:
      if shift[j] == 0: shift[j] = j - i
      j = border[j]
    i--; j--
    border[i] = j

partialSuffixMatch(shift, border, pattern)
  n = pattern.length
  j = border[0]
  for i = 0 to n-1:
    if shift[i] == 0: shift[i] = j
    if i == j: j = border[j]

searchPattern(text, pattern)
  build shift[] and border[] using above functions
  shift = 0
  while shift <= text.length - pattern.length:
    j = pattern.length - 1
    while j >= 0 AND pattern[j] == text[shift+j]: j--
    if j < 0:
      report match at shift
      shift += shift[0]
    else:
      shift += shift[j+1]

ตัวอย่างโค้ด C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void fullSuffixMatch(vector<int> &shift, vector<int> &border, string pattern) {
    int n = pattern.size();
    int i = n, j = n + 1;
    border[i] = j;
    while (i > 0) {
        while (j <= n && pattern[i-1] != pattern[j-1]) {
            if (shift[j] == 0) shift[j] = j - i;
            j = border[j];
        }
        i--; j--;
        border[i] = j;
    }
}

void partialSuffixMatch(vector<int> &shift, vector<int> &border, string pattern) {
    int n = pattern.size();
    int j = border[0];
    for (int i = 0; i < n; i++) {
        if (shift[i] == 0) shift[i] = j;
        if (i == j) j = border[j];
    }
}

void searchPattern(string text, string pattern) {
    int n = pattern.size(), m = text.size();
    vector<int> shift(n+1, 0), border(n+1, 0);

    fullSuffixMatch(shift, border, pattern);
    partialSuffixMatch(shift, border, pattern);

    int shiftPos = 0;
    while (shiftPos <= m - n) {
        int j = n - 1;
        while (j >= 0 && pattern[j] == text[shiftPos + j]) j--;
        if (j < 0) {
            cout << "Pattern found at position: " << shiftPos << endl;
            shiftPos += shift[0];
        } else {
            shiftPos += shift[j+1];
        }
    }
}

int main() {
    string text = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    searchPattern(text, pattern);
}

ความซับซ้อน

• Preprocessing: O(m) โดย m = pattern length
• Searching: O(n/m) Best case, O(n·m) Worst case
• Space: O(m)

สรุป Boyer-Moore

รวม Bad Character + Good Suffix → เลื่อน Pattern ตามค่าสูงสุดของทั้งสอง Heuristic ทำให้ข้ามตัวอักษรได้มาก → เร็วมากในทางปฏิบัติ