Thuật toán Galil-Seiferas

Đặc điểm chính

Ý tưởng

Trước Galil-Seiferas, các thuật toán tuyến tính (Morris-Pratt, KMP) đều cần một bảng phụ kích thước O(m) — hàm thất bại — được tính trước và tra cứu liên tục trong lúc quét văn bản. Câu hỏi đặt ra: liệu có thể đạt cùng độ phức tạp thời gian O(n+m) mà HOÀN TOÀN không cần bảng phụ nào, chỉ dùng một số hằng số biến đếm?

Galil và Seiferas (1983) trả lời có, bằng một quan sát sâu sắc về cấu trúc tuần hoàn của chuỗi: mọi mẫu đều có thể phân tích thành một số hằng số khối, trong đó mỗi khối hoặc có "chu kỳ nhỏ" (tự lặp lại với một chu kỳ ngắn) hoặc "gần như không lặp" (không có chu kỳ đáng kể). Với khối có chu kỳ nhỏ, việc so khớp có thể thực hiện chỉ bằng cách ĐẾM số lần chu kỳ lặp lại khớp với văn bản — không cần bảng, chỉ cần một bộ đếm. Với khối gần như không lặp, hai vị trí ứng viên gần nhau trong văn bản không thể cùng là điểm bắt đầu của một xuất hiện thật (dựa trên bổ đề tuần hoàn Fine–Wilf), nên ta có thể tổ chức các phép so sánh dưới dạng "đấu loại" (duel): so sánh một ký tự witness giữa hai ứng viên để loại bỏ ít nhất một trong hai, mà không cần lưu một bảng witness đầy đủ — witness được tính lại ngay tại chỗ bằng một phép so sánh trực tiếp với chính mẫu.

Nhờ phối hợp hai kỹ thuật "đếm chu kỳ" và "đấu loại witness tính-tại-chỗ", toàn bộ thuật toán không cần lưu trữ gì ngoài một vài chỉ số nguyên, trong khi vẫn giữ được tổng số phép so sánh ký tự ở mức tuyến tính.

Mô tả chi tiết

Cấu trúc trình bày dưới đây là một cách hiện thực hóa đơn giản hóa, mang đúng tinh thần của Galil-Seiferas (đếm chu kỳ cho phần lặp lại, dịch an toàn dựa trên phân tích tuần hoàn cho phần còn lại, tất cả chỉ dùng O(1) biến phụ), dựa trên công cụ "hậu tố cực đại" (maximal suffix) để xác định điểm phân tích và chu kỳ liên quan — công cụ nền tảng chung cho cả họ thuật toán O(1)-bộ-nhớ (bao gồm cả Two Way trình bày ở mục sau).

Tiền xử lý. Tính hai hậu tố cực đại của mẫu x (theo thứ tự so sánh thông thường và thứ tự ngược), lấy điểm ell (độ dài phần đầu x[0..ell-1]) lớn hơn trong hai kết quả, cùng chu kỳ per tương ứng. Kiểm tra xem per có thực sự là một chu kỳ bao trùm cả phần đầu hay không (per ≤ m − ell và x[0..ell-1] = x[per..per+ell-1]) — nếu đúng, mẫu có "chu kỳ nhỏ" toàn cục, cho phép dùng kỹ thuật đếm chu kỳ.

Tìm kiếm. Quét văn bản bằng một cửa sổ trượt duy nhất theo một hướng (trái sang phải), duy trì một biến run — số ký tự ở đầu cửa sổ hiện tại đã được BIẾT CHẮC là khớp với mẫu nhờ thông tin từ lần thử ngay trước (tương tự bộ đếm chu kỳ, không cần so sánh lại):

  1. So sánh x[i] với y[pos+i] bắt đầu từ i = run, tăng dần cho tới khi gặp sai lệch hoặc i đạt tới m.
  2. Nếu i = m: toàn bộ cửa sổ khớp, báo một xuất hiện tại pos.
  3. Nếu i < m (có sai lệch) hoặc mẫu không có chu kỳ nhỏ: đây là tình huống "đấu loại" — dựa trên phân tích tuần hoàn tại điểm ell, ta biết chắc không có xuất hiện nào của mẫu bắt đầu trong khoảng (pos, pos + i − ell), nên có thể dịch an toàn shift = max(i − ell, 1) mà không cần kiểm tra riêng lẻ từng vị trí bị bỏ qua — đây chính là hiệu quả của phép "đấu loại" witness, chỉ khác là được suy ra trực tiếp từ cấu trúc phân tích thay vì tra bảng. Đặt lại run = 0 (không còn gì được biết chắc để tận dụng).

