Thuật toán Boyer-Moore

Đặc điểm chính

Ý tưởng

Các thuật toán kiểu vét cạn hay họ Morris-Pratt/KMP đều so sánh mẫu với văn bản theo chiều từ trái sang phải, và mỗi lần dịch cửa sổ đi tối thiểu một ký tự. Boyer và Moore quan sát rằng nếu ta so sánh theo chiều ngược lại — từ ký tự cuối mẫu trở về đầu — thì một sai lệch được phát hiện sớm ở cuối cửa sổ cho phép ta suy luận về toàn bộ đoạn văn bản nằm trong cửa sổ, kể cả phần chưa kịp so sánh (từ đầu cửa sổ tới điểm sai lệch). Từ đó có thể tính ra một bước dịch chuyển an toàn lớn hơn nhiều so với 1, đôi khi lớn tới độ dài mẫu.

Có hai nguồn thông tin độc lập để tính bước dịch: ký tự văn bản gây ra sai lệch (quy tắc bad-character), và phần hậu tố của mẫu vừa khớp được trước khi sai lệch (quy tắc good-suffix). Boyer-Moore luôn lấy bước dịch lớn nhất trong hai quy tắc, nhờ đó cửa sổ thường "nhảy" qua nhiều ký tự không cần kiểm tra.

Mô tả chi tiết

So sánh ngược: với mỗi vị trí cửa sổ j, ta so x[m-1] với y[j+m-1], rồi x[m-2] với y[j+m-2], ... cho tới khi gặp ký tự lệch tại chỉ số i (tức x[i] != y[i+j]) hoặc so hết toàn bộ mẫu (khớp).

Quy tắc bad-character (bmBc): khi so đến vị trí i mà bị lệch, ký tự văn bản c = y[i+j] gây ra sai lệch đó. Ý tưởng: dịch cửa sổ sao cho lần xuất hiện gần nhất của c trong x[0..m-2] (tính từ bên phải) được canh thẳng hàng với vị trí i trên văn bản. Bảng bmBc[c] lưu, với mỗi ký tự c của bảng chữ cái, khoảng cách từ vị trí xuất hiện cuối cùng của c trong x[0..m-2] đến cuối mẫu x[m-1]; nếu c không xuất hiện trong x[0..m-2], giá trị mặc định là m (dịch hẳn qua khỏi c). Bước dịch thực tế theo bad-character tại vị trí lệch i là bmBc[c] - (m - 1 - i), có thể âm nếu ký tự c còn xuất hiện ở bên phải i trong mẫu — khi đó ta bỏ qua và chỉ dùng quy tắc good-suffix.

Quy tắc good-suffix (bmGs): khi lệch tại i, đoạn x[i+1..m-1] (hậu tố của mẫu) đã khớp thành công với văn bản trước khi lệch xảy ra. Ta muốn dịch cửa sổ tới vị trí gần nhất mà: 1. một lần xuất hiện khác của đoạn hậu tố này trong mẫu (không đứng ngay trước một ký tự bằng x[i], để tránh lặp lại đúng sai lệch cũ) được canh khớp với đoạn văn bản đó; hoặc, nếu không có, 2. một tiền tố của mẫu trùng với một hậu tố của đoạn hậu tố khớp được canh vào đúng vị trí.

Bảng bmGs[i] lưu bước dịch tương ứng cho mỗi vị trí lệch i (và bmGs[0], dùng khi khớp toàn bộ mẫu, ứng với trường hợp 2 áp dụng cho toàn mẫu). Việc xây bmGs dựa vào bảng phụ suff[i]: độ dài của hậu tố dài nhất của x[0..i] đồng thời cũng là hậu tố của toàn mẫu x. Bảng suff được tính trong O(m) bằng kỹ thuật tương tự tính biên nhưng theo chiều ngược (so sánh mẫu với chính nó lùi từ cuối).

Bước dịch cuối cùng tại mỗi lần thử là max(bmGs[i], bmBc[c] - m + 1 + i), đảm bảo không bỏ sót xuất hiện nào (an toàn) đồng thời tận dụng được thông tin lớn nhất có thể.

Cài đặt bằng C

#include <stdio.h>
#include <string.h>

#define ASIZE 256   /* kich thuoc bang chu cai (gia su ky tu 8-bit) */
#define XSIZE 256   /* do dai mau toi da ho tro cho mang tinh toan */
#define MAX(a, b) ((a) > (b) ? (a) : (b))

/* Tien xu ly bad-character: bmBc[c] = khoang cach tu lan xuat hien
   cuoi cung cua c trong x[0..m-2] den cuoi mau; m neu c khong xuat hien. */
void preBmBc(char *x, int m, int bmBc[]) {
    int i;
    for (i = 0; i < ASIZE; ++i)
        bmBc[i] = m;
    for (i = 0; i < m - 1; ++i)
        bmBc[(unsigned char) x[i]] = m - 1 - i;
}

/* suff[i] = do dai hau to dai nhat cua x[0..i] dong thoi la hau to cua x */
void suffixes(char *x, int m, int *suff) {
    int f, g, i;
    f = 0;
    suff[m - 1] = m;
    g = m - 1;
    for (i = m - 2; i >= 0; --i) {
        if (i > g && suff[i + m - 1 - f] < i - g)
            suff[i] = suff[i + m - 1 - f];
        else {
            if (i < g)
                g = i;
            f = i;
            while (g >= 0 && x[g] == x[g + m - 1 - f])
                --g;
            suff[i] = f - g;
        }
    }
}

/* Tien xu ly good-suffix dua tren bang suff */
void preBmGs(char *x, int m, int bmGs[]) {
    int i, j, suff[XSIZE];
    suffixes(x, m, suff);

    for (i = 0; i < m; ++i)
        bmGs[i] = m;
    j = 0;
    for (i = m - 1; i >= 0; --i)
        if (suff[i] == i + 1)
            for (; j < m - 1 - i; ++j)
                if (bmGs[j] == m)
                    bmGs[j] = m - 1 - i;
    for (i = 0; i <= m - 2; ++i)
        bmGs[m - 1 - suff[i]] = m - 1 - i;
}

void search(char *x, int m, char *y, int n) {
    int i, j, bmGs[XSIZE], bmBc[ASIZE];

    preBmGs(x, m, bmGs);
    preBmBc(x, m, bmBc);

    j = 0;
    while (j <= n - m) {
        for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i)
            ;
        if (i < 0) {
            printf("Tim thay tai vi tri %d\n", j);
            j += bmGs[0];
        } else {
            j += MAX(bmGs[i], bmBc[(unsigned char) y[i + j]] - m + 1 + i);
        }
    }
}

Ví dụ minh họa

Xét mẫu x = "GCAGAGAG" (m = 8) trên văn bản y = "GCATCGCAGAGAGTATACAGTACG" (n = 24).

Bảng bad-character (chỉ liệt kê các ký tự xuất hiện trong mẫu, các ký tự khác nhận giá trị mặc định m = 8):

ký tự A C G T
bmBc 1 6 2 8

Bảng suff và bảng good-suffix bmGs (chỉ số 0..7):

i 0 1 2 3 4 5 6 7
suff[i] 1 0 0 2 0 4 0 8
bmGs[i] 7 7 7 2 7 4 7 1

Diễn biến các lần thử đầu tiên:

Chỉ với 5 lần thử cửa sổ, Boyer-Moore tìm ra duy nhất một xuất hiện tại vị trí 5, minh họa rõ khả năng dịch chuyển "nhảy cóc" nhờ hai quy tắc.

Tài liệu tham khảo