Thuật toán Apostolico-Giancarlo

Đặc điểm chính

Ý tưởng

Boyer-Moore có thể phải so sánh lại, ở một cửa sổ mới, những đoạn văn bản đã từng được so sánh (và biết kết quả) ở một cửa sổ trước đó, nếu cửa sổ mới chồng lấn cửa sổ cũ. Turbo Boyer-Moore giải quyết một phần vấn đề này bằng cách nhớ một đoạn khớp gần nhất. Apostolico và Giancarlo đẩy ý tưởng đó lên một mức tổng quát hơn: thay vì chỉ nhớ một cặp (u, v), thuật toán duy trì một bảng skip đầy đủ, ghi lại tại mỗi vị trí trong cửa sổ hiện tại độ dài của đoạn hậu tố đã biết là khớp với mẫu tính từ vị trí đó — thông tin này được suy ra trực tiếp từ chính kết quả so sánh của (các) lần thử trước đó, dịch chuyển tương ứng theo bước dịch đã dùng.

Nhờ có sẵn thông tin "đã biết trước" tại mọi vị trí trong cửa sổ (chứ không chỉ ở đúng ranh giới đoạn nhớ như Turbo-BM), thuật toán có thể bỏ qua nhiều đoạn so sánh trùng lặp hơn, và quan trọng hơn, chứng minh được cận trên chặt cho tổng số phép so sánh: không quá 3n/2, đồng thời không còn kịch bản xấu nhất bậc hai nào.

Mô tả chi tiết

Thuật toán vẫn dùng bảng bmBc, bmGs giống Boyer-Moore để tính bước dịch, và bảng suff (độ dài hậu tố dài nhất của x[0..i] đồng thời là hậu tố của toàn mẫu, đã dùng để xây bmGs). Điểm khác biệt là một mảng phụ skip[0..m-1], trong đó skip[i] ghi nhận: nếu đặt cửa sổ ở vị trí hiện tại, đoạn văn bản bắt đầu từ chỉ số i trong cửa sổ (tức y[i+j..]) đã được biết chắc khớp với x[i..i+skip[i]-1] nhờ kết quả của (các) lần thử trước, mà không cần so sánh lại.

Tại một lần thử, khi so sánh lùi từ i = m-1, tại mỗi vị trí i ta tra k = skip[i] và s = suff[i] (độ dài hậu tố mẫu đồng thời khớp với hậu tố toàn cục tại vị trí đó):

Sau khi kết thúc một lần thử tại vị trí lệch i (hoặc khớp toàn bộ), bước dịch được tính đúng như Boyer-Moore: shift = max(bmGs[i], bmBc[y[i+j]] - m + 1 + i) (khi khớp toàn bộ dùng bmGs[0]). Bảng skip sau đó được dịch chuyển đi shift vị trí (những gì biết ở cửa sổ cũ vẫn còn giá trị ở cửa sổ mới, chỉ lệch chỉ số) và đặt skip[m-1] bằng độ dài hậu tố vừa khớp được ở lần thử này (m - 1 - i, hoặc m nếu khớp toàn bộ) — chính là thông tin mới sẽ được các lần thử sau khai thác.

Cài đặt bằng C

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

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

void preBmBc(char *x, int m, int bmBc[]) {
    int i;
    for (i = 0; i < ASIZE; ++i)
        bmBc[i] = m;
    for (i = 0; i < m - 1; ++i)
        bmBc[(unsigned char) x[i]] = m - 1 - i;
}

void suffixes(char *x, int m, int *suff) {
    int f, g, i;
    f = 0;
    suff[m - 1] = m;
    g = m - 1;
    for (i = m - 2; i >= 0; --i) {
        if (i > g && suff[i + m - 1 - f] < i - g)
            suff[i] = suff[i + m - 1 - f];
        else {
            if (i < g)
                g = i;
            f = i;
            while (g >= 0 && x[g] == x[g + m - 1 - f])
                --g;
            suff[i] = f - g;
        }
    }
}

void preBmGs(char *x, int m, int bmGs[]) {
    int i, j, suff[XSIZE];
    suffixes(x, m, suff);

    for (i = 0; i < m; ++i)
        bmGs[i] = m;
    j = 0;
    for (i = m - 1; i >= 0; --i)
        if (suff[i] == i + 1)
            for (; j < m - 1 - i; ++j)
                if (bmGs[j] == m)
                    bmGs[j] = m - 1 - i;
    for (i = 0; i <= m - 2; ++i)
        bmGs[m - 1 - suff[i]] = m - 1 - i;
}

void search(char *x, int m, char *y, int n) {
    int i, j, k, s, shift;
    int bmGs[XSIZE], bmBc[ASIZE], suff[XSIZE], skip[XSIZE];

    preBmGs(x, m, bmGs);
    preBmBc(x, m, bmBc);
    suffixes(x, m, suff);
    memset(skip, 0, m * sizeof(int));

    j = 0;
    while (j <= n - m) {
        i = m - 1;
        while (i >= 0) {
            k = skip[i];
            s = suff[i];
            if (k > 0) {
                if (k > s) {
                    /* Thong tin nho da du de ket luan diem dung, khong doc them van ban */
                    i = (i + 1 == s) ? -1 : i - s;
                    break;
                } else {
                    i -= k;         /* nhay qua doan da biet chac khop */
                    if (k < s)
                        break;      /* du de xac dinh diem lech, khong can so them */
                    /* k == s: van chua chac, tiep tuc so sanh thuc su tai vi tri moi */
                }
            } else {
                if (x[i] == y[i + j])
                    --i;
                else
                    break;
            }
        }

        if (i < 0) {
            printf("Tim thay tai vi tri %d\n", j);
            skip[m - 1] = m;
            shift = bmGs[0];
        } else {
            skip[m - 1] = m - 1 - i;
            shift = MAX(bmGs[i], bmBc[(unsigned char) y[i + j]] - m + 1 + i);
        }

        j += shift;
        /* Dich bang skip theo buoc shift vua dung */
        memmove(skip, skip + shift, (m - shift) * sizeof(int));
        memset(skip + m - shift, 0, shift * sizeof(int));
    }
}

Ví dụ minh họa

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

Điểm đáng chú ý nhất trong ví dụ là ở cửa sổ j = 5: nhờ bảng skip mang theo thông tin từ lần thử trước (j = 1, nơi 2 ký tự cuối "AG" của cửa sổ đã khớp trước khi lệch), Apostolico-Giancarlo tránh so sánh lại 2 ký tự văn bản khi thử lại ở cửa sổ mới — đây chính là cơ chế giúp cận 3n/2 được đảm bảo trong mọi trường hợp.

Tài liệu tham khảo