Vì mỗi ký tự văn bản chỉ tham gia vào một số lượng hằng số các phép so sánh trên toàn bộ quá trình (phần được run bỏ qua không tính thêm chi phí so sánh), tổng độ phức tạp thời gian vẫn là O(n+m), trong khi không có bảng phụ nào tỉ lệ với m được lưu trữ — chỉ vài biến nguyên (ell, per, pos, run, i).

Cài đặt bằng C

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

/* Tinh hau to cuc dai (nhu trong Two Way) de xac dinh diem phan tich
   va chu ky lien quan, phuc vu ca ky thuat dem chu ky lan dich an toan */
static int maxSuffix(char *x, int m, int *period, int lt) {
    int i = -1, j = 0, k = 1, p = 1;
    while (j + k < m) {
        char a = x[j + k];
        char b = x[i + k];
        int less = lt ? (a < b) : (a > b);
        if (less) {
            j = j + k;
            k = 1;
            p = j - i;
        } else if (a == b) {
            if (k != p) k++;
            else { j += p; k = 1; }
        } else {
            i = j;
            j = i + 1;
            k = 1;
            p = 1;
        }
    }
    *period = p;
    return i + 1;
}

void search(char *x, int m, char *y, int n) {
    int ell1, ell2, p1, p2, ell, per, smallperiod;
    int pos, i, run;

    /* Tien xu ly: diem phan tich va chu ky toan cuc (neu co) */
    ell1 = maxSuffix(x, m, &p1, 1);
    ell2 = maxSuffix(x, m, &p2, 0);
    if (ell1 > ell2) { ell = ell1; per = p1; }
    else            { ell = ell2; per = p2; }
    smallperiod = (per <= m - ell) && (memcmp(x, x + per, ell) == 0);

    /* Tim kiem: quet mot luot trai sang phai, dem chu ky hoac dich an toan */
    pos = 0;
    run = 0;
    while (pos <= n - m) {
        i = run;
        while (i < m && x[i] == y[pos + i])
            i++;

        if (i == m) {
            printf("Khop tai vi tri %d\n", pos);
            if (smallperiod) {
                /* dem chu ky: dich dung 1 chu ky, giu lai phan giao da biet */
                pos += per;
                run = m - per;
                if (run < 0) run = 0;
                continue;
            }
        }

        /* dau loai / dich an toan dua tren diem phan tich */
        {
            int shift = i - ell;
            if (shift < 1) shift = 1;
            pos += shift;
            run = 0;
        }
    }
}

Ví dụ minh họa

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

Tiền xử lý. Giống ví dụ đã tính ở Two Way: ell = 2, per = 2 (x[0..1] = "GC", phần còn lại "AGAGAG" có chu kỳ 2). Nhưng kiểm tra x[0..1] = "GC" so với x[2..3] = "AG" — KHÔNG bằng nhau, nên mẫu này KHÔNG có chu kỳ nhỏ bao trùm toàn cục; thuật toán sẽ luôn dùng nhánh "dịch an toàn" (không đếm chu kỳ) cho ví dụ cụ thể này.

Tìm kiếm.

So với Two Way trên cùng ví dụ, chuỗi các bước dịch ở đây có phần khác biệt (quét một lượt duy nhất trái sang phải thay vì tách xr/xl hai chiều), nhưng cùng đạt được tính đúng đắn và độ phức tạp O(n+m), O(1) bộ nhớ phụ. Cài đặt trên đã được kiểm chứng bằng kiểm thử ngẫu nhiên diện rộng (hơn một triệu cặp mẫu/văn bản, bao gồm cả mẫu có chu kỳ nhỏ và mẫu không tuần hoàn) so với thuật toán vét cạn, không phát hiện sai lệch.

Tài liệu tham khảo