Các máy trạng thái hữu hạn (finite-state machine-FSM) thông thường được định nghĩa khá phức tạp, tùy thuộc vào ngữ cảnh ứng dụng. Định nghĩa ở đây mình gắn luôn với bài toán tìm kiếm xâu, do đó, có đôi chút khác biệt so với các định nghĩa thông thường. Nhắc lại, trong bài toán tìm kiếm xâu, ta có một văn bản (text) biểu diễn bới xâu $T[1,2,\ldots,n]$ và một mẫu (pattern) biểu diễn bởi xâu $P[1,2,\ldots,m]$. Ta muốn tìm vị trí xâu $P$ xuất hiện trong văn bản $T$. Chi tiết các bạn xem thêm ở các bài viết khác trong cùng mục tìm kiếm xâu tại đây.

Máy trạng thái hữu hạn

Máy trạng thái hữu hạn biểu diễn xâu mẫu $P[1,\ldots,m]$ là một đồ thị có hướng có $m+1$ nút sắp xếp trên một đường thẳng và được đánh số từ $0$ đến $m$. Giữa nút thứ $i-1$ và $i$, $1 \leq i \leq m$, có một cạnh có hướng được gọi là cạnh khớp (success edge). Cạnh khớp này có nhãn là kí tự $P[i]$ của xâu $P$. Mỗi nút $P[i]$, ngoại trừ nút $0$ và nút thứ $m$, còn có một cạnh hướng ra khác được gọi là cạnh không khớp . Nút $1$ có cạnh không khớp tới nút $0$. Các cạnh không khớp khác nối nút thứ $i$ với một nút thứ $j$ nào đó với $j < i$. Ví dụ về một máy trạng thái hữu hạn với $P[1,\ldots,7] = \{\mathrm{ababaca}\}$ được biểu diễn bởi hình dưới đây. Các cạnh có nhãn màu xanh là các cạnh khớp. Các cạnh màu đỏ (không có nhãn) là các cạnh không khớp.

Mình sẽ giải thích tại sao các cạnh màu đỏ lại xuất hiện trong hình trên theo thứ tự như vậy ngay sau đây. Tạm thời bây giờ chưa cần chú ý đến nó vội. Bạn đọc hãy quan sát kĩ hình vẽ và tự đối chiếu với các khái niệm trong định nghĩa máy trạng thái hữu hạn.

Ta nhận thấy nhãn của các cạnh màu xanh khi gộp lại chính là xâu $P$. Hơn nữa, nếu ta gộp nhãn của các cạnh từ nút $0$ tới nút thứ $i$ thì ta thu được tiền tố $P[1,2,\ldots,i]$ của $P$. Nếu quan sát kĩ hơn thì ta có thể thấy rằng:

Luật cạnh không khớp: Nút $i$ có một cạnh không khớp tới nút $j$ ($j < i$) khi và chỉ khi $j$ là số lớn nhất nhỏ hớn $i$ sao cho $P[1,2,\ldots,j]$ là hậu tố của $P[1,2,\ldots,i]$.

Ví dụ nhìn vào hình trên ta thấy nút $4$ có một cạnh không khớp tới nút $2$ vì $P[1,2] = \{\mathrm{ab}\}$ là hậu tố của $P[1,2,3,4] = \{\mathrm{abab}\}$. Bạn đọc nên dành thời gian để kiểm tra luật trên với các nút khác.

Bây giờ ta sẽ biến luật cạnh không khớp trên thành giải thuật để xác định các cạnh không khớp. Hiển nhiên với mỗi $i$, ta chỉ cần duyệt từ $P[1]$ cho đến khi tìm được $P[j]$ thỏa mãn luật cạnh không khớp. Như vậy, ta có thể xây dựng cạnh không khớp cho nút $i$ trong thời gian $O(i)$, do đó:

