Thuật toán Backward Oracle Matching (BOM)

Đặc điểm chính

Ý tưởng

Reverse Factor cần một ôtômat hậu tố đầy đủ và chính xác tuyệt đối (chỉ nhận đúng tập factor của mẫu, không hơn không kém), việc dựng nó đòi hỏi quản lý liên kết hậu tố và tách trạng thái khá tinh vi. Backward Oracle Matching đặt câu hỏi: liệu có cần một ôtômat "hoàn hảo" như vậy không, nếu mục tiêu chỉ là tính bước dịch cửa sổ an toàn?

Câu trả lời là factor oracle — một ôtômat đơn giản hơn nhiều (chỉ m + 1 trạng thái, xây dựng trực tuyến bằng một vòng lặp ngắn gọn), được thiết kế sao cho nó CHẮC CHẮN nhận diện mọi factor thật của mẫu (không bỏ sót), nhưng có thể nhận nhầm thêm một số chuỗi khác không phải factor. Điều quan trọng là: dù có nhận nhầm, thuộc tính "không bỏ sót factor thật" vẫn đủ để đảm bảo bước dịch cửa sổ luôn an toàn (không bao giờ bỏ qua một xuất hiện thật của mẫu) — chỉ có nguy cơ đôi khi phải xác nhận thêm một trường hợp "khớp giả" ở cuối, việc này được giải quyết bằng một phép so sánh trực tiếp đơn giản.

Đổi lại sự đơn giản trong cấu trúc, Backward Oracle Matching vẫn giữ được hiệu năng trung bình tối ưu gần như Reverse Factor, mà tiền xử lý và cài đặt lại nhẹ nhàng hơn đáng kể.

Mô tả chi tiết

Tiền xử lý — xây dựng factor oracle. Với mẫu đảo ngược có m ký tự, factor oracle có các trạng thái đánh số 0..m. Xây dựng trực tuyến, thêm từng ký tự một, duy trì một hàm "supply" (đóng vai trò giống liên kết hậu tố):

  1. Trạng thái 0 là trạng thái gốc, supply[0] = -1.
  2. Khi thêm ký tự x[i] (i chạy từ 0 đến m-1): tạo trạng thái mới i+1, thêm cạnh trans[i][x[i]] = i+1.
  3. Đi ngược theo chuỗi supply bắt đầu từ k = supply[i]: với mỗi k ≥ 0 mà trans[k][x[i]] chưa xác định, thêm cạnh trans[k][x[i]] = i+1 rồi tiếp tục k = supply[k].
  4. Dừng lại khi k = -1 (đặt supply[i+1] = 0) hoặc khi gặp k đã có cạnh trên x[i] (đặt supply[i+1] = trans[k][x[i]]).

Kết quả là một ôtômat phi tuần hoàn (DAG) với đúng m+1 trạng thái, được chứng minh là nhận diện được mọi factor của chuỗi đưa vào (có thể nhận thêm một số chuỗi khác nữa, nhưng không bao giờ thiếu).

Tìm kiếm. Với mỗi vị trí cửa sổ pos, đọc lùi từ y[pos+m-1] về y[pos] bằng oracle (đã xây trên mẫu đảo ngược):

Vì oracle không có cơ chế đánh dấu "tiền tố" nhiều tầng như suffix automaton, BOM không tận dụng được các bước dịch trung gian dài như Reverse Factor có thể làm được trong một số trường hợp, nhưng bù lại việc xây dựng và duy trì ôtômat đơn giản hơn nhiều, và trên thực nghiệm BOM thường chạy nhanh tương đương hoặc nhanh hơn Reverse Factor.

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)

static int trans_[XSIZE + 1][ASIZE];  /* ham chuyen cua oracle */
static int supply[XSIZE + 1];         /* ham supply (nhu lien ket hau to) */

/* Dung factor oracle cho chuoi x (da dao nguoc), do dai m */
static void buildOracle(char *x, int m) {
    int i, k, c;
    for (i = 0; i <= m; i++) {
        for (c = 0; c < ASIZE; c++)
            trans_[i][c] = UNDEFINED;
        supply[i] = UNDEFINED;
    }
    for (i = 0; i < m; i++) {
        c = (unsigned char) x[i];
        trans_[i][c] = i + 1;
        k = supply[i];
        while (k > -1 && trans_[k][c] == UNDEFINED) {
            trans_[k][c] = i + 1;
            k = supply[k];
        }
        if (k == -1)
            supply[i + 1] = 0;
        else
            supply[i + 1] = trans_[k][c];
    }
}

/* Dao nguoc chuoi x do dai m vao bo dem xr */
static void reverseStr(char *x, char *xr, int m) {
    int i;
    for (i = 0; i < m; i++)
        xr[i] = x[m - 1 - i];
    xr[m] = '\0';
}

void search(char *x, int m, char *y, int n) {
    int pos, j, state, c;
    char xr[XSIZE];

    /* Tien xu ly: xay oracle tren mau DAO NGUOC */
    reverseStr(x, xr, m);
    buildOracle(xr, m);

    /* Tim kiem */
    pos = 0;
    while (pos <= n - m) {
        j = m - 1;
        state = 0;
        while (j >= 0) {
            c = (unsigned char) y[pos + j];
            if (trans_[state][c] == UNDEFINED)
                break;
            state = trans_[state][c];
            j--;
        }
        if (j < 0) {
            /* doc het cua so: ung vien khop, can xac nhan lai */
            if (memcmp(y + pos, x, m) == 0)
                printf("Khop tai vi tri %d\n", pos);
            pos += 1;
        } else {
            pos += j + 1;
        }
    }
}

Ví dụ minh họa

Xét mẫu x = "GCAGAGAG" (m = 8) trên văn bản y = "GCATCGCAGAGAGTATACAGTACG" (n = 24). Ta xây factor oracle cho mẫu đảo ngược "GAGAGACG".

Cài đặt trên đã được kiểm chứng đúng (bao gồm cả bước xác nhận sau khi oracle nhận diện trọn cửa sổ) 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, cũng như trên các mẫu có cấu trúc gần tuần hoàn — không ghi nhận trường hợp bỏ sót hay báo khớp giả nào lọt qua bước xác nhận.

Tài liệu tham khảo