Thuật toán Quick Search (Sunday)

Đặc điểm chính

Ý tưởng

Horspool tính bước dịch dựa trên ký tự cuối cùng của cửa sổ hiện tại. Daniel Sunday nhận ra rằng ta có thể khai thác thêm một ký tự nữa mà không tốn thêm chi phí đáng kể: ký tự văn bản ngay sau cửa sổ hiện tại, tức y[j+m]. Ký tự này chưa hề tham gia vào cửa sổ hiện tại, nhưng nó chắc chắn sẽ là một phần của cửa sổ kế tiếp (vì bước dịch tối thiểu là 1).

Lý do dùng ký tự này cho bước dịch lớn hơn: nếu y[j+m] không xuất hiện ở bất kỳ đâu trong toàn bộ mẫu x (kể cả ký tự cuối x[m-1], khác với Horspool chỉ xét x[0..m-2]), thì mọi cách dịch cửa sổ sao cho y[j+m] rơi vào bên trong cửa sổ mới đều chắc chắn thất bại — nên có thể dịch hẳn m + 1 vị trí, vượt qua toàn bộ khả năng đó chỉ trong một bước. Đây là bước dịch lớn nhất có thể trong toàn bộ họ thuật toán dựa trên bad-character, và giải thích vì sao Quick Search thường vượt trội khi bảng chữ cái lớn (xác suất một ký tự bất kỳ không xuất hiện trong mẫu ngắn là khá cao).

Mô tả chi tiết

Bảng bad-character qsBc: khác biệt so với Boyer-Moore/Horspool ở chỗ bảng này tính trên toàn bộ mẫu x[0..m-1] (bao gồm cả ký tự cuối), không bỏ sót vị trí nào. Với mỗi ký tự c của bảng chữ cái: qsBc[c] là khoảng cách từ lần xuất hiện cuối cùng của c trong toàn mẫu đến hết mẫu, cộng thêm 1 (vì ta đang xét ký tự nằm ngay sau cửa sổ, ứng với vị trí ảo m tính từ đầu cửa sổ). Nếu c không xuất hiện trong mẫu, qsBc[c] = m + 1.

Pha tìm kiếm: tại cửa sổ vị trí j, so sánh mẫu với y[j..j+m-1] theo thứ tự tuỳ ý (không ảnh hưởng kết quả). Nếu khớp, báo một xuất hiện. Bất kể khớp hay không, nếu cửa sổ chưa chạm mép phải văn bản (j + m < n), tra ký tự c = y[j+m] — ký tự ngay sau cửa sổ — và dịch j += qsBc[c]. Nếu cửa sổ đã chạm mép phải (không còn ký tự sau cửa sổ để tra), thuật toán dừng.

Vì bảng qsBc được tính trên toàn bộ mẫu (kể cả x[m-1]), giá trị nhỏ nhất có thể của qsBc[c] là 1 (khi c = x[m-1]), và giá trị lớn nhất là m + 1 (khi c không xuất hiện trong mẫu) — lớn hơn hẳn giới hạn m của bad-character kiểu Horspool. Đây chính là điểm khác biệt cốt lõi, giúp Quick Search đạt bước dịch trung bình lớn hơn, đặc biệt hiệu quả khi m nhỏ so với σ (lúc đó xác suất qsBc[c] = m+1 càng cao).

Cài đặt bằng C

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

#define ASIZE 256

/* Tien xu ly bad-character kieu Quick Search: xet toan bo mau, gia tri mac
   dinh la m + 1 (ung voi ky tu ngay sau cua so khong xuat hien trong mau). */
void preQsBc(char *x, int m, int qsBc[]) {
    int i;
    for (i = 0; i < ASIZE; ++i)
        qsBc[i] = m + 1;
    for (i = 0; i < m; ++i)
        qsBc[(unsigned char) x[i]] = m - i;
}

void search(char *x, int m, char *y, int n) {
    int j, qsBc[ASIZE];

    preQsBc(x, m, qsBc);

    j = 0;
    while (j <= n - m) {
        if (memcmp(x, y + j, m) == 0)
            printf("Tim thay tai vi tri %d\n", j);
        if (j + m >= n)
            break;
        /* Tra bang theo ky tu NGAY SAU cua so, khong phai ky tu cuoi cua so */
        j += qsBc[(unsigned char) y[j + m]];
    }
}

Ví dụ minh họa

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

Bảng bad-character kiểu Quick Search (tính trên toàn bộ mẫu, kể cả ký tự cuối):

ký tự A C G T
qsBc 2 7 1 9

(Ví dụ qsBc['G'] = 1 vì G xuất hiện ở chính vị trí cuối mẫu x[7]; qsBc['T'] = 9 = m+1 vì T không xuất hiện trong mẫu.)

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

Chỉ với 5 lần thử cửa sổ (ít hơn cả Boyer-Moore đầy đủ trong ví dụ này nhờ bước nhảy qsBc['T'] = 9 rất lớn ngay sau khi tìm thấy xuất hiện), Quick Search minh hoạ rõ lợi thế của việc khai thác thêm một ký tự nằm ngoài cửa sổ hiện tại.

Tài liệu tham khảo