Thuật toán Horspool (Boyer-Moore-Horspool)

Đặc điểm chính

Ý tưởng

Boyer-Moore dùng hai quy tắc dịch chuyển (bad-character và good-suffix) và lấy giá trị lớn hơn. Horspool nhận thấy rằng chỉ riêng quy tắc bad-character, nếu áp dụng một cách đơn giản hoá, đã mang lại hiệu năng thực nghiệm rất tốt, trong khi bảng good-suffix — vốn phức tạp hơn để xây dựng — chỉ đóng góp cải thiện không đáng kể trong đa số trường hợp thực tế (nhất là với bảng chữ cái lớn như văn bản tiếng Anh hay mã nguồn).

Điểm mấu chốt của đơn giản hoá: thay vì tính bad-character dựa trên đúng ký tự gây ra sai lệch (có thể nằm ở bất kỳ đâu trong cửa sổ), Horspool luôn dùng ký tự văn bản tại vị trí cuối cùng của cửa sổ để tra bảng dịch chuyển — bất kể việc so sánh chi tiết trong cửa sổ phát hiện lệch ở đâu. Nhờ đó chỉ cần một bảng bad-character duy nhất và không cần bảng good-suffix, giúp cài đặt cực kỳ gọn nhẹ mà tốc độ trung bình vẫn rất cao.

Mô tả chi tiết

Bảng bad-character bmBc: xây dựng giống hệt Boyer-Moore — với mỗi ký tự c của bảng chữ cái, bmBc[c] là khoảng cách từ lần xuất hiện cuối cùng của c trong x[0..m-2] (không tính ký tự cuối mẫu) đến cuối mẫu; nếu c không xuất hiện trong đoạn đó, giá trị là m.

Pha tìm kiếm: tại mỗi cửa sổ ở vị trí j, trước tiên kiểm tra xem toàn bộ mẫu có khớp với y[j..j+m-1] hay không (thứ tự so sánh không quan trọng về mặt đúng đắn, thường cài đặt so từ đầu hoặc từ cuối cửa sổ để tận dụng việc đã đọc ký tự cuối). Bất kể kết quả so khớp là gì (khớp hay không), bước dịch tiếp theo luôn được tính từ ký tự văn bản c = y[j+m-1] (ký tự cuối cửa sổ hiện tại, không phải ký tự gây lệch): j += bmBc[c].

Vì sao cách làm đơn giản này vẫn an toàn (không bỏ sót xuất hiện)? Nếu c không xuất hiện ở đâu trong x[0..m-2], thì bất kỳ cách canh cửa sổ nào khiến c rơi vào giữa mẫu (trừ vị trí cuối) đều chắc chắn không khớp, nên có thể dịch hẳn qua khỏi c. Nếu c xuất hiện ở vị trí nào đó trong x[0..m-2], dịch tới đúng lần xuất hiện gần cuối nhất của nó là bước tối thiểu để hy vọng canh c (nay đóng vai trò một ký tự giữa mẫu) khớp trở lại — đây chính xác là ý nghĩa gốc của bad-character shift, chỉ khác là ta luôn tra theo ký tự ở cuối cửa sổ thay vì ký tự gây lệch thực sự. Vì ký tự cuối cửa sổ luôn được đọc dù kết quả so khớp thế nào (nó là một phần của mẫu cần kiểm tra), việc dùng nó để tra bảng không tốn thêm chi phí đọc dữ liệu.

Đánh đổi: vì bỏ qua thông tin good-suffix, trên một số mẫu có cấu trúc lặp đặc biệt (ví dụ mẫu gồm toàn một ký tự lặp lại nhiều lần), Horspool có thể suy biến về độ phức tạp O(mn) rõ ràng hơn Boyer-Moore gốc. Tuy nhiên trên dữ liệu thực tế với bảng chữ cái vừa hoặc lớn, hiệu năng trung bình vẫn vượt trội nhờ tính đơn giản và ít phép tính phụ trong vòng lặp chính.

Cài đặt bằng C

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

#define ASIZE 256

/* Tien xu ly bad-character: giong het Boyer-Moore */
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 search(char *x, int m, char *y, int n) {
    int j, bmBc[ASIZE];
    char c;

    preBmBc(x, m, bmBc);

    j = 0;
    while (j <= n - m) {
        c = y[j + m - 1];
        if (x[m - 1] == c && memcmp(x, y + j, m - 1) == 0)
            printf("Tim thay tai vi tri %d\n", j);
        /* Buoc dich luon tra theo ky tu cuoi cua so, bat ke ket qua so khop */
        j += bmBc[(unsigned char) c];
    }
}

Ví dụ minh họa

Xét lại x = "GCAGAGAG" (m = 8) trên y = "GCATCGCAGAGAGTATACAGTACG" (n = 24).

Bảng bad-character (giống Boyer-Moore vì cách xây dựng không đổi):

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

Diễn biến các lần thử đầu tiên (dịch luôn tra theo y[j+m-1], ký tự cuối cửa sổ):

So với Boyer-Moore đầy đủ (dịch 1, 4, [khớp], 4, 7 — tổng 4 lần thử sau khớp), Horspool cần nhiều lần thử hơn ở đoạn cuối (j = 5, 7, 8, 16) vì luôn tra bad-character theo ký tự cuối cửa sổ thay vì tận dụng thêm good-suffix — minh chứng rõ cho đánh đổi giữa độ đơn giản và bước dịch tối ưu.

Tài liệu tham khảo