Nguồn: wcipeg
Người dịch: Trần Kim Thạch
Trước khi đọc bài này, bạn có thể đọc về các thuật ngữ trong xử lý xâu cũng như về bài toán so khớp chuỗi ở đây
Thuật toán Knuth-Morris-Pratt (KMP) là một thuật toán với thời gian chạy tuyến tính nhằm giải quyết bài toán so khớp chuỗi.
Thuật toán được xây dựng dựa vào quan sát rằng một xâu con chung của $S$ và $T$ sẽ đưa ra được thông tin $S$ có khớp với các vị trí sau của $T$ hay không. Bởi vì xâu con chung này đồng nghĩa với một phần của $T$ đã khớp với một phần của $S$, nên bằng việc khởi tạo trước một số thông tin với xâu $S$, ta sẽ thu được những kết luận về $T$ (nhờ xâu con chung) mà không cần quay ngược và so sánh lại những ký tự đã khớp.
Cụ thể hơn, ta muốn tính toán trước cách xâu $S$ tự khớp với chính nó. Nhờ vậy thuật toán sẽ không quay nhìn lại và chỉ duyệt qua $T$ một lần duy nhất.
Cùng với quá trình tiền xử lí tuyến tính $O(|T|)$ (với $|T|$ là độ dài xâu $T$), thuật toán có thời gian chạy tuyến tính.
Cảm hứng của KMP có thể được minh họa rõ nhất qua 3 ví dụ dưới đây.
S = aaa
T = aaaaaaaaa
Ở ví dụ này, ta cần các lần xuất hiện của xâu $S$ trong xâu $T$ ($S$ xuất hiện 7 lần).
Ta có thể duyệt bình thường với độ phức tạp $O(|S| * |T|)$ như sau:
Và cứ mãi như vậy cho đến khi đủ hết trường hợp.
Tuy nhiên ta có thể làm tốt hơn nếu ta tiền xử lý $S$ và để ý:
Vậy tiền tố độ dài 2 của $S$ ($S_1 S_2$) khớp với xâu con độ dài 2 ở vị trí thứ 2 của $S$ ($S_2 S_3$) - nói cách khác, $S$ tự khớp một phần.
Sau khi kiểm tra khớp ở vị trí số 1 (so sánh $S$ với $T_1 T_2 T_3$), ta đã biết:
Khi ta kiểm tra khớp ở vị trí số 2 (so sánh $S$ với $T_2 T_3 T_4$), ta có:
Suy ra:
Do vậy, việc so sánh với $T_2$, $T_3$ là không cần thiết nữa. Ta chỉ cần kiểm tra nốt $S_3 = T_4$ là đã kết luận được $S$ được tìm thấy ở vị trí 2 trong $T$. Như vậy, sau đáp án ở vị trí $1$, ta chỉ cần thêm $1$ thao tác để kết luận $S$ cũng có ở vị trí $2$ trong $T$, thay vì $3$ như thuật duyệt bình thường. Đến đây ta biết:
Và tương tự, lại kết luận được:
Ta sau đó chỉ cần so $S_3$ với $T_5$, tìm được một đáp án nữa, cứ thế tiếp tục. Trong khi thuật toán duyệt cần đến $3$ phép tính cho mỗi lần so sánh $S$ với một xâu con của $T$, kĩ thuật của chúng ta chỉ cần $3$ phép tính ở lần lặp đầu và $1$ cho mỗi kết quả sau, và không xét lại các kí tự của $T$. (Đây cũng là cách con người giải quyết bài toán)
S = aaa
T = aabaabaaa
Như ở trên, ta bắt đầu như thuật toán duyệt, so sánh:
Ở đây ta thấy $S_3$ khác $T_3$, vậy $S$ không khớp với $T$ ở vị trí $1$. Đến bước này thuật duyệt sẽ tiếp tục bằng cách so $S_1$ với $T_2$ và $S_2$ với $T_3$, không khớp; rồi lại so $S_1$ với $T_3$, không khớp; cứ như vậy.
Thế nhưng chúng ta sẽ thấy ngay rằng sau kết quả không khớp ở vị trí đầu, khả năng tìm thấy $S$ ở các vị trí $2$ và $3$ của $T$ đã không còn. Lí do là vì, như đã trình bày ở ví dụ 1:
Do đó $S_2 \neq T_3$.
Tương tự như vậy, do:
Nên $S_1 \neq T_3$, ta không cần tìm $S$ ở vị trí thứ $3$ của $T$ làm gì. Sẽ hợp lí hơn khi bắt đầu tiếp ở vị trí số $4$ (do ta không thể chắc chắn có thể tìm được hay không $S_2 S_3 S_4 \, = \, T_4T_5T_6$).
Sau khi so sánh ở vị trí 4 và thấy tiếp tục không khớp, ta dùng lập luận tương tự loại bỏ vị trí số $5$ và $6$, và bắt đầu lại ở vị trí số $7$ (ở đây 2 xâu khớp nhau). Lần nữa, hãy chú ý các kí tự của $T$ được duyệt qua theo trình tự.
Đây là một ví dụ phức tạp hơn:
S = tartan
T = tartaric_acid
Ta quan sát thấy tiền tố độ dài $2$ của $S$ khớp với chính xâu con độ dài $2$ bắt đầu ở vị trí số $4$ của nó. Bây giờ lần lượt so sánh các vị trí từ $S_1$ đến $S_6$ với $T_1$ đến $T_6$. Ta thấy $S_6$ không khớp với $T_6$, vậy không có kết quả ở vị trí số $1$.
Ở đây hãy chú ý:
Nên ta có $S_1 \neq T_2$ và $S_1 \neq T_3$. Vậy không thể có trùng khớp ở vị trí số $2$ và $3$.
Tới đây hãy nhớ lại rằng:
Ta suy ra $S_1 = T_4$, $S_2 = T_5$. Vậy ta sẽ tiếp tục kiểm tra vị trí số 4 bằng việc so sánh $S_3$ với $T_6$. Làm theo cách này, ta loại bỏ được hai trường hợp và bắt đầu duyệt lại không phải ở đầu mà ở giữa xâu $S$, tránh được việc xét lại $T_4$ và $T_5$.
Gọi $S^i$ là tiền tố độ dài $i$ của xâu $S$.
Các ví dụ trên chính là tư tưởng hoạt động của KMP: dựa trên quan sát rằng một số xâu con của xâu cần tìm có khớp với xâu con nào khác của xâu cần tìm hay không. Tuy nhiên định hướng chung, mang tính hệ thống của thuật toán thì chưa rõ ràng. Định hướng này được phát biểu như sau:
Ở mỗi vị trí $i$ của $S$, tìm hậu tố chuẩn dài nhất của $S^i$ mà cũng là tiền tố của $S$. (Hậu tố chuẩn của một xâu là hậu tố có độ dài bé hơn xâu đó.)
Ta sẽ gọi độ dài của xâu con này là $\pi_i$. Ta cũng có thể định nghĩa $\pi_i$ là số $j$ lớn nhất để $S^j \sqsupset S^i$. Ký hiệu $X \sqsupset Y$ nghĩa là $X$ là hậu tố của $Y$.
Bảng $\pi$, gọi là hàm tiền tố, chiếm bộ nhớ tuyến tính, và như sẽ trình bày dưới đây, có thể tính được trong thời gian tuyến tính. Bảng sẽ chứa toàn bộ các thông tin cần thiết để máy thực hiện những phương án "thông minh nhất" cho quá trình tìm kiếm. Cụ thể hơn:
a
khớp hậu tố a
.aa
khớp hậu tố aa
.t
khớp với xâu con t
kết thúc ở vị trí thứ $4$.ta
khớp với xâu con ta
kết thúc ở vị trí thứ $5$.Tổng quát, bảng $\pi$ cho ta biết, sau một lần khớp hoặc không khớp giữa "cây kim" và "đống rơm", vị trí tiếp theo trong "đống rơm" ta cần kiểm tra là gì. Các phép so sẽ tiếp tục ở các vị trí tiếp theo, không bao giờ quay ngược về các kí tự ta đã kiểm tra rồi.
Để tính độ phức tạp cho hàm tiền xử lí, trước tiên ta có quan sát:
Vậy, ta có thể đếm toàn bộ những hậu tố của $S^i$ đồng thời là tiền tố của $S$ bằng cách bắt đầu với $i$, dò nó trong bảng $\pi$, dùng kết quả đó dò tiếp tục và tiếp tục, đến khi kết thúc bằng $0$.
Chứng minh:
Cũng chính nhờ việc chứng minh này, ta có thể xây dựng một thuật toán để tính bảng $\pi$. Với mỗi $i$:
Dưới đây là mã giả để tính $\pi$:
π[1] ← 0
for i ∈ [2..m]
k ← π[i-1]
while k > 0 and S[k+1] ≠ S[i]
k ← π[k]
if S[k+1] = S[i]
π[i] ← k+1
else
π[i] ← 0
Hoặc có thể viết gọn lại như sau:
π[1] ← 0
k ← 0
for i ∈ [2..m]
while k > 0 and S[k+1] ≠ S[i]
k ← π[k]
if S[k+1] = S[i]
k ← k+1
π[i] ← k
Thuật toán có độ phức tạp $O(m)$. Để hiểu tại sao thì hãy để ý, k
không bao giờ âm; nó không thể giảm nhiều hơn mức nó tăng. k
chỉ tăng ở dòng k ← k+1
, vốn chỉ bị gọi nhiều nhất là $m-1$ lần. Vậy k
giảm nhiều nhất là k lần. Nhưng k
giảm ở mỗi lần lặp của vòng while
, vậy tổng tất cả các bước trong vòng while
không quá $O(m)$. Tất cả những câu lệnh trong vòng for
đều có độ phức tạp là hằng số, nên cả thuật toán có độ phức tạp $O(m)$.
Coi như ta đã xây dựng xong bảng $\pi$. Đây là lúc ta sử dụng những thông tin cực khổ lấy được này. Giả sử rằng ta đã kiểm tra đang vị trí thứ $j$, và $k$ kí tự đầu của $S$ đã khớp. Nói cách khác:
Có 2 khả năng:
Lí do cho trường hợp 2 là:
Nếu ta đã biết từ $S_1$ đến $S_k$ khớp với từ $T_j$ đến $T_{j+k-1}$, vị trí nào ta có thể bỏ qua? Đây là cốt lõi của thuật toán KMP:
Nói một cách dễ hình dung hơn, ta có thể bỏ qua tất cả các vị trí từ $0$ đến $p-1$.
Suy nghĩ thật kĩ lí thuyết này.
Chứng minh:
Ta kết luận rằng $k-q$ là một giá trị khả dĩ của $p$ khi và chỉ khi $S^q \sqsupset S^k$. Do maximum của $q$ là $\pi_k$, minumum của $p$ được xác định bởi $k-\pi_k$.
Dưới đây là mã giả:
j ← 1
k ← 0
while j+m-1 ≤ n
while k ≤ m and S[k+1] = T[j+k]
k ← k+1
if k = m
print "Match at position " j
if k = 0
j ← j+1
else
j ← j+k-π[k]
k ← π[k]
Ta dò trong xâu cần search một lần một kí tự; kí tự đang được xét là nằm ở vị trí $j+k$. Nếu xảy ra không trùng khớp, ta dùng bảng $\pi$ để tìm đến vị trí khả dĩ tiếp theo.
Đoạn code tương đương dưới đây thể hiện rõ hơn việc thuật toán xét một kí tự một lần và không quay ngược lại:
k ← 0
for i ∈ [1..n]
while k > 0 and S[k+1] ≠ T[i]
k ← π[k]
if S[k+1] = T[i]
k ← k+1
if k = m
print "Match at position " i-m+1
k ← π[k]
Ở đây, i
tương ứng với j+k
ở đoạn code trên. Mỗi lần lặp của vòng lặp trong của một trong 2 đoạn code tương ứng với một lần lặp của vòng lặp ngoài ở đoạn còn lại. Ở đoạn thứ hai, ta cũng có thể chứng minh thuật có độ phức tạp $O(n)$; mỗi lần vòng while
ở trong được thực hiện, giá trị của k
giảm, nhưng nó không thể giảm nhiều hơn n
lần bởi k
khởi đầu là không và không bao giờ âm. k
chỉ tăng nhiều nhất một lần ở vòng lặp ngoài (tức nhiều nhất tổng cộng n
lần). Vậy vòng lặp trong chỉ lặp nhiều nhất n
lần, và tất cả các câu lệnh khác có độ phức tạp hằng số.