Thuật toán Turbo Boyer-Moore

Đặc điểm chính

Ý tưởng

Boyer-Moore có một điểm chưa tối ưu: khi dịch cửa sổ theo quy tắc good-suffix, phần đầu cửa sổ mới đôi khi trùng lặp với phần cuối cửa sổ cũ — tức là một số ký tự văn bản đã được so sánh (và biết là khớp) ở lần thử trước, nhưng lần thử sau lại so sánh lại từ đầu theo chiều phải sang trái, bỏ phí công sức đã bỏ ra.

Turbo Boyer-Moore (Crochemore, Czumaj, Gąsieniec, Jarominek, Lecroq, Plandowski, Rytter — cải tiến dựa trên ý tưởng "nhớ lại" quen thuộc trong họ Morris-Pratt) khắc phục bằng cách lưu lại một cặp số (u, v): u là độ dài của đoạn hậu tố đã biết chắc khớp với mẫu ở lần thử trước (gọi là factor bộ nhớ), còn vị trí tương đối của nó trong cửa sổ hiện tại được suy ra từ bước dịch vừa thực hiện. Khi so sánh ở lần thử mới chạm tới đúng ranh giới của đoạn đã nhớ, thuật toán nhảy qua toàn bộ đoạn đó mà không so sánh lại từng ký tự, vì đã có đủ căn cứ toán học để khẳng định chúng khớp.

Ngoài ra, thông tin về độ dài và vị trí đoạn nhớ còn cho phép tính thêm một bước dịch mới — turbo-shift — độc lập với bad-character và good-suffix, và bước dịch cuối cùng vẫn là giá trị lớn nhất trong ba lựa chọn. Nhờ turbo-shift, thuật toán còn tránh được kiểu "khớp lại y hệt lần trước rồi lại lệch y hệt vị trí cũ", vốn là nguyên nhân khiến Boyer-Moore gốc có thể rơi vào trường hợp xấu O(mn).

Mô tả chi tiết

Thuật toán dùng lại nguyên vẹn hai bảng bmBc và bmGs của Boyer-Moore — không cần tiền xử lý gì thêm. Phần khác biệt nằm ở pha tìm kiếm, với hai biến trạng thái mang theo qua các lần thử:

Tại một lần thử, khi so sánh lùi từ i = m-1, nếu u != 0 và con trỏ so sánh i chạm đúng ranh giới m - 1 - shift (biên của đoạn đã nhớ được dịch chuyển tương ứng), thuật toán nhảy thẳng i lùi thêm u vị trí (bỏ qua so sánh phần chắc chắn khớp).

Khi phát hiện lệch tại i (với v = m - 1 - i là độ dài hậu tố vừa khớp lần này), ba bước dịch được xét: - bad-character: như Boyer-Moore, bmBc[y[i+j]] - m + 1 + i. - good-suffix: bmGs[i]. - turbo-shift: chỉ có ý nghĩa khi đoạn nhớ u thực sự liên quan đến điểm lệch hiện tại (tức i nằm trong hoặc trước ranh giới đoạn nhớ, i <= m - 1 - shift); giá trị là u - v. Ý nghĩa: nếu đoạn nhớ dài u và lần này chỉ khớp thêm v ký tự trước khi lệch, thì vị trí lệch chắc chắn cách xa hơn u - v so với vị trí có thể xảy ra trùng khớp thực sự, nên có thể dịch an toàn ít nhất bấy nhiêu.

Bước dịch được chọn là giá trị lớn nhất trong các bước có nghĩa ở trên. Nếu bước dịch được chọn chính là bmGs[i], đoạn nhớ mới u được cập nhật thành min(m - shift, v); ngược lại (bad-character hoặc turbo-shift thắng thế), đoạn nhớ được đặt lại u = 0 vì không còn đủ căn cứ để khẳng định một đoạn khớp liên tục nào cho lần thử kế tiếp (trừ khi turbo-shift nhỏ hơn bad-character, khi đó cần đảm bảo dịch ít nhất u + 1 để không lặp lại chính điểm lệch đã dùng để tính u).

Khi khớp toàn bộ mẫu, cửa sổ dịch theo bmGs[0] như Boyer-Moore, và đoạn nhớ mới được đặt u = m - shift.

Cài đặt bằng C

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

#define ASIZE 256
#define XSIZE 256
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

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;
}

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;
        }
    }
}

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 bcShift, i, j, shift, u, v, turboShift;
    int bmGs[XSIZE], bmBc[ASIZE];

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

    j = u = 0;
    shift = m;
    while (j <= n - m) {
        i = m - 1;
        while (i >= 0 && x[i] == y[i + j]) {
            --i;
            /* Nhay qua doan nho da xac nhan khop o lan thu truoc */
            if (u != 0 && i == m - 1 - shift)
                i -= u;
        }
        if (i < 0) {
            printf("Tim thay tai vi tri %d\n", j);
            shift = bmGs[0];
            u = m - shift;
        } else {
            v = m - 1 - i;
            bcShift = bmBc[(unsigned char) y[i + j]] - m + 1 + i;
            if (u != 0 && i <= m - 1 - shift) {
                /* Doan nho lien quan truc tiep den diem lech: tinh them turbo-shift */
                turboShift = u - v;
                shift = MAX(turboShift, bcShift);
                shift = MAX(shift, bmGs[i]);
                if (shift == bmGs[i])
                    u = MIN(m - shift, v);
                else {
                    if (turboShift < bcShift)
                        shift = MAX(shift, u + 1);
                    u = 0;
                }
            } else {
                shift = MAX(bcShift, bmGs[i]);
                if (shift == bmGs[i])
                    u = MIN(m - shift, v);
                else
                    u = 0;
            }
        }
        j += shift;
    }
}

Ví dụ minh họa

Trên cùng cặp x = "GCAGAGAG" (m = 8), y = "GCATCGCAGAGAGTATACAGTACG" (n = 24), diễn biến turbo-shift là:

Vì đoạn nhớ chỉ tồn tại giữa hai lần thử liên tiếp và ví dụ này tìm ra xuất hiện khá sớm, turbo-shift không phải là số hạng lớn nhất ở bước nào trong ví dụ trên. Để thấy rõ cơ chế "nhảy qua đoạn đã nhớ" trong khi so sánh, xét một ví dụ nhỏ khác với bảng chữ nhị phân: x = "aabb" (m = 4) trên y = "ababbaaaab".

Ví dụ thứ hai cho thấy rõ: nhờ nhớ lại đoạn đã khớp, thuật toán tiết kiệm được một phép so sánh ký tự (x[2] với y[3]) mà Boyer-Moore gốc sẽ phải thực hiện lại.

Tài liệu tham khảo