Thuật toán KMP Skip Search

Đặc điểm chính

Ý tưởng

Skip Search thuần có nhược điểm: trong trường hợp xấu, cùng một đoạn văn bản có thể bị so đi so lại nhiều lần, dẫn tới O(mn). KMP Skip Search khắc phục bằng cách mượn kỹ thuật của Knuth-Morris-Pratt.

Ý tưởng cốt lõi là duy trì một bức tường wall: vị trí xa nhất trong văn bản mà ta đã từng so tới. Khi kiểm tra một ứng viên mới, ta không bao giờ so lại các ký tự nằm bên trái bức tường — chúng đã được xác nhận trước đó. Kết hợp với các bảng mpNext/kmpNext để dịch trạng thái khớp một cách nhất quán, mỗi ký tự văn bản chỉ được so đúng một số lần hằng, cho tổng thời gian tuyến tính.

Mô tả chi tiết

Cấu trúc bucket rút gọn. Thay cho danh sách liên kết, ở đây dùng hai mảng số nguyên. z[c] giữ vị trí xuất hiện phải nhất (chỉ số lớn nhất) của ký tự c trong mẫu, hoặc -1 nếu không có. list[i] liên kết vị trí i tới vị trí xuất hiện kế trước của cùng ký tự x[i] trong mẫu. Nhờ vậy, từ z[c] ta lần theo list để duyệt mọi vị trí của c mà không cần cấp phát động.

Hai bảng dịch.

Chu kỳ mẫu. per = m - kmpNext[m] là chu kỳ của mẫu, dùng để dịch tiếp sau khi tìm được một xuất hiện.

Tìm kiếm. Biến j nhảy theo bước m để tìm mốc mà y[j] xuất hiện trong mẫu (dựa vào z). Từ mốc đó ta suy ra vị trí đặt mẫu start = j - i. Hàm attempt so mẫu với văn bản nhưng bắt đầu từ bức tường (wall - start), không so lại phần đã xác nhận, rồi cập nhật wall. Khi khớp đủ m ký tự, in ra start và dịch trạng thái theo chu kỳ per. Khi lệch, ta dùng list để lấy vị trí ứng viên kế tiếp, đồng thời dùng kmpNext/mpNext để đồng bộ kmpStart sao cho không bỏ sót và cũng không so trùng. Chính sự phối hợp giữa bước nhảy Skip Search và cơ chế bức tường KMP đưa độ phức tạp xấu nhất về O(n).

Cài đặt bằng C

#include <stdio.h>

#define ASIZE 256
#define XSIZE 1024

void preMp(char *x, int m, int mpNext[]) {
    int i, j;
    i = 0;
    j = mpNext[0] = -1;
    while (i < m) {
        while (j > -1 && x[i] != x[j])
            j = mpNext[j];
        mpNext[++i] = ++j;
    }
}

void preKmp(char *x, int m, int kmpNext[]) {
    int i, j;
    i = 0;
    j = kmpNext[0] = -1;
    while (i < m) {
        while (j > -1 && x[i] != x[j])
            j = kmpNext[j];
        i++;
        j++;
        if (i < m && x[i] == x[j])
            kmpNext[i] = kmpNext[j];
        else
            kmpNext[i] = j;
    }
}

/* So mẫu với văn bản bắt đầu từ bức tường (không so lại phần đã khớp) */
int attempt(char *y, char *x, int m, int start, int wall) {
    int k = wall - start;
    while (k < m && x[k] == y[k + start])
        ++k;
    return k;
}

void search(char *x, int m, char *y, int n) {
    int i, j, k, kmpStart, per, start, wall;
    int mpNext[XSIZE + 1], kmpNext[XSIZE + 1], list[XSIZE], z[ASIZE];

    /* Tiền xử lý */
    preMp(x, m, mpNext);
    preKmp(x, m, kmpNext);
    for (i = 0; i < ASIZE; ++i)
        z[i] = -1;
    for (i = 0; i < m; ++i)
        list[i] = -1;
    z[(unsigned char)x[0]] = 0;
    for (i = 1; i < m; ++i) {
        list[i] = z[(unsigned char)x[i]];
        z[(unsigned char)x[i]] = i;
    }

    /* Tìm kiếm */
    wall = 0;
    per = m - kmpNext[m];
    j = -1;
    do {
        j += m;
    } while (j < n && z[(unsigned char)y[j]] < 0);
    if (j >= n)
        return;
    i = z[(unsigned char)y[j]];
    start = j - i;
    while (start <= n - m) {
        if (start > wall)
            wall = start;
        k = attempt(y, x, m, start, wall);
        wall = start + k;
        if (k == m) {
            printf("Tim thay tai vi tri %d\n", start);
            i -= per;
        } else
            i = list[i];
        if (i < 0) {
            do {
                j += m;
            } while (j < n && z[(unsigned char)y[j]] < 0);
            if (j >= n)
                return;
            i = z[(unsigned char)y[j]];
        }
        kmpStart = start + k - kmpNext[k];
        k = kmpNext[k];
        start = j - i;
        while (start < kmpStart || (kmpStart < start && start < wall)) {
            if (start < kmpStart) {
                i = list[i];
                if (i < 0) {
                    do {
                        j += m;
                    } while (j < n && z[(unsigned char)y[j]] < 0);
                    if (j >= n)
                        return;
                    i = z[(unsigned char)y[j]];
                }
                start = j - i;
            } else {
                kmpStart += (k - mpNext[k]);
                k = mpNext[k];
            }
        }
    }
}

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ý bucket. z[G] = 7, z[C] = 1, z[A] = 6 (vị trí phải nhất của mỗi ký tự). Chuỗi list cho G là 7 → 5 → 3 → 0, cho A là 6 → 4 → 2, cho C là 1 → (-1). Chu kỳ mẫu per = m - kmpNext[m] = 2 (mẫu có dạng lặp AG).

Nhảy tìm mốc đầu. Từ j = m - 1 = 7: y[7] = A, có trong mẫu (z[A] = 6), nên i = 6, start = 7 - 6 = 1.

Thử tại start = 1. attempt so x với y[1..] = "CATCG..."; ngay ký tự đầu x[0]=G khác y[1]=C, k = 0. Không khớp, lần theo list[6] = 4 → start = 7 - 4 = 3; rồi list[4] = 2 → start = 5.

Thử tại start = 5. So x với y[5..12] = "GCAGAGAG", k chạy tới m = 8, cập nhật wall = 13. Tìm thấy xuất hiện tại vị trí 5. Nhờ chu kỳ per = 2 và bức tường, các phép thử tiếp theo không so lại vùng y[5..12].

Quá trình nhảy tiếp qua các mốc j = 15, 23; không có xuất hiện nào khác. Mỗi ký tự văn bản chỉ tham gia một số hằng phép so sánh, bảo đảm tổng thời gian O(n).

Tài liệu tham khảo