Thuật toán Knuth–Morris–Pratt

Thuật toán được Donald Knuth, Vaughan Pratt và James H. Morris nghiên cứu độc lập năm 1977, nhưng họ công bố nó cùng nhau.

==Thuật toán KMP==
===Ví dụ cho thuật toán tìm kiếm ===
Để minh họa chi tiết thuật toán, chúng ta sẽ tìm hiểu từng quá trình thực hiện của thuật toán. Ở mỗi thời điểm, thuật toán luôn được xác định bằng hai biến kiểu nguyên, codice_4 và codice_5, được định nghĩa lần lượt là vị trí tương ứng trên codice_2 bắt đầu cho một phép so sánh với codice_1, và "chỉ số" trên codice_1 xác định ký tự đang được so sánh. Khi bắt đầu, thuật toán được xác định như sau:

Chúng ta tiến hành so sánh các ký tự của codice_1 tương ứng với các ký tự của codice_2, di chuyển lần lượt sang các chữ cái tiếp theo nếu chúng giống nhau. 
codice_11 và codice_12 đều là 'A'. Ta tăng i:

codice_13 và codice_14 đều là 'B'. Ta tiếp tục tăng i:

codice_15 và codice_16 đều là 'C'. Ta tăng i lên 3:

Nhưng, trong bước thứ tư, ta thấy codice_17 là một khoảng trống trong khi codice_18, không phù hợp. Thay vì tiếp tục so sánh lại ở vị trí codice_13, ta nhận thấy rằng không có ký tự codice_20 xuất hiện trong khoảng từ vị trí 0 đến vị trí 3 trên xâu codice_2 ngoài trừ vị trí 0; do đó, nhờ vào quá trình so sánh các ký tự trước đó, chúng ta thấy rằng không có khả năng tìm thấy xâu dù có so sánh lại. Vì vậy, chúng ta di chuyển đến ký tự tiếp theo, gán codice_22 và codice_23.

Tiếp tục quá trình so sánh như trên, ta xác định được xâu chung codice_24, với codice_25 (codice_26), ta lại thấy không phù hợp. Nhưng từ kết quả của quá trình so sánh trước, ta đã duyệt qua codice_27, có khả năng sẽ là khởi đầu cho một đoạn xâu khớp, vì vậy ta bắt đầu so sanh từ vị trí này. Như chúng ta đã thấy các ký tự này đã trùng khớp với nhau ký tự trong phép so khớp trước, chúng ta không cần kiểm tra lại chúng một lần nữa; ta bắt đầu với codice_28, codice_29 và tiếp tục quá trình so khớp.

Quá trình so khớp ngay lập tức thất bại, nhưng trong codice_1 không xuất hiện ký tự codice_31,vì vậy, ta tăng codice_4 lên 11, và gán codice_23.

Một lần nữa, hai xâu trùng khớp đoạn ký tự codice_24 nhưng ở ký tự tiếp theo, codice_35, không trùng với codice_36 trong codice_1. Giống như trước, ta gán codice_38, và gán codice_29, và tiếp tục so sánh.

Lần này, chúng ta đã tìm được khớp tương ứng với vị trí bắt đầu là codice_40.

===Thuật toán và mã giả của thuật toán tìm kiếm ===
Bây giờ, chúng ta tìm hiểu về sự tồn tại của bảng "so khớp một phần"(partial match) codice_41, được mô tả bên dưới, giúp ta xác định được vị trí tiếp theo để so khớp khi phép so khớp trước đã thất bại. Mảng codice_41 được tổ chức để nếu chúng ta có một phép so khớp bắt đầu từ codice_43 thất bại khi so sánh codice_44 với codice_45, thì vị trí của phép so khớp tiếp theo có chỉ số là codice_46 trong codice_2 (codice_48 là đại lượng xác định số ô cần lùi khi có một phép so khớp thất bại). Mặc dù phép so khớp tiếp theo sẽ bắt đầu ở chỉ số codice_46, giống như ví dụ ở trên, chúng ta không cần so sánh các ký tự codice_48 sau nó, vì vậy chúng ta chỉ cần tiếp tục so sánh từ ký tự codice_51. Ta có codice_52, cho thấy rằng nếu codice_12 không khớp, ta không phải lùi lại mà tiếp tục phép so sánh mới ở ký tự tiếp theo. Sau đây là đoạn mã giả mẫu của thuật toán tìm kiếm KMP.

