ℓ của mẫu.ℓ = ⌈log_σ(m)⌉, với σ là số ký tự khác nhau; đây là độ dài "vừa đủ" để mỗi factor tương đối hiếm.m - ℓ + 1, lớn hơn ý nghĩa so với bước của Skip Search khi ℓ nhỏ.Skip Search lập bucket theo từng ký tự đơn. Với bảng chữ nhỏ (ví dụ ADN chỉ 4 ký tự), mỗi ký tự xuất hiện rất nhiều lần trong mẫu, nên bucket dày và số ứng viên phải kiểm tra lớn.
Alpha Skip Search khắc phục bằng cách lập chỉ mục theo factor (đoạn con liên tiếp) độ dài ℓ thay vì một ký tự. Chọn ℓ = ⌈log_σ(m)⌉ sao cho số factor khả dĩ (σ^ℓ ≈ m) cân bằng với số factor thực có trong mẫu (m - ℓ + 1). Khi đó mỗi factor xuất hiện trung bình một số hằng lần, bucket trở nên thưa, và ta có thể nhảy qua văn bản với bước dài m - ℓ + 1. Đây chính là điều đưa thời gian trung bình xuống mức tối ưu O(n·log_σ(m) / m).
Chọn ℓ. Đếm số ký tự phân biệt σ trong mẫu, tính ℓ = ⌈log_σ(m)⌉ (chặn 1 ≤ ℓ ≤ m).
Trie các factor. Ta duyệt mọi factor x[i..i+ℓ-1] với i = 0 … m-ℓ, và chèn từng factor vào một trie (cây tiền tố). Tại nút lá ứng với mỗi factor, ta gắn một bucket chứa các vị trí bắt đầu i sinh ra factor đó. Nhờ trie, việc tra một factor của văn bản chỉ tốn ℓ bước đi xuống cây.
Tìm kiếm. Ta xét các mốc j cách nhau shift = m - ℓ + 1, bắt đầu từ j = m - ℓ. Tại mỗi mốc, đọc factor y[j..j+ℓ-1] và tra trie:
ℓ ký tự y[j], y[j+1], …. Nếu nửa chừng không có nhánh, factor này không phải factor của mẫu → bỏ qua mốc.i trong bucket, ứng viên đặt mẫu là s = j - i. Nếu 0 ≤ s ≤ n - m, so toàn bộ mẫu với y[s..s+m-1].s.Việc chọn shift = m - ℓ + 1 là an toàn vì mọi xuất hiện của mẫu (dài m) đều chứa ít nhất một mốc factor: hai mốc liên tiếp cách nhau m - ℓ + 1, nên một cửa sổ dài m luôn phủ trọn ít nhất một đoạn factor được canh với mốc.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ASIZE 256
/* Bucket: danh sách vị trí bắt đầu của factor trong mẫu */
typedef struct _cell {
int element;
struct _cell *next;
} *List;
/* Nút trie các factor */
typedef struct _trie {
struct _trie *child[ASIZE];
List bucket;
} Trie;
static Trie *newTrieNode(void) {
return (Trie *)calloc(1, sizeof(Trie));
}
static void freeTrie(Trie *t) {
int c;
List ptr;
if (t == NULL) return;
for (c = 0; c < ASIZE; ++c)
freeTrie(t->child[c]);
while (t->bucket != NULL) {
ptr = t->bucket;
t->bucket = ptr->next;
free(ptr);
}
free(t);
}
void search(char *x, int m, char *y, int n) {
int i, j, k, ell, sigma, shift, s;
int seen[ASIZE];
Trie *root, *node;
List ptr;
/* Tiền xử lý: ell = ceil(log_sigma m) */
memset(seen, 0, sizeof(seen));
sigma = 0;
for (i = 0; i < m; ++i)
if (!seen[(unsigned char)x[i]]) {
seen[(unsigned char)x[i]] = 1;
++sigma;
}
if (sigma > 1)
ell = (int)ceil(log((double)m) / log((double)sigma));
else
ell = 1;
if (ell < 1) ell = 1;
if (ell > m) ell = m;
/* Dựng trie các factor độ dài ell của mẫu */
root = newTrieNode();
for (i = 0; i + ell <= m; ++i) {
node = root;
for (k = 0; k < ell; ++k) {
unsigned char c = (unsigned char)x[i + k];
if (node->child[c] == NULL)
node->child[c] = newTrieNode();
node = node->child[c];
}
ptr = (List)malloc(sizeof(struct _cell));
ptr->element = i;
ptr->next = node->bucket;
node->bucket = ptr;
}
/* Tìm kiếm: nhảy theo bước m - ell + 1 */
shift = m - ell + 1;
for (j = m - ell; j + ell <= n; j += shift) {
node = root;
for (k = 0; k < ell && node != NULL; ++k)
node = node->child[(unsigned char)y[j + k]];
if (node == NULL)
continue;
for (ptr = node->bucket; ptr != NULL; ptr = ptr->next) {
s = j - ptr->element;
if (s >= 0 && s <= n - m && memcmp(x, y + s, m) == 0)
printf("Tim thay tai vi tri %d\n", s);
}
}
freeTrie(root);
}Xét mẫu x = "GCAGAGAG" (m = 8) trên văn bản y = "GCATCGCAGAGAGTATACAGTACG".
Mẫu dùng σ = 3 ký tự phân biệt (G, C, A), nên ℓ = ⌈log₃ 8⌉ = ⌈1.89⌉ = 2. Ta lập chỉ mục các factor độ dài 2 của mẫu:
| factor | các vị trí bắt đầu |
|---|---|
| GC | 0 |
| CA | 1 |
| AG | 2, 4, 6 |
| GA | 3, 5 |
Bước nhảy shift = m - ℓ + 1 = 7, bắt đầu tại j = m - ℓ = 6.
Mốc j = 6 (factor y[6..7] = "CA"): tra trie → bucket {1}. Ứng viên s = 6 - 1 = 5. So x với y[5..12] = "GCAGAGAG" → khớp toàn bộ. Tìm thấy xuất hiện tại vị trí 5.
Mốc j = 13 (factor y[13..14] = "TA"): tra trie → không có nhánh cho T ở gốc, factor không thuộc mẫu → bỏ qua ngay.
Mốc j = 20 (factor y[20..21] = "TA"): tương tự, bỏ qua.
Chỉ với ba mốc và một lần kiểm tra đầy đủ, thuật toán tìm đúng xuất hiện duy nhất tại vị trí 5. Vì factor "CA" khá hiếm, bucket của nó chỉ có một phần tử — minh hoạ vì sao lập chỉ mục theo factor giúp bucket thưa hơn so với lập chỉ mục theo ký tự đơn.