Thuật toán BoyerMoore (BM) là một thuật toán tìm kiếm xâu khá hiệu quả trong thực tế, tuy rằng về mặt lý thuyết, số phép so sánh trong trường hợp tồi nhất là $O(mn)$ (không tốt hơn thuật toán trâu bò). Ta phát biểu lại bài toán tìm kiếm xâu như sau:

Thuật toán BM gồm hai bước chính, bắt đầu từ vị trí $1$ của văn bản $T$:

1. So sánh $T[i,i+1,\ldots, i+m-1]$ với $P[1,2,\ldots, m]$ theo chiều từ phải sang trái của $P$.
2. Tại vị trí xảy ra không khớp, $T[i+j] \not= P[j+1]$, $0 \leq j \leq m-1$, dịch $P$ lên $x$ đơn vị ($x$ có giá trị bao nhiêu sẽ thảo luận ở dưới).

Như vậy, thuật toán BM sẽ đối sánh $T$ và $P$ theo chiều từ phải sang trái của $P$. Liệu so sánh từ phải sang trái có tốt hơn từ trái sang phải như trong thuật toán trâu bò? Bằng cách áp dụng thêm luật kí tự tồi (bad character rule) và luật hậu tố tốt, thuật toán BM trong thực tế nhanh hơn hẳn thuật toán trâu bò.

Luật kí tự tồi

Trước hết chúng ta hãy xem xét ví dụ sau để hiểu luật này.

Ví dụ: $T= \mathrm{FINDIFAHAYXEACKNEXDLE}$ và $P = \mathrm{NEXDLE}$.

1. Tại bước đầu tiên $(i=1)$ so sánh $T[1,2,\ldots, 6]$ với $P[1,2,\ldots, 6]$, ta thấy rằng $T[6] \not= P[6]$ (chú ý ta so sánh từ phải sang trái của $P$). Do $T[6] \not \in P$, ta ngay lập tức có thể dịch $P$ lên $6$ đơn vị và bắt đầu so sánh $T[7,8, \ldots, 12]$ với $P[1,2,\ldots,6]$
2. Tại bước này ta sẽ gặp vị trí không khớp $T[11] \not= P[5]$, vì $T[11] = P[3]$, ta sẽ dịch $P$ lên $2$ đơn vị để cho $T[11]$ thẳng hàng với $P[3]$ và tiếp tục so sánh $T[9,\ldots, 14]$ với $P[1,2,\ldots,6]$.
3. Tại bước này, $T[14] \not= P[6]$ và $T[14] \not\in P$, ta dịch $P$ lên $6$ đơn vị và so sánh $T[15,\ldots, 20]$ với $P[1,2,\ldots, 6]$.
4. $\ldots$ Tiếp tục các bước như trong hình vẽ dưới đây, cuối cùng ta tìm được mẫu $P$ ở vị trí $i=16$.

Hi vọng ví dụ trên đã thuyết phục bạn rằng đối sánh thừ phải sang trái thực sự nhanh hơn từ trái sang phải. Tại bước 1 và 3 trong ví dụ trên, ta có thể dịch lên $6$ đơn vị ở mỗi bước chỉ dùng 1 phép so sánh. Do đó, ta có thể suy ra trong trường hợp tốt nhất, ta chỉ cần $O(\frac{n}{m} + m)$ phép so sánh để tìm ra $P$ trong $T$.

Luật kí tự tồi sẽ cho phép chúng ta xác định giá trị của $x$ trong bước thứ 2 của thuật toán BM. Tại mỗi bước đối sánh một xâu con của $T$ với $P$, kí tự $T[k]$ gọi là kí tự tồi (bad character) nếu không khớp xảy ra tại kí tự này $T[k] \not= P[j]$. Trong ví dụ trên, tại bước thứ 1, kí tự $T[6]$ là kí tự tồi. Hay trong bước 2, kí tự $T[11]$ là kí tự tồi.

Mỗi lần bắt gặp một kí tự tồi, chúng ta dịch $i$ theo luật sau:

Luật kí tự tồi: Dịch $P$ lên một số $x$ đơn vị sao cho kí tự tồi $T[k]$ khớp với kí tự $P[s]$ là kí tự xuất hiện gần với $P[m]$ nhất ($s$ lớn nhất). Nếu $s > j$ hoặc không tồn tại kí tự $P[s]$ như vậy thì ta dịch $P$ lên 1.