===Độ phức tạp của thuật toán tìm kiếm ===
Với sự xuất hiện của mảng codice_41, phần tìm kiếm của thuật toán Knuth–Morris–Pratt có độ phức tạp codice_55, trong đó codice_56 là độ dài của xâu codice_2. Ngoại trừ các thủ tục nhập xuất hàm ban đầu, tất cả các phép toán đều được thực hiện trong vòng lặp codice_58, chúng ta sẽ tính số câu lệnh được thực hiện trong vòng lặp; để làm được việc này ta cần phải tìm hiểu về bản chất của mảng codice_41. Theo định nghĩa, mảng được tạo để: nếu một phép so khớp bắt đầu ở vị trí codice_43 thất bại khi so sánh codice_44 với codice_45, thì phép so khớp có thể thành công tiếp theo sẽ bắt đầu ở vị trí codice_63. Cụ thể hơn, phép so khớp tiếp theo sẽ bắt đầu tại vị trí có chỉ số cao hơn codice_4, vì vậy codice_65.

Từ điều này, chúng ta thấy rằng vòng lặp có thể thực hiện codice_66 lần. Với mỗi lần lặp, nó thực hiện một trong hai nhánh của vòng lặp. Nhánh thứ nhất tăng codice_5 và không thay đổi codice_4, vì vậy chỉ số codice_69 của ký tự đang so sánh trên codice_2 tăng lên. Nhánh thứ hai cộng thêm codice_71 vào codice_4, và như chúng ta đã biết, đây luôn là số dương. Vì vậy, vị trí codice_4, vị trí bắt đầu của một phép so khớp tiềm năng tăng lên. Vòng lặp dừng nếu codice_74; vì vậy mỗi nhánh của vòng lặp có thể được sử dụng trong tối đa codice_56 lần, do chúng lần lượt tăng giá trị của codice_69 hoặc codice_4, và codice_78: nếu codice_79, thì codice_80, vì vậy: do các phép toán chủ yếu tăng theo đơn vị, chúng ta đã có codice_74 vào một thời điểm nào đó trước, và vì vậy thuật toán dừng.

Do đó vòng lặp chủ yếu thực hiện codice_66 lần, độ phức tạp tính toán của thuật toán tìm kiếm chỉ là codice_55.

==Bảng so sánh một phần ("Partial match")==
Mục đích của bảng là cho phép thuật toán so sánh mỗi ký tự của codice_2 không quá một lần. Sự quan sát chìa khóa về bản chất của phương pháp tìm kiếm tuyến tính cho phép điều này xảy ra là trong quá trình so sánh các đoạn của chuỗi chính với đoạn mở đầu của mẫu, chúng ta biết chính xác được những vị trí mà đoạn mẫu có thể xuất hiện trước vị trí hiện tại. Nói cách khác, chúng ta "tự tìm kiếm" đoạn mẫu trước và đưa ra một danh sách các vị trí trước đó mà bỏ qua tới các ký tự vô vọng mà vẫn không mất đi các đoạn tiềm năng.

Chúng ta muốn tìm kiếm, với mỗi vị trí trên codice_1, độ dài của đoạn dài nhất giống với "đoạn bắt đầu" trên codice_1 tính đến (không bao gồm) vị trí đó, đây là khoảng cách chúng ta có thể lùi lại để tiếp tục so khớp. Do vậy codice_48 là giá trị của độ dài đoạn dài nhất kết thúc bởi phần tử codice_88. Chúng ta sử dụng quy ước rằng một chuỗi rỗng có độ dài là 0. Với trường hợp không trùng với mẫu ngay ở giá trị đầu tiên (không có khả năng lùi lại), ta gán codice_52.

===Ví dụ cho thuật toán xây dựng bảng===
Ta xét xâu codice_90. Ta sẽ thấy thuật toán xây dựng bảng có nhiều nét tương đồng với thuật toán tìm kiếm chính. Ta gán codice_52. Để tính codice_92, ta cần tìm ra một xâu con codice_93 đồng thời cũng là xâu con bắt đầu của codice_1. Vì vậy ta gán codice_95. Tương tự, codice_96 và codice_97.

Ta xét đến ký tự codice_98, codice_20. Dễ thấy ký tự này trùng với ký tự bắt đầu xâu codice_12. Nhưng do codice_48 là độ dài xâu dài nhất trùng với xâu con bắt đầu trong codice_1 tính đến codice_103 nên codice_104 và codice_105. Tương tự, ký tự codice_106 trùng với ký tự codice_14 nên codice_108.

