Thuật toán Reverse Colussi

Đặc điểm chính

Ý tưởng

Reverse Colussi là sự lai ghép giữa hai dòng tư tưởng: cách "so sánh theo thứ tự thông minh" của Colussi (áp dụng cho họ Morris-Pratt, so trái sang phải) và cách "so cuối mẫu trước, dịch xa" của Boyer-Moore. Thay vì luôn so sánh mẫu với cửa sổ theo đúng thứ tự từ cuối về đầu, Reverse Colussi tính trước — chỉ dựa vào cấu trúc chu kỳ nội tại của mẫu — một hoán vị các vị trí h[0], h[1], ..., h[m-1] (với h[0] = m-1, tức ký tự cuối mẫu luôn được so đầu tiên, giữ vai trò "bộ lọc nhanh" kiểu Boyer-Moore-Horspool) sao cho việc dừng sớm ở bất kỳ vị trí nào trong thứ tự đó đều cho phép suy ra một bước dịch an toàn, đủ lớn để tổng chi phí so sánh toàn cục không vượt quá 2n.

Nói cách khác, nếu Colussi nguyên bản chia vị trí mẫu thành nohole/hole và so hai đợt (tăng dần rồi giảm dần), Reverse Colussi tổng quát hoá thành một thứ tự duy nhất được tính tối ưu qua phân tích chu kỳ của mẫu, kết hợp thêm quy tắc bad-character mở rộng để tăng tốc bước "lọc nhanh" ban đầu.

Mô tả chi tiết

Xây thứ tự so sánh h: dựa trên các bảng chu kỳ tương tự Colussi — hmin[k] (vị trí dừng khi tìm chu kỳ độ dài k), kmin[i] (chu kỳ nhỏ nhất ứng với mỗi vị trí, đánh dấu các vị trí có tính chất chu kỳ đặc biệt), và rmin[i] (chu kỳ nhỏ nhất lớn hơn i). Các vị trí có kmin khác 0 được xếp trước theo một thứ tự do hmin/kmin quyết định (những vị trí "giàu thông tin chu kỳ" nhất được ưu tiên so sớm), các vị trí còn lại xếp sau. Vị trí m-1 (ký tự cuối mẫu) luôn được đặt ở đầu bảng h để đóng vai trò lọc nhanh kiểu bad-character trước khi đi vào so sánh chi tiết theo thứ tự đã tính.

Bảng bước dịch an toàn rcGs[r]: với mỗi "hạng" dừng r (nghĩa là các vị trí h[0], ..., h[r-1] đã so khớp, còn h[r] bị lệch hoặc r = m khi khớp toàn bộ mẫu), rcGs[r] là bước dịch nhỏ nhất đảm bảo không bỏ sót bất kỳ xuất hiện nào của mẫu: với bước dịch s = rcGs[r], mọi vị trí đã biết khớp h[t] (t < r) mà còn nằm trong mẫu sau khi dịch (h[t] >= s) đều phải tiếp tục khớp (x[h[t]-s] = x[h[t]]), và nếu có vị trí lệch h[r] còn nằm trong mẫu sau khi dịch thì tại đó không được khớp (x[h[r]-s] != x[h[r]]) — nếu không, một xuất hiện tiềm năng có thể bị bỏ qua. Giá trị rcGs[r] được xác định là bước dịch nhỏ nhất thỏa hai điều kiện trên, tính được ngay trong pha tiền xử lý bằng cách duyệt thử các bước dịch tăng dần từ 1, do đó góp phần vào độ phức tạp O(m²) của tiền xử lý.

Bảng bad-character mở rộng rcBc[c][s]: khác với Boyer-Moore (chỉ phụ thuộc ký tự gây lệch), ở đây bước dịch bad-character còn phụ thuộc vào bước dịch hiện hành s đang dùng để lọc nhanh (vì việc lọc nhanh lặp lại nhiều lần liên tiếp trước khi vào so sánh chi tiết, mỗi lần với một bước dịch tiềm năng khác nhau). rcBc[c][s] cho biết, khi ký tự cuối cửa sổ là c và bước dịch đang dùng để lọc nhanh là s, bước dịch tiếp theo nên là bao nhiêu để tới lần xuất hiện gần nhất (nhìn từ phải) của c trong mẫu mà khoảng cách so với cuối mẫu tối thiểu bằng s.

Pha tìm kiếm: tại mỗi vị trí cửa sổ, trước tiên lặp "lọc nhanh": chừng nào ký tự cuối cửa sổ y[j+m-1] khác x[m-1], tra rcBc[y[j+m-1]][s] để có bước dịch mới và dịch cửa sổ, không cần đọc thêm ký tự nào khác. Khi ký tự cuối cửa sổ đã trùng x[m-1], chuyển sang so sánh chi tiết theo đúng thứ tự h[1], h[2], ... cho tới khi lệch ở hạng r (hoặc khớp hết, r = m); báo xuất hiện nếu r = m, rồi dịch cửa sổ theo rcGs[r].

Cài đặt bằng C

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

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

/* Buoc dich an toan nho nhat khi dung so sanh o hang r: h[0..r-1] da khop,
   h[r] le (hoac r = m neu khop het). Duyet tang dan s = 1, 2, ... va kiem
   dieu kien an toan truc tiep tren mau x. */
