Thuật toán Reverse Factor (BDM)

Đặc điểm chính

Ý tưởng

Các thuật toán họ Boyer-Moore quét cửa sổ từ phải sang trái để phát hiện hậu tố đã khớp. Reverse Factor đi xa hơn: nó không chỉ theo dõi hậu tố mà theo dõi factor (đoạn con bất kỳ) dài nhất của mẫu, tính từ đầu bên phải của cửa sổ đọc ngược vào. Muốn vậy, ta dùng một ôtômat có thể nhận diện mọi factor của mẫu.

Có một mẹo: nhận diện factor của mẫu x khi đọc văn bản từ phải sang trái tương đương với nhận diện tiền tố của x đảo ngược khi đọc xuôi. Otomat hậu tố (suffix automaton, còn gọi là DAWG — Directed Acyclic Word Graph) của x đảo ngược chính là công cụ nhận mọi factor này, với kích thước tuyến tính O(m). Khi quét ngược cửa sổ mà ôtômat vẫn còn đường đi hợp lệ, ta biết đoạn vừa đọc là một factor của mẫu; khi ôtômat "kẹt" (không còn chuyển hợp lệ), đoạn đọc được không còn là factor nữa và ta có căn cứ để dịch cửa sổ.

Mô tả chi tiết

Tiền xử lý. Dựng ôtômat hậu tố cho x đảo ngược bằng thuật toán online kinh điển (thêm từng ký tự, quản lý liên kết hậu tố suffix link và tách trạng thái - clone khi cần). Otomat này nhận diện đúng tập hợp mọi factor của mẫu gốc khi ta nạp ký tự theo chiều đọc ngược. Ta đánh dấu các trạng thái "kết" (terminal): đó là những trạng thái nằm trên chuỗi suffix link xuất phát từ trạng thái cuối cùng — chúng tương ứng với các tiền tố của x đảo ngược, tức các HẬU TỐ của x; nhưng theo hướng nhận diện factor, một trạng thái kết ứng với việc đoạn vừa đọc là một tiền tố của mẫu.

Tìm kiếm. Đặt cửa sổ tại vị trí j, quét biến i từ m-1 về 0, mỗi bước nạp ký tự y[j+i] vào ôtômat (khởi đầu từ trạng thái gốc):

Giá trị last khởi tạo bằng m (dịch tối đa khi không tìm được tiền tố nào). Bước dịch trung bình lớn cỡ m nên tổng chi phí đạt cận dưới tối ưu O(n · log_σ(m) / m).

Cài đặt bằng C

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

#define ASIZE 128          /* kích thước bảng chữ cái */
#define XSIZE 64           /* độ dài mẫu tối đa */
#define UNDEFINED (-1)

/* Ô-tô-mát hậu tố (suffix automaton) của mẫu đảo ngược */
typedef struct {
    int len;               /* độ dài factor dài nhất của trạng thái */
    int link;              /* liên kết hậu tố */
    int term;              /* 1 nếu là trạng thái kết (nhận tiền tố mẫu) */
    int next[ASIZE];       /* hàm chuyển */
} SamState;

static SamState sam[2 * XSIZE];
static int samSize, samLast;

static void samInit(void) {
    int c;
    samSize = 1;
    samLast = 0;
    sam[0].len = 0;
    sam[0].link = UNDEFINED;
    sam[0].term = 0;
    for (c = 0; c < ASIZE; ++c)
        sam[0].next[c] = UNDEFINED;
}

static void samExtend(int c) {
    int cur, p, q, clone, i;
    cur = samSize++;
    sam[cur].len = sam[samLast].len + 1;
    sam[cur].term = 0;
    for (i = 0; i < ASIZE; ++i)
        sam[cur].next[i] = UNDEFINED;
    p = samLast;
    while (p != UNDEFINED && sam[p].next[c] == UNDEFINED) {
        sam[p].next[c] = cur;
        p = sam[p].link;
    }
    if (p == UNDEFINED)
        sam[cur].link = 0;
    else {
        q = sam[p].next[c];
        if (sam[p].len + 1 == sam[q].len)
            sam[cur].link = q;
        else {
            clone = samSize++;
            sam[clone].len = sam[p].len + 1;
            sam[clone].link = sam[q].link;
            sam[clone].term = 0;
            memcpy(sam[clone].next, sam[q].next, sizeof(sam[q].next));
            while (p != UNDEFINED && sam[p].next[c] == q) {
                sam[p].next[c] = clone;
                p = sam[p].link;
            }
            sam[q].link = clone;
            sam[cur].link = clone;
        }
    }
    samLast = cur;
}

/* Dựng ô-tô-mát hậu tố cho x đảo ngược và đánh dấu trạng thái kết */
static void buildReverseSam(char *x, int m) {
    int i, p;
    samInit();
    for (i = m - 1; i >= 0; --i)          /* nạp x từ phải sang trái */
        samExtend((unsigned char) x[i]);
    p = samLast;                          /* đánh dấu các trạng thái kết */
    while (p != UNDEFINED) {
        sam[p].term = 1;
        p = sam[p].link;
    }
}

void search(char *x, int m, char *y, int n) {
    int i, j, state, last;

    /* Tiền xử lý */
    buildReverseSam(x, m);

    /* Tìm kiếm */
    j = 0;
    while (j <= n - m) {
        i = m - 1;
        state = 0;
        last = m;                          /* bước dịch mặc định */
        while (i >= 0 &&
               (state = sam[state].next[(unsigned char) y[j + i]])
                   != UNDEFINED) {
            if (sam[state].term && i > 0)
                last = i;                  /* ghi nhớ tiền tố dài nhất */
            --i;
        }
        if (i < 0)                         /* đọc hết cửa sổ: khớp */
            printf("Khop tai vi tri %d\n", j);
        j += last;
    }
}

Ví dụ minh họa

Xét mẫu x = "GCAGAGAG" (m = 8) và văn bản y = "GCATCGCAGAGAGTATACAGTACG" (n = 24). Ta dựng ôtômat hậu tố cho mẫu đảo ngược "GAGAGACG".

Điểm mạnh của BDM: khi cửa sổ không khớp, việc đọc ngược thường kẹt rất sớm và cho phép dịch cửa sổ những bước dài xấp xỉ m, đưa tới độ phức tạp trung bình dưới tuyến tính O(n · log_σ(m) / m).

Tài liệu tham khảo