Áp dụng luật kí tự tồi vào bước thứ 2 của ví dụ trên, $T[11] \not= P[5]$ ($k=11, j = 5$), ta dịch $P$ lên $x$ đơn vị sao cho $T[11]$ khớp với $P[3]$ vì $P[3]$ là kí tự xuất hiện gần với $P[6]$ nhất và khớp với $T[11]$ ($P[3] = T[11]$). Do đó, ta phải dịch $P$ lên $x = 2$ đơn vị.

Để thực thi luật kí tự tồi, với mỗi kí tự $\sigma \in \Sigma$, gọi $R[\sigma]$ là vị trí xuất hiện của kí tự $\sigma$ gần với $P[m]$ nhất. Nếu $\sigma \not\in P$, $R[\sigma] = 0$. Theo quy luật kí tự tồi, mỗi bước chúng ta sẽ dịch $P$ một đoạn là:

$\max(1, j - R[T[k]]) \qquad (1)$

Thủ tục BadCharBackup dưới đây cập nhật bảng $R[1,2,\ldots, |\Sigma|]$ trong thời gian $O(|\Sigma|)$. Giả mã của thuật toán BM sử dụng luật kí tự tồi như sau:

 
Code của giả mã bằng C:

int BMmatcher(int n, int m){
badCharBackup(m);
int i = 1, j = 0, p = 0, skip = 0;
while(i <= n-m+1){
skip = 0;
j = m;
while(j >= 1 && skip == 0){
if(T[i+j-1] != P[j]){
p = T[i+j-1]-96;
skip = max(1, j - R[p]);
}
j--;
}
if(skip == 0) {
return i;
}
i = i + skip; // shift P by skip amount
}
return -1;
}

void badCharBackup(int m){
int i = 0;
memset(R, 0, sizeof(R)); // set everything to 0
for(i = 1; i <= m; i++){
R[P[i] - 96] = i;
}
}

Luật kí tự tồi mở rộng

Xét ví dụ khi bạn đang so sánh một đoạn $T[4,5,6,\ldots, 10]= \mathrm{YHAXAXA}$ của văn bản $T$ nào đó với $P[1,2,\ldots, 7] = \mathrm\{YXCDAXA\}$, bạn sẽ thấy không khớp xảy ra ở vị trí $T[7] \not= P[4]$ ($k = 5, j = 3$). Ta có kí tự khớp với $T[7]$ và gần $P[7]$ nhất là $P[6]$, theo luật kí tự tồi, ta dịch $P$ lên $1$ đơn vị vì $6 > 3$. Tuy nhiên ta có thể dịch $P$ lên 3 đơn vị để $T[7]$ khớp với $P[2]$ (thay vì $P[6]$). Luật kí tự tồi mở rộng phát biểu như sau:

Luật kí tự tồi mở rộng: Dịch $P$ lên một số $x$ đơn vị sao cho kí tự tồi $T[k]$ khớp với kí tự $P[s]$ xuất hiện gần nhất bên trái của $P[j]$.

Như vậy, với mỗi gía trị không khớp $T[k] \not= P[j]$, ta phải tìm $s$ lớn nhất sao cho:

$P[s] = T[k], s < j \qquad (2)$

và dịch $P$ sao cho $T[k] = P[s]$.

Gọi $S[1,2,\ldots, |\Sigma|][1,2,\ldots,m]$ là bảng 2 chiều trong đó $S[\sigma,j] = s$ tương ứng với $T[k] = \sigma$ và vị trí xảy ra không khớp là $j$ trong mẫu $P$. Thủ tục ExtendedBadChar cập nhật bảng $S[1,2,\ldots, |\Sigma|][1,2,\ldots,m]$ trong thời gian $O(|\Sigma|m)$ ($ = O(m)$ nếu số kí tự trong bảng chữ cái không nhiều). Thuật toán BM với luật kí tự tồi mở rộng như sau:

Code của giả mã bằng C:

