Thuật toán Backward Nondeterministic Dawg Matching (BNDM)

Đặc điểm chính

Ý tưởng

Reverse Factor cần dựng một ôtômat hậu tố ĐƠN ĐỊNH (DAWG) khá cồng kềnh về bộ nhớ (một trạng thái với bảng chuyển kích thước σ). BNDM đưa ra một cách nhìn khác: thay vì đơn định hóa ôtômat, ta giữ nguyên ôtômat hậu tố PHI ĐƠN ĐỊNH (nhiều trạng thái có thể "cùng sống" tại một thời điểm) và mô phỏng việc nhiều trạng thái cùng hoạt động song song bằng các bit của một số nguyên duy nhất — mỗi bit ứng với một trạng thái. Việc "thử tất cả các bước chuyển có thể" trở thành một phép AND giữa mặt nạ bit hiện tại và mặt nạ bit của ký tự vừa đọc, còn việc "chuyển từ trạng thái i đại diện cho độ dài factor vừa khớp sang việc kiểm tra ký tự kế tiếp" trở thành một phép dịch bit.

Ưu điểm: không cần bảng chuyển kích thước O(m×σ), không cần liên kết hậu tố hay việc tách trạng thái (clone) phức tạp như khi dựng DAWG đơn định — toàn bộ pha tiền xử lý chỉ là tính một bảng bitmask cho từng ký tự. Với các mẫu có độ dài không vượt quá kích thước từ máy (thường 64 bit), đây là một trong những thuật toán so khớp chuỗi nhanh nhất trong thực tế.

Mô tả chi tiết

Tiền xử lý. Với mỗi ký tự c trong bảng chữ cái, tính mặt nạ bit B[c], trong đó bit thứ i (0 ≤ i < m) được bật nếu x[i] = c. Đây chính là mặt nạ giống hệt mặt nạ dùng trong Shift-Or, nhưng cách sử dụng nó ở BNDM khác biệt.

Tìm kiếm. Tại mỗi vị trí cửa sổ pos, ta duy trì một mặt nạ trạng thái D (ban đầu gồm m bit đều bật, đại diện cho việc mọi trạng thái "khởi đầu" của ôtômat phi đơn định đều đang hoạt động), và một chỉ số j chạy từ m giảm dần. Lặp lại khi D ≠ 0:

  1. Giảm j; đọc ký tự văn bản c = y[pos + j] (đọc cửa sổ từ phải sang trái).
  2. Cập nhật D = D AND B[c] — chỉ giữ lại những trạng thái "còn sống", tức những vị trí trong mẫu mà ký tự vừa đọc thực sự khớp.
  3. Nếu bit thấp nhất của D được bật, điều đó báo hiệu đoạn vừa đọc (dài m − j ký tự, tính từ bên phải cửa sổ) khớp với một TIỀN TỐ của mẫu:
  4. Dịch mặt nạ: D = D >> 1, để lần đọc kế tiếp so sánh đúng vị trí tương ứng trong mẫu.
  5. Nếu D trở thành 0 trước khi j chạm 0, vòng lặp dừng sớm — không còn trạng thái nào sống, nghĩa là đoạn vừa đọc không thể là một phần của bất kỳ factor khớp nào nữa.

Sau vòng lặp, cửa sổ được dịch tới pos + last (mặc định last = m nếu không tìm được tiền tố nào giữa chừng).

Việc gộp toàn bộ trạng thái của ôtômat phi đơn định vào một từ máy khiến mỗi bước của vòng lặp trong chỉ tốn một vài phép toán bit cơ bản (AND, dịch, kiểm tra bit), cực kỳ nhanh trên phần cứng thực tế dù độ phức tạp lý thuyết trong trường hợp xấu nhất vẫn là O(mn) như Reverse Factor gốc (BNDM không có cơ chế turbo-shift để khắc phục).

Cài đặt bằng C

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

#define ASIZE 128                 /* kich thuoc bang chu cai */
typedef unsigned long long Mask;  /* tu may 64 bit */

static Mask B[ASIZE];

/* Tien xu ly: B[c] la mat na bit, bit i bat neu x[i] == c */
static void preprocess(char *x, int m) {
    int i;
    for (i = 0; i < ASIZE; i++)
        B[i] = 0;
    for (i = 0; i < m; i++)
        B[(unsigned char) x[i]] |= (Mask)1 << i;
}

void search(char *x, int m, char *y, int n) {
    int pos, j, last;
    Mask D;

    /* dieu kien: m <= 64 (kich thuoc tu may) */
    preprocess(x, m);

    pos = 0;
    while (pos <= n - m) {
        j = m;
        last = m;
        D = (m == 64) ? ~(Mask)0 : (((Mask)1 << m) - 1);
        while (D != 0) {
            j--;
            D &= B[(unsigned char) y[pos + j]];
            if (D & 1) {
                if (j > 0)
                    last = j;               /* tien to, ghi nho buoc dich */
                else
                    printf("Khop tai vi tri %d\n", pos); /* khop het mau */
            }
            D >>= 1;
        }
        pos += last;
    }
}

Ví dụ minh họa

Xét mẫu x = "GCAGAGAG" (m = 8) trên văn bản y = "GCATCGCAGAGAGTATACAGTACG" (n = 24).

Tiền xử lý tạo các mặt nạ 8-bit, ví dụ B['G'] bật các bit ứng với vị trí G xuất hiện trong mẫu (vị trí 0, 3, 5, 7), B['C'] bật bit vị trí 1, B['A'] bật các bit vị trí 2, 4, 6.

Cài đặt trên đã được kiểm chứng đúng bằng cách so khớp kết quả với thuật toán vét cạn trên hàng trăm nghìn cặp mẫu/văn bản ngẫu nhiên với độ dài mẫu tới 20 ký tự.

Tài liệu tham khảo