Thuật toán Raita

Đặc điểm chính

Ý tưởng

Raita nhận xét rằng trong văn bản ngôn ngữ tự nhiên, các ký tự liền kề có phụ thuộc thống kê mạnh: nếu ký tự cuối của cửa sổ đã trùng ký tự cuối của mẫu, thì các ký tự lân cận cũng có xu hướng trùng theo. Vì vậy, để phát hiện sớm một cửa sổ KHÔNG khớp (đó là đại đa số trường hợp), nên so những ký tự ít tương quan với nhau trước, nhằm tối đa hóa xác suất bắt gặp sai khác ngay từ vài phép so sánh đầu.

Thứ tự Raita đề xuất là: so ký tự cuối trước (để tận dụng bảng bad-character), rồi ký tự đầu, rồi ký tự giữa, và chỉ khi ba ký tự "mốc" này đều trùng mới so nốt phần thân còn lại. Ba vị trí đầu-giữa-cuối cách xa nhau nên ít tương quan, giúp loại bỏ cửa sổ sai nhanh hơn so với việc quét tuần tự.

Mô tả chi tiết

Pha tiền xử lý chỉ dựng đúng bảng bmBc của Horspool: bmBc[a] = khoảng cách từ lần xuất hiện cuối của a trong m-1 ký tự đầu mẫu tới cuối mẫu, hoặc m nếu không có. Ngoài ra ta lưu sẵn ba ký tự mốc để tránh truy cập lặp: firstCh = x[0], middleCh = x[m/2], lastCh = x[m-1].

Tại mỗi cửa sổ j, gọi c = y[j+m-1] là ký tự văn bản thẳng hàng với ký tự cuối mẫu. Ta kiểm tra theo thứ tự với đoản mạch (short-circuit):

  1. lastCh == c? Nếu sai, bỏ qua ngay.
  2. middleCh == y[j + m/2]? So ký tự giữa.
  3. firstCh == y[j]? So ký tự đầu.
  4. Cuối cùng so phần thân x[1..m-2] với y[j+1..j+m-2] từ trái sang phải.

Nếu cả bốn điều kiện đều đúng thì có một lần xuất hiện tại j. Dù khớp hay không, cửa sổ luôn dịch đi bmBc[c] — chính xác là bước dịch của Horspool. Như vậy Raita giữ nguyên tính đúng đắn và bước dịch của Horspool, chỉ tối ưu chi phí so khớp trung bình bằng cách sắp xếp lại thứ tự kiểm tra.

Cài đặt bằng C

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

#define ASIZE 256

/* Bảng dịch bad-character kiểu Horspool */
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 search(char *x, int m, char *y, int n) {
    int j, bmBc[ASIZE];
    char c, firstCh, middleCh, lastCh;

    /* Tiền xử lý */
    preBmBc(x, m, bmBc);
    firstCh  = x[0];
    middleCh = x[m / 2];
    lastCh   = x[m - 1];

    /* Tìm kiếm */
    j = 0;
    while (j <= n - m) {
        c = y[j + m - 1];
        if (lastCh == c &&
            middleCh == y[j + m / 2] &&
            firstCh == y[j] &&
            memcmp(x + 1, y + j + 1, m - 2) == 0)
            printf("Khop tai vi tri %d\n", j);
        j += bmBc[(unsigned char) c];
    }
}

Ví dụ minh họa

Xét mẫu x = "GCAGAGAG" (m = 8) và văn bản y = "GCATCGCAGAGAGTATACAGTACG" (n = 24). Ba ký tự mốc: firstCh = x[0] = 'G', middleCh = x[4] = 'G', lastCh = x[7] = 'G'. Bảng bad-character: bmBc[A] = 1, bmBc[G] = 2, bmBc[C] = 6, còn lại 8.

Nhờ so ký tự cuối rồi đầu rồi giữa trước, đa số cửa sổ sai bị loại chỉ sau 1-3 phép so sánh thay vì phải quét cả 8 ký tự.

Tài liệu tham khảo