Thuật toán Skip Search

Đặc điểm chính

Ý tưởng

Nếu ta đứng tại vị trí j trong văn bản và biết ký tự y[j], thì mẫu chỉ có thể phủ lên y[j] ở những cách canh mà một ký tự nào đó của mẫu trùng với y[j]. Nói cách khác, nếu $y[j] = c$ và c xuất hiện trong mẫu tại các vị trí $i_1, i_2, \dots$, thì các vị trí đặt mẫu khả dĩ là $j - i_1, j - i_2, \dots$.

Skip Search khai thác điều này: với mỗi ký tự lưu sẵn danh sách các vị trí của nó trong mẫu (bucket). Khi đọc y[j], ta lấy ngay bucket của y[j] và với mỗi vị trí i trong đó, thử đặt mẫu tại $j - i$. Vì mỗi lần chỉ cần một ký tự văn bản là sinh được các ứng viên, ta có thể nhảy cửa sổ theo bước m và vẫn không bỏ sót xuất hiện nào.

Mô tả chi tiết

Tiền xử lý — các bucket. Với mỗi ký tự c của bảng chữ, z[c] là một danh sách liên kết chứa mọi chỉ số i sao cho $x[i] = c$. Nếu c không xuất hiện trong mẫu, danh sách rỗng. Tổng độ dài các danh sách bằng m, nên dựng chúng tốn $O(m + \sigma)$.

Tìm kiếm. Ta xét các vị trí $j = m-1, 2m-1, 3m-1, \dots$ (bước nhảy bằng m). Việc chọn các mốc cách nhau đúng m là an toàn: bất kỳ xuất hiện nào của mẫu bắt đầu ở s đều phủ khoảng $[s, s+m-1]$ dài đúng m, nên chắc chắn chứa ít nhất một trong các mốc j. Tại mỗi mốc j:

  1. Lấy bucket z[y[j]].
  2. Với mỗi vị trí i trong bucket, ứng viên đặt mẫu là $s = j - i$. Nếu $0 \le s \le n - m$, ta so toàn bộ mẫu với $y[s..s+m-1]$.
  3. Nếu khớp hết, ghi nhận xuất hiện tại s.

Với văn bản ngẫu nhiên trên bảng chữ đủ lớn, đa số bucket được truy cập là rỗng hoặc chỉ có vài phần tử, nên số lần kiểm tra ít; cộng với bước nhảy m giữa các mốc, thuật toán rất nhanh trên trung bình. Trường hợp xấu nhất (mẫu và văn bản chỉ dùng một ký tự) thì mỗi mốc có tới m ứng viên, mỗi ứng viên tốn m phép so sánh, cho $O(mn)$.

Cài đặt bằng C

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

#define ASIZE 256

/* Danh sách liên kết các vị trí (bucket) */
typedef struct _cell {
    int element;
    struct _cell *next;
} *List;

void search(char *x, int m, char *y, int n) {
    int i, j;
    List ptr, z[ASIZE];

    /* Tiền xử lý: với mỗi ký tự, danh sách vị trí trong mẫu */
    memset(z, 0, ASIZE * sizeof(List));
    for (i = 0; i < m; ++i) {
        ptr = (List)malloc(sizeof(struct _cell));
        ptr->element = i;
        ptr->next = z[(unsigned char)x[i]];
        z[(unsigned char)x[i]] = ptr;
    }

    /* Tìm kiếm: nhảy qua văn bản theo bước m */
    for (j = m - 1; j < n; j += m)
        for (ptr = z[(unsigned char)y[j]]; ptr != NULL; ptr = ptr->next)
            if (j - ptr->element <= n - m &&
                memcmp(x, y + j - ptr->element, m) == 0)
                printf("Tim thay tai vi tri %d\n", j - ptr->element);

    /* Giải phóng bộ nhớ các bucket */
    for (i = 0; i < ASIZE; ++i)
        while (z[i] != NULL) {
            ptr = z[i];
            z[i] = ptr->next;
            free(ptr);
        }
}

Ví dụ minh họa

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

Bucket sau tiền xử lý (mỗi ký tự → các vị trí trong mẫu):

ký tựvị trí trong mẫu
G0, 3, 5, 7
C1
A2, 4, 6

Mốc $j = 7$ ($y[7] = A$): bucket của A là $\{2, 4, 6\}$. Các ứng viên là $s = 7-2 = 5$, $s = 7-4 = 3$, $s = 7-6 = 1$.

Mốc $j = 15$ ($y[15] = T$): bucket của T rỗng → không có ứng viên, bỏ qua ngay.

Mốc $j = 23$ ($y[23] = G$): bucket của G là $\{0, 3, 5, 7\}$, cho các ứng viên $s = 23, 20, 18, 16$; kiểm tra thấy đều vượt $n - m = 16$ hoặc không khớp.

Chỉ với vài lần đọc ký tự, thuật toán đã quét hết văn bản và tìm đúng xuất hiện duy nhất ở vị trí 5.

Tài liệu tham khảo