void extendedBadChar(int m, int *S){
int X[28];
memset(X, 0, sizeof(X));
int i = 0,k = 0;
for(i = 1; i <= m ; i++){
for(k = 1; k < 28; k++){
*((S + k*(m+1)) + i) = X[k];  //  S[k][i] = X[k];

}
X[P[i] - 96] = i;
}
}

Chúng ta có thể tiết kiệm bộ nhớ bằng cách thay bảng $S[|\Sigma|][m]$ bằng danh sách liên kết, mỗi danh sách cho một kí tự của $P$ và mỗi danh sách của một kí tự lưu các vị trí xuất hiện của kí tự đó trong $P$, sắp xếp theo chiều giảm dần của vị trí. Bằng phân tích khấu trừ như trong thuật toán KMP, chúng ta cũng có thể chứng minh rằng lưu trữ bằng danh sách liên kết như vậy tối đa sẽ mất thời gian gấp đôi thuật toán FastBMMatcher với mảng hai chiều $S[|\Sigma|][m]$ (không tính thời gian khởi tạo $S$). Một cách khác là chúng ta cũng có thể thay thế danh sách liên kết bằng các cấu trúc khác để tăng thời gian tìm kiếm. Ở đây mình không đi sâu vào các vấn đề như vậy. Cũng như luật kí tự tồi, thời gian tiệm cận của thuật toán BM trong trường hợp xấu nhất vẫn không đổi và bằng $O(mn)$.

Chỉ sử dụng luật kí tự tồi không đủ để giảm thời gian tiệm cận của thuật toán BM và thực tế, thuật toán vẫn chưa đủ nhanh và khó mở rộng một cách hiệu quả ra trường hợp tìm tất cả sự xuất hiện của $P$ trong $T$. Ví dụ khi bạn muốn tìm tất cả các vị trí xuất hiện của xâu $P = \mathrm{AA\ldots A}$ ($m$ kí tự $\mathrm{A}$) trong $T = \mathrm{AAA\ldots, A}$ ($n$ kí tự $\mathrm{A}$). Kể cả áp dụng luật kí tự tồi mở rông, thời gian chaỵ vẫn là $O(mn)$. Một luật nữa được đề xuất để cải tiến thuật toán đó là luật hậu tố tốt (good suffix rule). Phiên bản đầu tiên của luật hậu tố tốt vẫn có thời gian tồi nhất $O(mn)$. Phiên bản mình trình bày ở đây bao gồm cả cải tiến của Galil [5] có thời gian $O(m+n)$ trong trường hợp tồi nhất.

Luật hậu tố tốt

Luật hậu tố tốt chúng ta phát biểu trong phần này mạnh hơn phát biểu gốc cuả thuật toán Boyer-Moore [1]. Phát biểu gốc của thuật toán vẫn chưa đủ để chứng minh thời gian trong trường hợp tồi nhất là tuyến tính. Trước khi đi sâu vào phát biểu và thực thi luật hậu tố tốt, mình recommend bạn đọc thuật toán Z trước vì thực thi luật này sẽ sử dụng hàm $Z$ trong bước tiền xử lí. Luật hậu tố tốt khá dài và khó hiểu.

Luật hậu tố tốt: Giả sử khi so sánh, một xâu con $T_{\mathrm{sub}}$ của văn bản $T$ khớp với hậu tố của mẫu $P$, nhưng kí tự liền kề bên trái của $T_{\mathrm{sub}}$ không khớp với kí tự tương ứng trong $P$. Tìm một xâu con $\overline{T_{\mathrm{sub}}}$ (nếu có) phải nhất (right most-- gần với kí tự cuối $P[m]$ nhất) của $P$ thỏa mãn: $(1)$ $\overline{T_{\mathrm{sub}}}$ không phải là hậu tố của $P$ và $(2)$ kí tự liền kề bên trái của $\overline{T_{\mathrm{sub}}}$ khác với kí tự liền kề bên trái của hậu tố $T_{\mathrm{sub}}$ của $P$. Dịch $P$ sao cho $\overline{T_{\mathrm{sub}}}$ khớp với $T_{\mathrm{sub}}$ trong $T$.

