Thuật toán Maximal Shift

Đặc điểm chính

Ý tưởng

Maximal Shift, cũng do Sunday đề xuất, là "người anh em" của Optimal Mismatch. Cả hai đều thay đổi thứ tự so sánh các vị trí của mẫu, nhưng theo tiêu chí khác nhau.

Ở đây tiêu chí không phải là tần suất ký tự trong văn bản, mà là lượng dịch cửa sổ mà mỗi vị trí đảm bảo khi xảy ra sai lệch tại đó. Một vị trí mà nếu lệch cho phép dịch cửa sổ xa thì nên được so sớm: như vậy khi ta gặp sai lệch (dù đã kiểm tra được vài vị trí), tổng lượng dịch tích luỹ sẽ lớn, giúp trượt qua văn bản nhanh hơn.

Mô tả chi tiết

1. Bảng minShift. Với mỗi vị trí i của mẫu, minShift[i] là khoảng cách tới lần xuất hiện gần nhất trước đó của cùng ký tự x[i] trong mẫu, tức minShift[i] = i - s với s là chỉ số lớn nhất < i sao cho x[s] = x[i] (nếu không có thì s = -1, cho minShift[i] = i + 1). Đại lượng này phản ánh: nếu vị trí i lệch, mẫu phải dịch tối thiểu bao nhiêu để ký tự đó có cơ hội khớp lại.

2. Thứ tự so sánh (orderPattern). Ta lập các cặp (loc = i, c = x[i]) rồi sắp xếp sao cho vị trí có minShift lớn đứng trước (dịch được xa hơn thì ưu tiên so trước); phá hoà bằng vị trí lớn hơn xếp trước. Mảng kết quả pat[] định thứ tự duyệt các vị trí trong pha tìm kiếm.

3. Bảng qsBc và adaptedGs. Hoàn toàn giống Optimal Mismatch: qsBc là bảng dịch kiểu Quick Search dựa vào ký tự y[j+m] ngay sau cửa sổ; adaptedGs[k] là lượng dịch khi đã khớp k vị trí đầu (theo thứ tự pat) rồi gặp sai lệch, được dựng bằng matchShift.

Điểm khác biệt duy nhất so với Optimal Mismatch là hàm so sánh dùng để sắp pat. Toàn bộ phần còn lại — cách dựng adaptedGs, cách tính bước dịch trong tìm kiếm — là như nhau. Tại mỗi vị trí cửa sổ j, so pat[0], pat[1], …; nếu khớp hết m vị trí thì báo xuất hiện; dịch cửa sổ max(adaptedGs[i], qsBc[y[j+m]]).

Cài đặt bằng C

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

#define ASIZE 256
#define XSIZE 1024
#define MAX(a, b) ((a) > (b) ? (a) : (b))

typedef struct {
    int loc;
    unsigned char c;
} Pair;

static int minShift[XSIZE];

/* minShift[i]: khoảng cách tới lần xuất hiện trước của x[i] trong mẫu */
void computeMinShift(char *x, int m) {
    int i, s;
    for (i = 0; i < m; ++i) {
        for (s = i - 1; s >= 0; --s)
            if (x[i] == x[s])
                break;
        minShift[i] = i - s;
    }
}

/* So sánh: vị trí có minShift lớn xếp trước (so trước) */
int maxShiftPcmp(const void *a, const void *b) {
    const Pair *p1 = (const Pair *)a, *p2 = (const Pair *)b;
    int d = minShift[p2->loc] - minShift[p1->loc];
    return d != 0 ? d : (p2->loc - p1->loc);
}

void orderPattern(char *x, int m,
                  int (*pcmp)(const void *, const void *), Pair *pat) {
    int i;
    for (i = 0; i < m; ++i) {
        pat[i].loc = i;
        pat[i].c = (unsigned char)x[i];
    }
    qsort(pat, m, sizeof(Pair), pcmp);
}

void preQsBc(char *x, int m, int qsBc[]) {
    int i;
    for (i = 0; i < ASIZE; ++i)
        qsBc[i] = m + 1;
    for (i = 0; i < m; ++i)
        qsBc[(unsigned char)x[i]] = m - i;
}

int matchShift(char *x, int m, int ploc, int lshift, Pair *pat) {
    int i, j;
    for (; lshift < m; ++lshift) {
        i = ploc;
        while (--i >= 0) {
            j = pat[i].loc - lshift;
            if (j < 0)
                continue;
            if (pat[i].c != (unsigned char)x[j])
                break;
        }
        if (i < 0)
            break;
    }
    return lshift;
}

void preAdaptedGs(char *x, int m, int adaptedGs[], Pair *pat) {
    int lshift, i, ploc;

    adaptedGs[0] = lshift = 1;
    for (ploc = 1; ploc <= m; ++ploc) {
        lshift = matchShift(x, m, ploc, lshift, pat);
        adaptedGs[ploc] = lshift;
    }
    for (ploc = 0; ploc < m; ++ploc) {
        lshift = adaptedGs[ploc];
        while (lshift < m) {
            i = pat[ploc].loc - lshift;
            if (i < 0 || pat[ploc].c != (unsigned char)x[i])
                break;
            ++lshift;
            lshift = matchShift(x, m, ploc, lshift, pat);
        }
        adaptedGs[ploc] = lshift;
    }
}

void search(char *x, int m, char *y, int n) {
    int i, j;
    int adaptedGs[XSIZE + 1], qsBc[ASIZE];
    Pair pat[XSIZE];

    /* Tiền xử lý */
    computeMinShift(x, m);
    orderPattern(x, m, maxShiftPcmp, pat);
    preQsBc(x, m, qsBc);
    preAdaptedGs(x, m, adaptedGs, pat);

    /* Tìm kiếm */
    j = 0;
    while (j <= n - m) {
        i = 0;
        while (i < m && pat[i].c == (unsigned char)y[j + pat[i].loc])
            ++i;
        if (i >= m)
            printf("Tim thay tai vi tri %d\n", j);
        j += MAX(adaptedGs[i], qsBc[(unsigned char)y[j + m]]);
    }
}

Ví dụ minh họa

Xét mẫu x = "GCAGAGAG" (m = 8).

Trước hết tính minShift. Duyệt từng vị trí:

ix[i]lần trước cùng ký tựminShift[i]
0Gkhông có1
1Ckhông có2
2Akhông có3
3Gtại 03
4Atại 22
5Gtại 32
6Atại 42
7Gtại 52

Vị trí 2 (A) và vị trí 3 (G) có minShift = 3 lớn nhất, nên chúng được xếp so trước; các vị trí minShift = 2 xếp sau; vị trí 0 (minShift = 1) so sau cùng.

Vị trí cửa sổ j = 0 (y[0..7] = "GCATCGCA"): thuật toán so vị trí ưu tiên trước. Khi tới vị trí mang G mà y[0+3] = T, xảy ra sai lệch; nhờ đã ưu tiên các vị trí "dịch xa", adaptedGs tại đây cho lượng dịch lớn, cửa sổ nhảy nhanh về phía trước.

Vị trí cửa sổ j = 5 (y[5..12] = "GCAGAGAG"): mọi vị trí trong pat đều khớp, ghi nhận xuất hiện tại vị trí 5.

Tài liệu tham khảo