static int safeShift(char *x, int m, int *h, int r) {
    int s, t, ok, q, p;
    p = (r < m) ? h[r] : -1;
    for (s = 1; s <= m; ++s) {
        ok = 1;
        for (t = 0; t < r && ok; ++t) {
            q = h[t];
            if (q >= s && x[q - s] != x[q])
                ok = 0;
        }
        if (ok && p >= 0 && p >= s && x[p - s] == x[p])
            ok = 0;
        if (ok)
            return s;
    }
    return m;
}

void preRc(char *x, int m, int h[], int rcBc[ASIZE][XSIZE], int rcGs[]) {
    int a, i, j, k, q, r, s;
    int hmin[XSIZE], kmin[XSIZE], link[XSIZE], locc[ASIZE], rmin[XSIZE];

    /* link/locc: chuoi cac vi tri xuat hien (tinh nguoc) cua tung ky tu trong x[0..m-2] */
    for (a = 0; a < ASIZE; ++a)
        locc[a] = -1;
    link[0] = -1;
    for (i = 0; i < m - 1; ++i) {
        link[i + 1] = locc[(unsigned char) x[i]];
        locc[(unsigned char) x[i]] = i;
    }

    /* rcBc[a][s]: buoc dich khi ky tu cuoi cua so la a, dang loc nhanh voi buoc s */
    for (a = 0; a < ASIZE; ++a)
        for (s = 1; s <= m; ++s) {
            i = locc[a];
            j = link[m - s];
            while (i - j != s && j >= 0)
                if (i - j > s) i = link[i + 1];
                else           j = link[j + 1];
            while (i - j > s)
                i = link[i + 1];
            rcBc[a][s] = m - i - 1;
        }

    /* hmin/kmin: phan tich chu ky cua mau, dung de xac dinh thu tu so sanh h */
    k = 1;
    i = m - 1;
    while (k <= m) {
        while (i - k >= 0 && x[i - k] == x[i])
            --i;
        hmin[k] = i;
        q = k + 1;
        while (q <= m && hmin[q - k] - (q - k) > i) {
            hmin[q] = hmin[q - k];
            ++q;
        }
        i += (q - k);
        k = q;
        if (i >= m)
            i = m - 1;
    }
    memset(kmin, 0, (m + 1) * sizeof(int));
    for (k = m; k > 0; --k)
        kmin[hmin[k]] = k;
    r = 0;
    for (i = m - 1; i >= 0; --i) {
        if (hmin[i + 1] == i)
            r = i + 1;
        rmin[i] = (kmin[i] == 0) ? r : 0;
    }

    /* Xay thu tu so sanh h: h[0] = m-1 (loc nhanh), roi cac vi tri "giau chu ky"
       theo hmin/kmin, cuoi cung la cac vi tri con lai */
    h[0] = m - 1;
    i = 1;
    for (k = 1; k <= m; ++k)
        if (hmin[k] != m - 1 && kmin[hmin[k]] == k)
            h[i++] = hmin[k];
    for (j = m - 2; j >= 0; --j)
        if (kmin[j] == 0)
            h[i++] = j;

    /* rcGs[r]: buoc dich an toan khi dung o hang r (1..m) */
    for (r = 1; r <= m; ++r)
        rcGs[r] = safeShift(x, m, h, r);
}

void search(char *x, int m, char *y, int n) {
    int i, j, s;
    static int rcBc[ASIZE][XSIZE];
    int rcGs[XSIZE], h[XSIZE];

    preRc(x, m, h, rcBc, rcGs);

    j = 0;
    s = m;
    while (j <= n - m) {
        /* Loc nhanh bang ky tu cuoi cua so */
        while (j <= n - m && x[m - 1] != y[j + m - 1]) {
            s = rcBc[(unsigned char) y[j + m - 1]][s];
            j += s;
        }
        if (j > n - m)
            break;

        /* So sanh chi tiet theo thu tu h[1..m-1] */
        for (i = 1; i < m && x[h[i]] == y[j + h[i]]; ++i)
            ;
        if (i >= m)
            printf("Tim thay tai vi tri %d\n", j);
        s = rcGs[i];
        j += s;
    }
}

Ví dụ minh họa

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

Thứ tự so sánh tính được: h = [7, 3, 5, 6, 4, 2, 1, 0] (vị trí 7 — ký tự cuối — luôn được lọc nhanh đầu tiên). Một phần bảng bước dịch an toàn: rcGs[1] = 2, rcGs[2] = 4, rcGs[3..8] = 7.

Diễn biến các lần thử đầu tiên:

Có thể thấy vai trò hai tầng rõ rệt: bước lọc nhanh (so ký tự cuối cửa sổ, giống Horspool) loại nhanh phần lớn các vị trí sai, còn khi ký tự cuối đã khớp thì thứ tự h được tính sẵn giúp phát hiện lệch ở ngay hạng đầu tiên (h[1] = 3) tại các cửa sổ j = 1, 3, 12, cho một bước dịch ổn định rcGs[1] = 2 mà không cần so thêm ký tự nào khác.

Tài liệu tham khảo