Nếu $\overline{T_{\mathrm{sub}}}$ không tồn taị, dịch $P$ một số lượng ít nhất sao cho: $(3)$ Kí tự đầu tiên của $P$ vượt quá kí tự đầu tiên của $T_{\mathrm{sub}}$ và $(4)$ tiền tố của $P$ khớp với hậu tố của $T_{\mathrm{sub}}$. Nếu không thể dịch $P$ để thỏa mãn điều kiện đó, dịch $P$ lên $m$ đơn vị

Trường hợp ta tìm tất cả sự xuất hiện của $P$ trong $T$, sau khi đã tìm thấy $P$, ta dịch $P$ một lượng ít nhất (> 0) sao cho tiền tố của $P$ khớp với hậu tố của $P$ trong $T$. Trong trường hợp không thể dịch như vậy, dịch $P$ lên $m$ đơn vị.

Có lẽ chỉ đọc luật thôi đã mệt rồi. Nếu bạn đọc một lần chưa hiểu thì .... đọc lại vậy.

Xét ví dụ sau: $T[1,2,\ldots, 18] = \mathrm{PRSTABSTUBABVQXRST}$ và $P[1,2,\ldots, 10] = \mathrm{QCABDABDAB}$ khi so sánh $T[3,\ldots, 12]$ với $P$, nhận thấy $T_{\mathrm{sub}} = \{AB\} = T[11,12]$, theo $(1)$, ta có thể dịch $3$ hoặc $6$ đơn vị để khớp với $T_{\mathrm{sub}}$. Tuy nhiên, theo $(2)$, ta dịch sẽ dịch $6$ đơn vị.

Xét một ví dụ khác, $T[1,2,\ldots,n] = \mathrm{XUXTUYZXKXCTXKXUY}$ và $P[1,2,\ldots,9] = \mathrm{XKXKXTZXK}$, khi so sánh $T[1,2,\ldots,9]$ với $P$, nhận thấy $T_{\mathrm{sub}} = \{ZXK\} = T[7,8,9]$. $\overline{T_{\mathrm{sub}}}$ không tồn tại trong trường hợp này, theo $(3)$ ta dịch $P$ ít nhất $6$ đơn vị và theo $(4)$, ta sẽ dịch $7$ đơn vị.

Trường hợp muốn tìm tất cả sự xuất hiện của $P$ trong $T$ khá dễ hiểu và có lẽ không cần thêm ví dụ.

