Thuật toán Galil-Giancarlo

Đặc điểm chính

Ý tưởng

Colussi đã giảm số phép so sánh bằng cách khéo léo chọn thứ tự so các vị trí, nhưng vẫn "quên" một dạng thông tin: khi mẫu bắt đầu bằng một loạt ký tự giống nhau (ví dụ mẫu aac… bắt đầu bằng hai chữ a), sau một lần thử thành công một phần, ta thường đã biết chắc một đoạn văn bản gồm toàn ký tự x[0]. Trong lần thử kế tiếp, thay vì so lại từng ký tự của đoạn đó, ta có thể "quét nhanh" để kéo dài loạt ký tự và bỏ qua các so sánh thừa.

Đặt ℓ là chỉ số sao cho x[0] = x[1] = … = x[ℓ] nhưng x[ℓ+1] ≠ x[0] — nghĩa là mẫu mở đầu bằng loạt (ℓ+1) ký tự x[0]. Galil-Giancarlo phân biệt hai chế độ:

Với mẫu là lũy thừa của một ký tự (x = a^m), bài toán suy biến thành đếm loạt ký tự và được xử lý riêng bằng một vòng lặp đơn giản.

Mô tả chi tiết

Tiền xử lý dùng lại toàn bộ bảng của Colussi (h, shift, nxt, và nd), cộng thêm việc tính ℓ.

Trong pha tìm kiếm ta duy trì thêm cờ heavy và biến last:

Khi heavy bật và ta đang ở đầu mẫu (i = 0):

  1. Biết y[j..last] toàn là x[0], ta đặt độ dài loạt k = last − j + 1 rồi tiếp tục quét y[j+k], y[j+k+1], … chừng nào còn bằng x[0].
  2. Nếu loạt quá ngắn (k ≤ ℓ) hoặc ký tự dừng y[j+k] khác x[ℓ+1]: không thể khớp bắt đầu trong loạt này, ta nhảy cửa sổ tới j + k + 1.
  3. Nếu ngược lại: căn chỉnh cửa sổ để phần đầu mẫu (ℓ+1 ký tự x[0] rồi x[ℓ+1]) khớp với cuối loạt, đặt i = 1 và tiếp tục ở chế độ nhẹ.

Khi heavy tắt, mỗi lần thử diễn ra hệt như Colussi; sau đó ta tính lại heavy dựa trên việc lần thử vừa rồi có bước sang pha hai và cửa sổ mới có còn nằm trong vùng đã khớp không.

Cài đặt bằng C

#include <stdio.h>
#include <stdlib.h>

/* dùng lại preColussi ở bài Colussi */
int preColussi(char *x, int m, int h[], int nxt[], int shift[]);

void search(char *x, int m, char *y, int n) {
    int i, j, k, ell, last, nd, heavy, phase2;
    int *h, *nxt, *shift;

    /* độ dài loạt ký tự đầu */
    for (ell = 0; ell + 1 < m && x[ell + 1] == x[0]; ++ell);

    if (ell == m - 1) {                 /* x = a^m : đếm loạt trực tiếp */
        k = 0;
        for (j = 0; j < n; ++j) {
            if (y[j] == x[0]) {
                ++k;
                if (k >= m) printf("Tim thay tai vi tri %d\n", j - m + 1);
            } else k = 0;
        }
        return;
    }

    h     = (int *) malloc((m + 1) * sizeof(int));
    nxt   = (int *) malloc((m + 1) * sizeof(int));
    shift = (int *) malloc((m + 1) * sizeof(int));
    nd = preColussi(x, m, h, nxt, shift);

    i = j = heavy = 0;
    last = -1;
    while (j + m <= n) {
        if (heavy && i == 0) {
            /* biết y[j..last] = x[0] lặp lại; kéo dài loạt */
            k = last - j + 1;
            while (j + k < n && y[j + k] == x[0]) ++k;
            if (j + k >= n) break;
            if (k <= ell || y[j + k] != x[ell + 1]) {
                j += k + 1;
                last = j - 1;
                i = 0;
            } else {
                j = j + k - ell - 1;
                last = j + ell + 1;
                i = 1;
            }
            heavy = 0;
        } else {
            while (i < m && last < j + h[i] && x[h[i]] == y[j + h[i]])
                ++i;
            if (i >= m || last >= j + h[i]) {
                printf("Tim thay tai vi tri %d\n", j);
                i = m;
            }
            phase2 = (i > nd);
            if (phase2) last = j + m - 1;
            j += shift[i];
            i = nxt[i];
            heavy = (phase2 && j <= last);
        }
    }
    free(h); free(nxt); free(shift);
}

Ví dụ minh họa

Với mẫu x = "GCAGAGAG", do x[0]=G khác ngay x[1]=C nên ℓ = 0: mẫu không mở đầu bằng loạt ký tự lặp, cờ heavy không mang lại lợi ích và thuật toán chạy y hệt Colussi.

Để thấy rõ chế độ "nặng", ta lấy mẫu x = "aacaa" (m = 5, ℓ = 1, tức mở đầu bằng hai chữ a rồi x[2]=c) trên văn bản y = "aaaaacaacaaa" (n = 12).

Nhờ khai thác loạt a đã biết, thuật toán tránh so lại những ký tự đã xác nhận, giữ tổng số so sánh không vượt 4n/3.

Tài liệu tham khảo