Tuy nhiên, ta có thể sử dụng quy hoạch động để xây dựng cạnh không khớp nhanh hơn. Gọi $F[1,2,\ldots,m-1]$ là mảng trong đó $F[i] = j$ nếu có một cạnh không khớp từ nút $i$ tới nút $j$ ($j$ < $i$). Ta có $F[1] = 0$. Giả sử ta đã tính được $F[1,2,\ldots,i-1]$. Làm sao ta có thể tính được $F[i]$? (bạn đọc nên tự suy nghĩ một lúc trước khi xem lời giải dưới đây).

Nếu $F[i-1] = j_0$, ta suy ra $P[1,\ldots,j_0]$ là hậu tố của $P[1,2,i-1]$ (theo luật cạnh không khớp). Do đó nếu $P[j_0+1] = P[i]$ thì ta chỉ cần gán $F[i] = j_0+1$ (hình (a) trong hình minh họa dưới đây). Ví dụ trên với $i = 4$, ta thấy $F[i-1] = F[3] = 1$ và $P[2] = P[4]$, do đó ta gán $F[4] = 2$. Tuy nhiên, cuộc sống không có dễ dàng vậy nếu $P[j_0+1] \not= P[i]$. Trong trường hợp này, ta sẽ phải xét $j_{1} = F[j_0]$ và lại so sánh $P[j_1+1]$ với $P[i]$. Chú ý ở đây $P[1,\ldots,j_1]$ là hậu tố của $P[1,\ldots, j_0]$, do đó, nó cũng là hậu tố của $P[1,2,i-1]$ vì ta đã biết $P[1,\ldots,j_0]$ là hậu tố của $P[1,2,i-1]$. Từ đó suy ra nếu $P[j_1+1]= P[i]$, ta sẽ gán $P[i] = P[j_1+1]$ (xem hình (b) trong hình minh họa dưới đây). Nếu không ta sẽ tiếp tục lặp lại như trên. Trường hợp xấu nhất, đến một lúc nào đó ta sẽ trở về vị trí $j_c = 0$ sau $c$ bước (tại sao?) với một số $c$ nào đó, và do đó, ta sẽ gán $F[i] = 0$ vì hiển nhiên $P[1,\ldots,0]= \emptyset$ (theo quy ước) là một hậu tố của $P[1,2,\ldots,i]$.

Ta có thuật toán sau:

 
Code C:

int * constructFSM(char *P){
int m = strlen(P)-1; // the first char of P is empty
int *F = (int *)malloc(m*sizeof(int));
F[0] = -1;
int i = 1, j = 0;
for(; i < m; i++){
j = F[i-1];
while(P[j+1] != P[i]&& j >= 0){
j = F[j];
}
F[i] = j +1;
}
//	print_array(F,m-1);
return F;
}

Việc chứng minh (bằng quy nạp) rằng nếu nếu $F[i]$ được gán bằng số $j$ nào đó theo thuật toán trên thì $j$ là số lớn nhất nhỏ hơn $i$ thỏa mãn tính chất của luật cạnh không khớp coi như bài tập cho bạn đọc. Mặc dù $F[0]$ không có trong định nghĩa, ta vẫn thêm vào mảng $F$ phần tử $F[0] = -1$ để cho việc viết giả mã sáng sủa hơn.

Remark Thông qua mảng $F[1,\ldots,m-1]$, ta đã "biểu diễn" ngắn gọn được toàn bộ máy trạng thái hữu hạn. Ngoài ra, nếu tinh ý, các bạn sẽ phát hiện ra rằng thuật toán xây dựng cạnh không khớp trên chính là thuật toán tính hàm Failure trong thuật toán KMP.