Trước hết ta chứng minh luật hậu tố tốt không bỏ sót bất kì kí tự nào.

 
Chứng minh: Giả sử $P[m]$ thẳng hàng với $T[k]$ trước khi luật hậu tố tốt dịch $P$ sang vị trí mới để $P[m]$ thẳng hàng với $T[k']$. Giả sử tồn tại $\ell$ sao cho:

1. $k < \ell < k'$
2. $P[m,m-1,\ldots, 1]$ khớp với $T[\ell, \ell-1,\ldots]$ theo thứ tự đó.

Nếu $\ell$ tồn tại, sẽ tồn tại $\overline{T_{\mathrm{sub}}}$ là xâu con của $P$ gần $T_{\mathrm{sub}}$ hơn $\overline{T_{\mathrm{sub}}}$ hiện tại khi $P[m]$ thẳng hàng với $T[k']$ hoặc tồn tại một tiền tố dài hơn của $P$ khớp với hậu tố của $T_{\mathrm{sub}}$. Do đó, luật hậu tố tốt sẽ dịch $P$ sao cho $P[m]$ thẳng hàng với $T[\ell]$ thay vì $T[k']$.

Thực thi luật hậu tố tốt

Trước hết để ý luật hậu tố tốt phát biểu chỉ phụ thuộc vào $P$, do đó ta có thể áp dụng tiền xử lí để thực thi luật này (có gì đó hơi giống KMP). Nhận xét thấy $T_{\mathrm{sub}}$ luôn là một hậu tố của $P$. Trước hết ta thực thi $(1)$ và $(2)$ trong luật hậu tố tốt. Gọi $L[i]$ là vị trí lớn nhất nhỏ hơn $m$ sao cho xâu $P[i,i+1,\ldots,m]$ khớp với hậu tố của $P[1,2,\ldots, L[i]]$ và $LL[i]$ là vị trí lớn nhất nhỏ hơn $m$ sao cho xâu $P[i,i+1,\ldots,m]$ khớp với hậu tố của $P[1,2,\ldots, L[i]]$ và kí tự liền kề bên trái của hậu tố khớp trong $P[1,2,\ldots, L[i]]$ khác $P[i-1]$.

Ví dụ: $P[1,2,\ldots, 10] = \mathrm{QCABDABDAB}$, $L[8] = 7, LL[8] = 4$

Nếu ta đã tính được $L[i]$ và $LL[i]$ với mọi $1\leq i \leq m-1$, theo trường hợp (1) và (2) của luật hậu tố tốt, ta sẽ dịch $P$ một đoạn là $m - LL[j]$ ($j$ là vị trí ngay trước vị trí xảy ra không khớp).

Ta sẽ tìm cách tính $L[1,2,\ldots,m-1]$ và $LL[1,2,\ldots,m-1]$ trong thời gian $O(m)$. Với mỗi $1\leq i \leq m-1$, gọi $\bar{Z}[i]$ là chiều dài của hậu tố dài nhất của $P[1,2,\ldots,i]$ khớp với hậu tố của $P[1,2,\ldots,m]$. Nhắc lại: với một xâu $S$, hàm Z của $S$ có $Z_S[i]$ là chiều dài của xâu con dài nhất của $S$ bắt đầu từ $i$ và khớp với một tiền tố của $S$. Do đó gọi $P^{\mathrm{rev}}$ là xâu đảo ngược của $P$, ta có thể tính được $\bar{Z}[1,2,\ldots,m-1]$ thông qua Z $Z^{\mathrm{rev}}[1,2,\ldots,m-1]$ của $P^{\mathrm{rev}}$ như sau:

$Z[i] = Z^{\mathrm{rev}}[1,2,\ldots,m-i-1] \qquad (3)$

Ta có quan hệ sau giữa $L[1,2,\ldots,m-1], LL[1,2,\ldots,m-1]$ và $\bar{Z}[1,2,\ldots,m-1]$ như sau:

Lemma 2 có thể được chứng minh trực tiếp từ định nghĩa của $\bar{Z}, L, LL$ và coi như bài tập cho bạn đọc. Ta có thuật toán sau tính $LL[1,2,\ldots,m]$:

 
Code của giả mã bằng C:

void computeLL(int m, int *LL, int *Zbar){
int i = 0, j = 0;
char Prev[m+1]; // the reverse of P[1,2,....,m]
int Zrev[m+1]; // the Z function of Prev[1,2,...,m]
for(i = m; i >= 1; i--){
Prev[m-i+1] = P[i];
}
//See http://www.giaithuatlaptrinh.com/?p=250 for details of Z function
compute_Z_function(Prev, Zrev, m);
for(i = 1; i<= m-1; i++){
Zbar[i] = Zrev[m-i+1];
}
for(j = 1; j <= m-1; j++){
i = m - Zbar[j]+1;
LL[i] = j;
}
}

Bây giờ chúng ta chỉ cần phải thực hiện $(3)$ và $(4)$ trong luật hậu tố tốt và luật dịch khi ta muốn tìm tất cả các vị trí xuất hiện của $P[1,2,\ldots,m]$ trong $T[1,2,\ldots,n]$. Gọi $SL[i]$ là chiều dài của hậu tố dài nhất (có thể có ) của $P[i,\ldots,m]$ khớp với một tiền tố của $P[1,2,\ldots,m]$. Nếu không tồn tại hậu tố như vậy, $SL[i] = 0$.
Dựa vào định nghĩa của $\bar{Z}[1,2,\ldots,m]$, ta có $SL[m-i+1]$ là số $j$ lớn nhất sao cho $\bar{Z}[j] = j$. Ta có giả mã tính $SL[1,2,\ldots,m]$ trong thời gian $O(m)$ như sau:

 
Code của giả mã bằng C:

void computeSL(int m, int *SL, int *Zbar){
int i = 1,j = 0;
for(i = 1; i  <= m-1; i++){
if(Zbar[i] == i){
SL[m-i+1] = i;
j = i;
} else {
SL[m-i+1] = j;
}
}
}

Tổng kết lại, gọi $j$ là kí tự khớp cuối cùng khi so sánh $P$ với một xâu con của $T$ ($P[j] = T_{\mathrm{sub}}[1]$). Ta sẽ dịch $P$ một lượng $x$ bằng:

$x = \begin{cases} m - LL[j], & \mbox{if } LL[j] > 0 \\ m - SL[j], & \mbox{otherwise }\end{cases} \qquad (6)$

Giả mã của thuật toán Boyer-Moore đầy đủ với luật kí tự tồi và luật hậu tố tốt:

Code của giả mã bằng C:

int fastfastBMmatcher(int n, int m){
int  R[28];
/*
* Zbar[i] is the lenght of the longest suffix of P[1,2,...,i]
* matched with a suffix of P[1,2,..,m]
*/

int Zbar[MAXM];
/*
* LL[i] is the maximum index smaller than m such that P[i,i+1,..,m]
* matched with a suffix of P[1,2,..,LL[i]] such that the char to the left of
* of the matched substring of  P[1,2,..,LL[i]] is not equal from P[i-1]
*/
int LL[MAXM];
/*
* SL[i] is the length of the longest suffix of P[i,i+1,..,m] that is matched with
* a prefix of P[1,2,...,m]
*/
int SL[MAXM];
badCharBackup(m,R);
int i = 1, j = 0, p = 0, skip = 0;
memset(Zbar, 0, sizeof(Zbar)); // set everything to 0
memset(LL,0,sizeof(LL));// set everything to 0
memset(SL,0, sizeof(SL));// set everything to 0
computeLL(m, LL, Zbar);
computeSL(m, SL, Zbar);
while(i <= n-m+1){
skip = 0;
j = m;
while(j >= 1 && skip == 0){
if(T[i+j-1] != P[j]){
p = T[i+j-1]-96;
skip = max(1, j - R[p]); // skip by the bad character rule;
if(j!=m){
if(LL[j+1] !=0){
skip = max(skip, m - LL[j+1]);// (1) and (2) of the good suffix rule
} else {
skip = max(skip, m - SL[j+1]);// (3) and (4) of the good suffix rule

}
}
}
j--;
}
if(skip == 0) return i;
i = i + skip;
}
return -1;
}

Remarks from [2]

Nếu mẫu $P$ không xuất hiện trong văn bản $T$, Knuth, Morris and Pratt [4] chứng minh rằng thời gian tìm kiếm của thuật toán Boyer-Moore với luật kí tự tồi và hậu tố tốt là $O(m+n)$. Phiên bản đầu tiên của thuật toán Boyer-Moore [1] tìm tất cả sự xuất hiện của $P$ trong $T$ có thời gian trong trường hợp tồi nhất là $O(mn)$. Galil [5] sửa đổi thuật toán Boyer-Moore tìm tất cả sự xuất hiện của $P$ trong thời gian $O(m+n)$. Ở giả mã trên mình chỉ tìm một sự xuất hiện của $P$. Code tìm sự tất cả sự xuất hiện của $P$ được đính kèm ở dưới (mình sử dụng code này cho bài toán xâu con trên spoj). Trong trường hợp chỉ sử dụng luật kí tự tồi với văn bản đầu vào là các kí tự được sinh ngẫu nhiên, thời gian của thuật toán Boyer-Moore là $o(n+m)$ (sub-linear). Trong thực tế, thuật toán Boyer-Moore cũng có thời gian sub-linear, do đó, thuật toán này được ưu tiên sử dụng hơn các thuật toán khác.

Code: BM-all-in-one, BM-accepted-code.

Tham khảo

[1] Boyer, Robert S., and J. Strother Moore. A fast string searching algorithm. Communications of the ACM 20.10 (1977): 762-772.
[2] Gusfield, Dan. Algorithms on strings, trees and sequences: computer science and computational biology, Chapter 2. Cambridge university press, 1997.
[3] Sedgewick, R., Wayne, K. (2011). Algorithms, 4th Edition, Chapter 5. Addison-Wesley. ISBN: 978-0-321-57351-3
[4] 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.
[5] Galil, Zvi. On improving the worst case running time of the Boyer-Moore string matching algorithm. Automata, Languages and Programming. Springer Berlin Heidelberg, 1978. 241-250.