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 và sẽ đưa ra được thông tin có khớp với các vị trí sau của hay không. Bởi vì xâu con chung này đồng nghĩa với một phần của đã khớp với một phần của , nên bằng việc khởi tạo trước một số thông tin với xâu , ta sẽ thu được những kết luận về (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 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 một lần duy nhất.
Cùng với quá trình tiền xử lí tuyến tính (với là độ dài xâu ), 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 trong xâu ( xuất hiện 7 lần).
Ta có thể duyệt bình thường với độ phức tạp 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ý và để ý:
Vậy tiền tố độ dài 2 của () khớp với xâu con độ dài 2 ở vị trí thứ 2 của () - nói cách khác, tự khớp một phần.
Sau khi kiểm tra khớp ở vị trí số 1 (so sánh với ), ta đã biết:
Khi ta kiểm tra khớp ở vị trí số 2 (so sánh với ), ta có:
Suy ra:
Do vậy, việc so sánh với , là không cần thiết nữa. Ta chỉ cần kiểm tra nốt là đã kết luận được được tìm thấy ở vị trí 2 trong . Như vậy, sau đáp án ở vị trí , ta chỉ cần thêm thao tác để kết luận cũng có ở vị trí trong , thay vì 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 với , 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 phép tính cho mỗi lần so sánh với một xâu con của , kĩ thuật của chúng ta chỉ cần phép tính ở lần lặp đầu và cho mỗi kết quả sau, và không xét lại các kí tự của . (Đâ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 khác , vậy không khớp với ở vị trí . Đến bước này thuật duyệt sẽ tiếp tục bằng cách so với và với , không khớp; rồi lại so với , 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 ở các vị trí và của đã không còn. Lí do là vì, như đã trình bày ở ví dụ 1:
Do đó .
Tương tự như vậy, do:
Nên , ta không cần tìm ở vị trí thứ của làm gì. Sẽ hợp lí hơn khi bắt đầu tiếp ở vị trí số (do ta không thể chắc chắn có thể tìm được hay không ).
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ố và , và bắt đầu lại ở vị trí số (ở đây 2 xâu khớp nhau). Lần nữa, hãy chú ý các kí tự của đượ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 của khớp với chính xâu con độ dài bắt đầu ở vị trí số của nó. Bây giờ lần lượt so sánh các vị trí từ đến với đến . Ta thấy không khớp với , vậy không có kết quả ở vị trí số .
Ở đây hãy chú ý:
Nên ta có và . Vậy không thể có trùng khớp ở vị trí số và .
Tới đây hãy nhớ lại rằng:
Ta suy ra , . Vậy ta sẽ tiếp tục kiểm tra vị trí số 4 bằng việc so sánh với . 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 , tránh được việc xét lại và .
Gọi là tiền tố độ dài của xâu .
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í của , tìm hậu tố chuẩn dài nhất của mà cũng là tiền tố của . (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à . Ta cũng có thể định nghĩa là số lớn nhất để . Ký hiệu nghĩa là là hậu tố của .
Bảng , 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ứ .ta khớp với xâu con ta kết thúc ở vị trí thứ .Tổng quát, bảng 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 đồng thời là tiền tố của bằng cách bắt đầu với , dò nó trong bảng , dùng kết quả đó dò tiếp tục và tiếp tục, đến khi kết thúc bằng .
Chứng minh:
Đầu tiên ta chứng minh chiều xuôi: nếu xuất hiện trong thì .
Giờ ta chứng minh chiều ngược: nếu , thuộc . Giả sử không xuất hiện trong dãy. Rõ ràng do và đều có trong dãy. Do luôn giảm, ta có thể tìm được một và chỉ một thuộc sao cho và . Nói cách khác, ta có thể tìm được một và chỉ một mà sau nó "có lẽ" sẽ xuất hiện (để giữ cho dãy luôn giảm). Ở phần đầu chứng minh ta đã biết . Do hậu tố độ dài của là một hậu tố của hậu tố độ dài của , hậu tố độ dài của phải khớp với hậu tố độ dài của . Nhưng hậu tố độ dài của cũng khớp với , nên khớp với hậu tố độ dài của . Vậy ta kết luận . Thế nhưng , mâu thuẫn.
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 . Với mỗi :
Dưới đây là mã giả để tính :
π[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 . Để 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à 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á . 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 .
Coi như ta đã xây dựng xong bảng . Đâ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ứ , và kí tự đầu của đã 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ừ đến khớp với từ đến , 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ừ đến .
Suy nghĩ thật kĩ lí thuyết này.
Chứng minh:
Ta kết luận rằng là một giá trị khả dĩ của khi và chỉ khi . Do maximum của là , minumum của được xác định bởi .
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í . Nếu xảy ra không trùng khớp, ta dùng bảng để 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 ; 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ố.