Thuật toán Simon

Đặc điểm chính

Ý tưởng

Otomat so khớp chuỗi kinh điển (xem thuật toán DFA) có m + 1 trạng thái 0, 1, …, m; từ trạng thái q gặp ký tự x[q] thì đi tiếp sang q+1 (cạnh "tiến"), còn với mọi ký tự khác thì lùi về một trạng thái nào đó (cạnh "lui"). DFA đầy đủ phải lưu σ cạnh cho mỗi trạng thái, tốn O(m·σ) bộ nhớ.

Simon nhận xét rằng đa số các cạnh lui đều dẫn về cùng những trạng thái mà ta có thể suy lại từ bảng biên của mẫu; chỉ một số ít cạnh là thật sự "đáng kể" — tức không thể tái tạo bằng quy tắc mặc định. Cụ thể, cạnh lui từ q theo ký tự c là đáng kể khi nó dẫn tới một trạng thái lớn hơn trạng thái mà quy tắc mặc định (dựa trên biên) đưa ra. Người ta chứng minh được số cạnh đáng kể như vậy không vượt quá m − 1. Nhờ đó ta lưu ôtômat bằng O(m) bộ nhớ mà vẫn tính được hàm chuyển trong thời gian phân bổ hằng số.

Mô tả chi tiết

Trước hết tính bảng biên border[q] = độ dài biên dài nhất của x[0..q-1], giống Morris-Pratt.

Với mỗi trạng thái q (từ 2 đến m − 1), ta xét chuỗi các biên b = border[q], border[border[q]], …. Với mỗi biên b > 0 mà ký tự đi sau nó x[b] khác x[q] (nghĩa là không phải cạnh tiến), cạnh chuyển từ q theo ký tự x[b] sang trạng thái b + 1 là một cạnh đáng kể — trừ khi đã có một cạnh đáng kể khác từ q theo cùng ký tự x[b] dẫn tới trạng thái lớn hơn (khi đó cạnh dài hơn "phủ" cạnh này). Ta lưu tập cạnh đáng kể của mỗi trạng thái trong một danh sách móc nối L[q].

Hàm chuyển δ(q, c) được tính như sau:

  1. Nếu q < m và c == x[q]: trả về q + 1 (cạnh tiến).
  2. Ngược lại, dò danh sách L[q]: nếu có cạnh đáng kể theo ký tự c thì trả về trạng thái đích của nó.
  3. Nếu không: áp quy tắc mặc định — trả về 1 khi c == x[0], và 0 trong các trường hợp còn lại.

Pha tìm kiếm chỉ việc chạy ôtômat: đọc lần lượt từng ký tự văn bản, cập nhật trạng thái; mỗi khi trạng thái đạt m thì báo tìm thấy và lùi trạng thái về border[m] để tiếp tục.

Cài đặt bằng C

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

typedef struct Cell {
    int target;           /* trạng thái đích của cạnh đáng kể (>= 2) */
    struct Cell *next;
} Cell;

static int transition(char *x, int m, Cell **L, int q, char c) {
    Cell *p;
    if (q < m && c == x[q])
        return q + 1;                 /* cạnh tiến */
    for (p = L[q]; p != NULL; p = p->next)
        if (c == x[p->target - 1])    /* x[b] với b = target-1 */
            return p->target;         /* cạnh lui đáng kể */
    return (c == x[0]) ? 1 : 0;       /* cạnh mặc định */
}

void preSimon(char *x, int m, Cell **L, int *border) {
    int q, b, covered;
    Cell *cell, *p;

    border[0] = -1;
    for (q = 1; q <= m; ++q) {
        b = border[q - 1];
        while (b > -1 && x[b] != x[q - 1])
            b = border[b];
        border[q] = b + 1;
    }

    for (q = 0; q <= m; ++q)
        L[q] = NULL;

    for (q = 2; q < m; ++q)
        for (b = border[q]; b > 0; b = border[b]) {
            if (x[b] == x[q])
                continue;             /* trùng cạnh tiến, bỏ qua */
            covered = 0;
            for (p = L[q]; p != NULL; p = p->next)
                if (x[p->target - 1] == x[b]) { covered = 1; break; }
            if (!covered) {
                cell = (Cell *) malloc(sizeof(Cell));
                cell->target = b + 1;
                cell->next = L[q];
                L[q] = cell;
            }
        }
}

void search(char *x, int m, char *y, int n) {
    int j, q;
    Cell **L = (Cell **) malloc((m + 1) * sizeof(Cell *));
    int *border = (int *) malloc((m + 1) * sizeof(int));

    preSimon(x, m, L, border);

    q = 0;
    for (j = 0; j < n; ++j) {
        q = transition(x, m, L, q, y[j]);
        if (q == m) {
            printf("Tim thay tai vi tri %d\n", j - m + 1);
            q = border[m];
        }
    }

    for (j = 0; j <= m; ++j) {
        Cell *p = L[j];
        while (p) { Cell *t = p->next; free(p); p = t; }
    }
    free(L);
    free(border);
}

Ví dụ minh họa

Xét x = "GCAGAGAG" (m = 8) trên y = "GCATCGCAGAGAGTATACAGTACG" (n = 24).

Bảng biên:

q012345678
border[q]−100010101

Các cạnh lui đáng kể tìm được (ngoài các cạnh tiến và cạnh mặc định về 0/1):

Chạy ôtômat trên các ký tự đầu:

q=0 --G--> 1 --C--> 2 --A--> 3 --T--> 0 --C--> 0 --G--> 1
    --C--> 2 --A--> 3 --G--> 4 --A--> 5 --G--> 6 --A--> 7
    --G--> 8   => tìm thấy tại vị trí 5, lùi về border[8]=1

Ta thấy hầu hết các bước chỉ dùng cạnh tiến hoặc cạnh mặc định; các cạnh đáng kể (như 4 --C--> 2) chỉ được dùng khi văn bản dẫn thuật toán vào đúng tình huống cần đến chúng.

Tài liệu tham khảo