Thuật toán Tuned Boyer-Moore

Đặc điểm chính

Ý tưởng

Trong thuật toán Horspool, phần lớn thời gian chạy được tiêu tốn ở việc dịch chuyển cửa sổ khi ký tự cuối cùng của cửa sổ không khớp. Ý tưởng của Tuned Boyer-Moore là tách riêng bước "dò tìm nhanh" ký tự cuối cùng ra khỏi bước "kiểm tra khớp thật sự". Trước tiên ta chỉ liên tục dịch cửa sổ cho tới khi ký tự văn bản thẳng hàng với ký tự cuối của mẫu bằng đúng ký tự cuối đó; chỉ khi điều kiện này thỏa mãn ta mới bỏ công so khớp toàn bộ mẫu.

Để vòng dò tìm này chạy nhanh nhất có thể, người ta áp dụng hai kỹ thuật hiện thực quan trọng: (1) giãn vòng lặp (loop unrolling) ba lần để giảm chi phí kiểm tra điều kiện dừng của vòng lặp, và (2) đặt một "lính canh" (sentinel) bằng cách chép chính mẫu vào ngay sau cuối văn bản, nhờ đó vòng dò tìm luôn dừng lại một cách tự nhiên mà không cần so sánh chỉ số j với n ở mỗi bước.

Mô tả chi tiết

Thuật toán dùng một bảng bmBc giống hệt Horspool: với mỗi ký tự a của bảng chữ cái, bmBc[a] bằng khoảng cách từ lần xuất hiện cuối cùng của a trong m-1 ký tự đầu của mẫu tới cuối mẫu; nếu a không xuất hiện thì giá trị bằng m.

Điểm khác biệt nằm ở cơ chế điều khiển vòng lặp:

Khi vòng dò tìm dừng (giá trị dịch bằng 0, tức ký tự cuối đã khớp), ta thực hiện so khớp "ngây thơ" (naive) m-1 ký tự còn lại từ trái sang phải. Nếu tất cả khớp và j vẫn nằm trong văn bản thật (j < n) thì báo một lần xuất hiện. Cuối cùng dịch cửa sổ đi shift để tiếp tục.

Cài đặt bằng C

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

#define ASIZE 256

/* Bảng dịch bad-character kiểu Horspool */
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;
}

/* Lưu ý: vùng nhớ của y phải còn ít nhất m byte trống sau y[n-1]
   để chép mẫu vào làm "lính canh" (sentinel). */
void search(char *x, int m, char *y, int n) {
    int j, k, shift, bmBc[ASIZE];

    /* Tiền xử lý */
    preBmBc(x, m, bmBc);
    shift = bmBc[(unsigned char) x[m - 1]]; /* bước dịch thật của ký tự cuối */
    bmBc[(unsigned char) x[m - 1]] = 0;     /* để vòng lặp nhanh dừng lại */
    memcpy(y + n, x, m);                    /* lính canh ở cuối văn bản */

    /* Tìm kiếm */
    j = 0;
    while (j < n) {
        k = bmBc[(unsigned char) y[j + m - 1]];
        while (k != 0) {                    /* vòng lặp nhanh, giãn 3 lần */
            j += k; k = bmBc[(unsigned char) y[j + m - 1]];
            j += k; k = bmBc[(unsigned char) y[j + m - 1]];
            j += k; k = bmBc[(unsigned char) y[j + m - 1]];
        }
        if (memcmp(x, y + j, m - 1) == 0 && j < n)
            printf("Khop tai vi tri %d\n", j);
        j += shift;
    }
}

Ví dụ minh họa

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

Ký tự cuối mẫu là G. Bảng bad-character (chỉ liệt kê các ký tự có mặt trong mẫu): với 7 ký tự đầu GCAGAGA, ta có bmBc[A] = 1, bmBc[G] = 2, bmBc[C] = 6, các ký tự khác bằng 8. Do đó shift = bmBc[G] = 2, và sau đó ta gán bmBc[G] = 0.

Ký tựACGTkhác
bmBc (sau khi gán)16088

Các bước dò tìm bằng vòng lặp nhanh giúp thuật toán chỉ dừng lại ở những cửa sổ mà ký tự cuối đã trùng, tránh so khớp vô ích tại phần lớn vị trí.

Tài liệu tham khảo