Thuật toán Colussi

Đặc điểm chính

Ý tưởng

Trong KMP, khi so mẫu với cửa sổ hiện tại và gặp lệch, ta trượt cửa sổ nhưng lại quên rằng một số ký tự văn bản đã được so khớp thành công ở lần thử trước. Colussi khai thác triệt để hơn thông tin này.

Chìa khoá là phân loại các vị trí i của mẫu theo bảng dịch chuyển KMP. Một vị trí i gọi là nohole nếu kmpNext[i] > kmpNext[i+1] (theo cách định nghĩa của Colussi, đây là vị trí mà giá trị hàm biên "giảm", ứng với những vị trí mà khi so khớp ta thu được thông tin thật sự mới); các vị trí còn lại gọi là hole. Ý tưởng: khi thử một cửa sổ, trước tiên chỉ so các vị trí nohole theo chiều tăng dần; nếu tất cả nohole khớp thì mới quay lại so các vị trí hole theo chiều giảm dần. Cách sắp xếp này bảo đảm mỗi ký tự văn bản không bị so quá một số lần có kiểm soát, dẫn tới cận 3n/2.

Mô tả chi tiết

Pha tiền xử lý tính một loạt bảng:

Pha tìm kiếm dùng một biến last ghi lại chỉ số văn bản lớn nhất đã được so khớp chắc chắn ở lần thử trước. Với mỗi cửa sổ đặt tại j, ta duyệt h từ chỉ số i: chừng nào vị trí h[i] chưa vượt qua last (điều kiện last < j + h[i]) và ký tự khớp thì tăng i. Khi phát hiện lệch (hoặc đã duyệt xong toàn bộ), ta cập nhật last nếu đã bước sang phần hole, rồi trượt cửa sổ j += shift[i] và đặt i = nxt[i].

Cài đặt bằng C

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

int preColussi(char *x, int m, int h[], int nxt[], int shift[]) {
    int i, k, q, r, s, nd;
    int *hmax = (int *) malloc((m + 1) * sizeof(int));
    int *kmin = (int *) calloc(m, sizeof(int));
    int *rmin = (int *) calloc(m, sizeof(int));
    int *nhd0 = (int *) calloc(m + 1, sizeof(int));

    /* hmax: chu kỳ dài nhất của mỗi tiền tố */
    i = k = 1;
    do {
        while (i < m && x[i] == x[i - k]) ++i;
        hmax[k] = i;
        q = k + 1;
        while (q <= m && hmax[q - k] + k < i) {
            hmax[q] = hmax[q - k] + k;
            ++q;
        }
        k = q;
        if (k == i + 1) i = k;
    } while (k <= m);

    /* kmin[i]: chu kỳ nhỏ nhất k với hmax[k] = i */
    for (k = m; k >= 1; --k)
        if (hmax[k] < m) kmin[hmax[k]] = k;

    /* rmin[i]: chu kỳ nhỏ nhất của x lớn hơn i (cho các hole) */
    r = 0;
    for (i = m - 1; i >= 0; --i) {
        if (hmax[i + 1] == m) r = i + 1;
        rmin[i] = (kmin[i] == 0) ? r : 0;
    }

    /* h: nohole tăng dần ở đầu, hole giảm dần ở cuối */
    s = -1; r = m;
    for (i = 0; i < m; ++i)
        if (kmin[i] == 0) h[--r] = i;
        else              h[++s] = i;
    nd = s;

    /* nhd0[i]: số nohole ở các vị trí < i */
    s = 0;
    for (i = 0; i < m; ++i) {
        nhd0[i] = s;
        if (kmin[i] > 0) ++s;
    }
    nhd0[m] = s;

    /* shift và nxt */
    for (i = 0; i <= nd; ++i) {
        shift[i] = kmin[h[i]];
        nxt[i]   = nhd0[h[i] - kmin[h[i]]];
    }
    for (i = nd + 1; i < m; ++i) {
        shift[i] = rmin[h[i]];
        nxt[i]   = nhd0[m - rmin[h[i]]];
    }
    shift[m] = rmin[0];
    nxt[m]   = nhd0[m - rmin[0]];

    free(hmax); free(kmin); free(rmin); free(nhd0);
    return nd;
}

void search(char *x, int m, char *y, int n) {
    int i, j, last, nd;
    int *h     = (int *) malloc((m + 1) * sizeof(int));
    int *nxt   = (int *) malloc((m + 1) * sizeof(int));
    int *shift = (int *) malloc((m + 1) * sizeof(int));

    nd = preColussi(x, m, h, nxt, shift);

    i = j = 0;
    last = -1;
    while (j + m <= n) {
        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;
        }
        if (i > nd) last = j + m - 1;
        j += shift[i];
        i = nxt[i];
    }
    free(h); free(nxt); free(shift);
}

Ví dụ minh họa

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

Tiền xử lý cho: nd = 3 (bốn vị trí nohole), thứ tự duyệt

chỉ số i01234567
h[i]12467530

Bốn vị trí đầu (1, 2, 4, 6) là nohole (duyệt tăng), bốn vị trí sau (7, 5, 3, 0) là hole (duyệt giảm).

Vài lần thử đầu:

Cách duyệt nohole trước, hole sau giúp Colussi phát hiện lệch sớm và trượt xa, đồng thời khống chế tổng số phép so sánh dưới 3n/2.

Tài liệu tham khảo