Vì vậy ta có bảng sau:

Một ví dụ khác phức tạp hơn
===Mã giả của thuật toán tạo bảng ===
Ví dụ ở trên đã mô tả kỹ thuật tổng quát để tạo bảng.

Dưới đây là đoạn mã giả

===Độ phức tạp của thuật toán tạo bảng ===
Độ phức tạp của thuật toán tạo bảng là codice_109, với codice_110 là độ dài của codice_1. Ngoại trừ một số sắp xếp ban đầu, toàn bộ công việc được thực hiện trong vòng lặp codice_58, độ phức tạp của toàn bộ vòng lặp là codice_109, với việc cùng lúc xử lý giá trị của codice_114 và codice_115. Trong trường hợp thứ nhất, codice_115 không thay đổi, khi cả codice_114 và codice_118 cùng tăng lên một đơn vị. Ở trường hợp hai, codice_118 được thay thế bởi codice_120, như chúng ta đã biết ở trên, luôn luôn nhỏ hơn codice_118, do đó tăng giá trị của codice_115. Trong trường hợp thứ ba, codice_114 tăng và codice_118 thì không, nên cả giá trị của codice_114 và codice_115 đều tăng. Mà codice_127, điều này có nghĩa là ở mỗi bước hoặc codice_114 hoặc chặn dưới codice_114 đều tăng; mà thuật toán kết thúc khi codice_130, nên nó phải kết thúc tối đa sau codice_131 vòng lặp, do codice_115 bắt đầu với giá trị codice_133. Vì vậy độ phức tạp của thuật toán xây dựng bảng là codice_109.

==Độ phức tạp của thuật toán KMP==
 Độ phức tạp của thuật toán là O(n)
Như đã thấy trong ví dụ ở trên, thuật toán mạnh hơn các thuật toán so khớp chuỗi kém hơn vì nó có thể bỏ qua các ký tự đã duyệt. Ít ô phải quay trở lại hơn, thuật toán sẽ nhanh hơn, và được thể hiện trong bảng codice_41 bởi sự hiện diện của các số không. Một từ như codice_136 sẽ làm tốt với thuật toán này vì nó không có sự lặp lại của những chữ bắt đầu, vì vậy mảng đơn giản chỉ toàn số không với -1 ở đầu. Ngược lại, với từ codice_137 nó hoạt động tồi tệ, bởi vì bảng sẽ là

Đây là mẫu xấu nhất cho mảng codice_41, và nó có thể dùng để so sánh với đoạn như codice_139, trong trường hợp này thuật toán sẽ cố gắng ghép tất cả các chữ codice_20 với 'B' trước khi dừng lại; kết quả là số lượng tối đa câu lệnh được sử dụng, tiến tới trên hai lần số ký tự của xâu S khi số lần lặp của codice_141 tăng. Mặc dù quá trình xây dựng bảng rất nhanh so với chữ này (nhưng vô tác dụng), quá trình này chạy có một lần với chữ codice_1, trong khi quá trình tìm kiếm chạy rất nhiều lần. Nếu với mỗi lần, từ codice_1 được dùng để tìm trên xâu như xâu codice_2, độ phức tạp tổng thể sẽ rất lớn. Bằng cách so sánh, sự kết hợp này là trường hợp tốt nhất với thuật toán so khớp chuỗi Boyer-Moore.

Lưu ý rằng trong thực tế, thuật toán KMP làm việc không tốt đối với tìm kiếm trong văn bản ngôn ngữ tự nhiên, bởi vì nó chỉ có thể bỏ qua các ký tự khi phần đầu của từ giống với một phần trong văn bản. Trong thực tế điều này chỉ đôi khi xảy ra trong các văn bản ngôn ngữ tự nhiên. Ví dụ, hãy xem xét bao nhiêu lần một xâu "text" xuất hiện trong đoạn văn này.

==Liên kết ngoài==
- An explanation of the algorithm and sample C++ code by David Eppstein
- Knuth-Morris-Pratt algorithm description and C code by Christian Charras and Thierry Lecroq
- Interactive animation for Knuth-Morris-Pratt algorithm by Mike Goodrich
- Explanation of the algorithm from scratch by FH Flensburg.