Thuật toán Smith

Đặc điểm chính

Ý tưởng

Smith quan sát rằng hai heuristic bad-character phổ biến đôi khi cho bước dịch khác nhau, và không cái nào luôn thắng cái nào. Horspool dùng ký tự văn bản thẳng hàng với ký tự CUỐI của mẫu, tức y[j+m-1]. Quick Search (Sunday) dùng ký tự NGAY SAU cửa sổ, tức y[j+m]. Ý tưởng của Smith đơn giản mà hiệu quả: tính cả hai bước dịch rồi lấy giá trị lớn hơn. Vì cả hai bước dịch đều "an toàn" (không bỏ sót lần xuất hiện nào), lấy max vẫn an toàn nhưng luôn dịch xa ít nhất bằng cái tốt hơn trong hai heuristic.

Mô tả chi tiết

Thuật toán dùng hai bảng tiền xử lý:

Bảng Horspool bmBc. Với mỗi ký tự a: bmBc[a] bằng khoảng cách từ lần xuất hiện cuối của a trong m-1 ký tự đầu mẫu tới cuối mẫu, hoặc m nếu a không xuất hiện ở đó. Bảng này tra bằng y[j+m-1]. Miền giá trị: từ 1 đến m.

Bảng Quick Search qsBc. Với mỗi ký tự a: qsBc[a] bằng khoảng cách từ lần xuất hiện cuối của a trong TOÀN BỘ mẫu tới vị trí ngay sau mẫu, cụ thể m - i với i là chỉ số lớn nhất mà x[i] = a; nếu a không có trong mẫu thì bằng m + 1. Bảng này tra bằng y[j+m] — ký tự ngay sau cửa sổ. Miền giá trị: từ 1 đến m + 1.

Tại mỗi cửa sổ j, ta so khớp mẫu với y[j..j+m-1]. Nếu khớp, báo một lần xuất hiện. Bất kể kết quả, dịch cửa sổ đi:

shift = max( bmBc[y[j+m-1]] , qsBc[y[j+m]] )

Vì qsBc đọc y[j+m], khi cửa sổ ở sát cuối văn bản ta cần y[n] truy cập được — với chuỗi C kết thúc bằng ký tự \0 thì điều này tự thỏa mãn (và \0 thường không nằm trong mẫu nên qsBc trả về m + 1).

Cài đặt bằng C

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

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

/* Bảng bad-character kiểu Horspool: dựa trên y[j + m - 1] */
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;
}

/* Bảng bad-character kiểu Quick Search: dựa trên y[j + m] */
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;
}

/* Lưu ý: y[n] phải đọc được (chuỗi C kết thúc bằng '\0' là đủ). */
void search(char *x, int m, char *y, int n) {
    int j, bmBc[ASIZE], qsBc[ASIZE];

    /* Tiền xử lý */
    preBmBc(x, m, bmBc);
    preQsBc(x, m, qsBc);

    /* Tìm kiếm */
    j = 0;
    while (j <= n - m) {
        if (memcmp(x, y + j, m) == 0)
            printf("Khop tai vi tri %d\n", j);
        j += MAX(bmBc[(unsigned char) y[j + m - 1]],
                 qsBc[(unsigned char) y[j + m]]);
    }
}

Ví dụ minh họa

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

Bảng Horspool (m-1 = 7 ký tự đầu GCAGAGA): bmBc[A] = 1, bmBc[G] = 2, bmBc[C] = 6, còn lại 8.
Bảng Quick Search (toàn bộ mẫu): qsBc[G] = 1 (G ở vị trí cuối), qsBc[A] = 2, qsBc[C] = 7, còn lại 9.

Bước cuối cho thấy lợi ích rõ: một mình Horspool chỉ dịch 2, nhưng nhờ lấy max với Quick Search ta nhảy hẳn 9 vị trí.

Tài liệu tham khảo