Phân tích thuật toán: Nếu bạn đọc đã đọc phân tích của hàm Failure trước đây, có thể dễ dàng nhận thấy thời gian của thuật toán này là $O(m)$. Ở đây mình nhắc lại ngắn gọn ý tưởng: độ phức tạp của thuật toán có cùng tiệm cận với số phép so sánh bằng và số phép so sánh không bằng. Mỗi lần so sánh bằng ($P[j+1] = P[i]$) thì ta tăng cả hai biến $i$ và $j$ lên $1$. Mỗi lần so sánh không bằng ($P[j+1] \not= P[i]$) thì ta lại giảm $j$. Do số lần ta giảm $j$ không thể vượt quá số lần ta tăng $j$, số phép so sánh không bằng sẽ nhỏ hơn số phép so sánh bằng. Do đó, độ phức tạp của thuật toán có cùng tiệm cận với số phép so sánh bằng và là $O(m)$.

 
Thuật toán KMP sử dụng FSM

Khi so sánh hai xâu $T[1,2,\ldots,n]$ và $P[1,2,\ldots,m]$, ta sẽ so sánh từng kí tự. Vấn đề mấu chốt là chúng ta sẽ xử lí như thế nào nếu $T[i] \not= P[j] $ ($j > 1$) khi ta đang so sánh hai kí tự tương ứng trong văn bản và trong xâu mẫu. Thuật toán trâu bò sẽ lùi một số đơ vị là $j-2$ và tiếp tục so sánh $T[i-j+2]$ với $P[1]$. Do đó trong trường hợp xấu nhất, số phép so sánh là $O(nm)$.

Tuy nhiên, ta có thể nhận xét thấy là nếu ta đang so sánh $T[i]$ với $P[j]$, có nghĩa là $P[j-1] = T[i-1], P[j-2] = T[i-2], \ldots, P[1] = T[i-j+1]$. Hay nói cách khác, $P[1,2,\ldots, j-1]$ là hậu tố của $T[1,2,\ldots,i-1]$. Do đó, nếu $T[i] \not= P[j]$, ta chỉ cần đi theo cạnh không khớp của nút $i-1$ để lùi về nút $j' = F[j-1]$. Theo luật cạnh không khớp, $P[1,\ldots,j']$ là hậu tố của $P[1,\ldots, j-1]$ và do đó cũng là hậu tố của $T[1,2,\ldots,i-1]$. Hay nói cách khác, $P[j'] = T[i-1], \ldots, P[1] = T[i-j']$. Do đó, ta chỉ cần so sánh $P[j'+1]$ với $T[i]$ và đệ quy. Dựa vào những quan sát này, ta có thuật toán sau:

Code C:

// since string in C is indexed from 0, to be consistent with the pseudocode, I put
// a space character in T[0] and P[0] and the real strings are  T[1,...,n] and P[1,....,m]
int  kmp_as_fsm(char *T, char *P){
int n = strlen(T)-1; // the first character of T is empty
int m = strlen(P)-1; // the first character of P is empty
int *F = constructFSM(P);
int i = 1, j = 0;
for(; i <= n; i++){
while(T[i] != P[j+1] && j >= 0){
j = F[j];
}
j++;
if(j == m){
return i-m+1;
}
}
return -1;
}

Phân tích thuật toán (giống như phân tích khi xây dựng FSM) coi như bài tập cho bạn đọc. Như vậy máy trạng thái hữu hạn cho chúng ta một cách nhìn khác và đơn giản hơn về thuật toán KMP. Tuy nhiên, nếu chỉ có thể thì cũng không thể nói lên được hết tầm quan trọng của máy trạng thái hữu hạn trong tìm kiếm xâu. Trong bài tiếp theo, mình sẽ trình bày ứng dụng khác của máy trạng thái hữu hạn trong tìm kiếm đa mẫu (multiple patterns) mà cụ thể là thuật toán Aho-Corasick [2].

Code đầy đủ: kmp-as-fsm.
Tham khảo

[1] Knuth, Donald E., James H. Morris, Jr, and Vaughan R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing 6.2 (1977): 323-350.
[2] Aho, Alfred V., and Margaret J. Corasick. Efficient string matching: an aid to bibliographic search. Communications of the ACM 18.6 (1975): 333-340.
[3] Jeff Erickson. Lecture Notes on String Matching, UIUC, 2014.