Thuật toán Forward Dawg Matching (FDM)

Đặc điểm chính

Ý tưởng

Nếu Reverse Factor dùng ôtômat hậu tố của mẫu đảo ngược để quét cửa sổ từ phải sang trái, thì Forward Dawg Matching đi theo hướng tự nhiên hơn: dùng trực tiếp ôtômat hậu tố của mẫu để quét văn bản từ trái sang phải, giống cách con người đọc văn bản.

Tại mỗi vị trí i của văn bản, ta muốn biết: hậu tố dài nhất của y[0..i] mà đồng thời là một factor (đoạn con) của mẫu x có độ dài bao nhiêu? Otomat hậu tố của x chính là công cụ lý tưởng để trả lời câu hỏi này một cách tăng dần: khi đọc thêm một ký tự mới, ta chỉ cần cập nhật trạng thái hiện tại của ôtômat. Nếu độ dài factor khớp được đạt tới m (độ dài mẫu), nghĩa là toàn bộ mẫu vừa xuất hiện, kết thúc tại vị trí i hiện tại.

Điểm khéo léo nằm ở việc xử lý khi ôtômat "kẹt" — không có chuyển tương ứng với ký tự mới. Khi đó ta không quay lại từ đầu (như thuật toán vét cạn) mà đi theo liên kết hậu tố (suffix link) để tìm trạng thái đại diện cho hậu tố ngắn hơn kế tiếp có thể mở rộng được, và lặp lại cho tới khi tìm được chuyển hợp lệ hoặc quay về trạng thái gốc. Cơ chế này gợi nhớ tới hàm thất bại của KMP, nhưng vận hành trên ôtômat hậu tố nhận diện MỌI factor thay vì chỉ theo dõi một chuỗi tiền tố cụ thể.

Mô tả chi tiết

Tiền xử lý. Dựng ôtômat hậu tố (suffix automaton) cho mẫu x bằng thuật toán online kinh điển: thêm lần lượt từng ký tự, quản lý liên kết hậu tố (link) và độ dài lớn nhất của factor mà mỗi trạng thái đại diện (len), tách trạng thái (clone) khi cần để giữ tính chất của ôtômat. Với ôtômat này, sam[link(s)].len luôn là độ dài của hậu tố dài nhất, ngắn hơn thực sự, mà trạng thái link(s) còn nhận diện được.

Tìm kiếm. Duy trì một trạng thái hiện hành state (khởi đầu là trạng thái gốc) và độ dài khớp hiện hành l (khởi đầu 0), đại diện cho hậu tố dài nhất của phần văn bản đã đọc mà cũng là một factor của mẫu. Với mỗi ký tự mới c = y[i]:

  1. Trong khi state không có chuyển hợp lệ trên c và state chưa phải trạng thái gốc: đi theo liên kết hậu tố state = link(state), đồng thời cập nhật l = len(state) — đây chính là độ dài hậu tố tối đa còn giữ được sau khi "lùi" trạng thái.
  2. Nếu sau vòng lặp, state có chuyển hợp lệ trên c: cập nhật state = next(state, c) và tăng l = l + 1.
  3. Nếu không (kể cả trạng thái gốc cũng không có chuyển), đặt lại state về gốc và l = 0.
  4. Nếu l đạt tới m (độ dài mẫu), ta vừa tìm thấy một xuất hiện của mẫu kết thúc tại vị trí i, tức bắt đầu tại i - m + 1.

Lập luận khấu hao (amortized): mỗi lần đi theo liên kết hậu tố làm l giảm ngặt, còn mỗi ký tự mới đọc được chỉ làm l tăng thêm nhiều nhất 1. Vì l không thể vượt quá m và không âm, tổng số lần "lùi" trên toàn bộ quá trình quét bị chặn bởi tổng số lần "tiến", tức O(n). Nhờ vậy toàn bộ thuật toán chạy đúng thời gian tuyến tính O(n), không có trường hợp xấu nhất tệ hơn.

Cài đặt bằng C

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

#define ASIZE 128           /* kich thuoc bang chu cai */
#define XSIZE 256            /* do dai mau toi da */
#define UNDEFINED (-1)

/* O-to-mat hau to (suffix automaton) cua mau x */
typedef struct {
    int len;                /* do dai factor dai nhat cua trang thai */
    int link;               /* lien ket hau to */
    int next[ASIZE];        /* ham chuyen */
} 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;
    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;
    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;
            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;
}

/* Dung o-to-mat hau to cho mau x (khong dao nguoc) */
static void buildSam(char *x, int m) {
    int i;
    samInit();
    for (i = 0; i < m; ++i)
        samExtend((unsigned char) x[i]);
}

void search(char *x, int m, char *y, int n) {
    int i, state, l, c, nstate;

    /* Tien xu ly */
    buildSam(x, m);

    /* Tim kiem: quet van ban tu trai sang phai */
    state = 0;
    l = 0;
    for (i = 0; i < n; ++i) {
        c = (unsigned char) y[i];
        while (state != UNDEFINED && sam[state].next[c] == UNDEFINED) {
            state = sam[state].link;
            l = (state == UNDEFINED) ? 0 : sam[state].len;
        }
        if (state == UNDEFINED) {
            state = 0;
            l = 0;
        } else {
            nstate = sam[state].next[c];
            state = nstate;
            l = l + 1;
        }
        if (l >= m)
            printf("Khop, ket thuc tai vi tri %d (bat dau tai %d)\n",
                   i, i - m + 1);
    }
}

Ví dụ minh họa

Xét mẫu x = "GCAGAGAG" (m = 8) trên văn bản y = "GCATCGCAGAGAGTATACAGTACG" (n = 24). Otomat hậu tố được dựng trực tiếp trên x (không đảo ngược).

Cài đặt trên đã được kiểm chứng bằng cách đối chiếu với thuật toán vét cạn trên hàng vạn cặp mẫu/văn bản ngẫu nhiên và luôn cho kết quả trùng khớp.

Tài liệu tham khảo