Thuật toán so khớp KMP

Thuật toán so khớp KMP

Pattern matching là một trong những bài toán cơ bản và quan trọng nhất của ngành máy tính.

Tìm patterns trong các chuỗi-DNA là bài toán cơ bản của sinh tin học. Các phần mềm quét virus hiện đại có mấy chục triệu “patterns” là các “chữ ký” (virus signature) của các con virus máy tính đã biết. Khi quét máy thì phần mềm phải tìm các patterns này trong các files hay bộ nhớ của máy. Mỗi pattern thường là một chuỗi bytes nhất định. Lệnh grep chúng ta thường dùng trong Unix cũng làm tác vụ tương tự, trong đó các patterns có thể được biểu diễn bằng các biểu thức chính quy (regular expressions).

 Nếu chỉ tính các thuật toán tìm các xuất hiện của một chuỗi đơn (một chuỗi các ký tự cho sẵn) bên trong một chuỗi khác thôi thì ta đã có đến cả trăm thuật toán khác nhau. Knuth-Morris-Pratt (KMP) là một trong những thuật toán đó. KMP không phải là thuật toán nhanh nhất hay tốn ít bộ nhớ nhất trên thực tế. Trên thực tế các biến thể của thuật toán Boyer-Moore hay Rabin-Karp với hàm băm và bộ lọc Bloom thường được dùng. Ta sẽ nói về chúng sau. Nhưng KMP thật sự rất thanh lịch và nếu tác vụ tìm kiếm không ghê gớm quá thì KMP không kém Boyer-Moore là mấy.

Ý tưởng chính của phương pháp này như sau : trong quá trình tìm kiếm vị trí của mẫu P trong xâu gốc T, nếu tìm thấy một vị trí sai ta chuyển sang vị trí tìm kiếm tiếp theo và quá trình tìm kiếm sau này sẽ được tận dụng thông tin từ quá trình tìm kiếm trước để không phải xét các trường hợp không cần thiết.

Xem Thêm Bài Viết  Tạo một ứng dụng Empty Project hoặc Win32 trên Visual C++

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, m và i, được định nghĩa lần lượt là vị trí tương ứng trên S bắt đầu cho một phép so sánh với W, và chỉ số trên W xác định kí tự đang được so sánh. Khi bắt đầu, thuật toán được xác định như sau:

m:         0
S:      ABC ABCDAB ABCDABCDABDE
W:      ABCDABD
i:      0

Chúng ta tiến hành so sánh các kí tự của W tương ứng với các kí tự của S, di chuyển lần lượt sang các chữ cái tiếp theo nếu chúng giống nhau. S[0] và W[0] đều là ‘A’. Ta tăng i:

m:         0
S:      ABC ABCDAB ABCDABCDABDE
W:      ABCDABD
i:      _1      

S[1] và W[1] đều là ‘B’. Ta tiếp tục tăng i:

m:         0
S:      ABC ABCDAB ABCDABCDABDE
W:      ABCDABD
i:      __2     

S[2] và W[2] đều là ‘C’. Ta tăng i lên 3:

m:         0
S:      ABC ABCDAB ABCDABCDABDE
W:      ABCDABD
i:      ___3    

Nhưng, trong bước thứ tư, ta thấy S[3] là một khoảng trống trong khi W[3] = 'D', không phù hợp. Thay vì tiếp tục so sánh lại ở vị trí S[1], ta nhận thấy rằng không có kí tự'A' xuất hiện trong khoảng từ vị trí 0 đến vị trí 3 trên xâu S 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 m = 4 và i = 0.

m: ____4
S:      ABC ABCDAB ABCDABCDABDE
W:          ABCDABD
i:          0   

Tiếp tục quá trình so sánh như trên, ta xác định được xâu chung "ABCDAB", với W[6] (S[10]), 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 "AB", 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 m = 8i = 2 và tiếp tục quá trình so khớp.

m: ________8
S:      ABC ABCDAB ABCDABCDABDE
W:              ABCDABD
i:              __2

Quá trình so khớp ngay lập tức thất bại, nhưng trong W không xuất hiện kí tự ‘ ‘,vì vậy, ta tăng m lên 11, và gán i = 0.

m:         ___________11
S:      ABC ABCDAB ABCDABCDABDE
W:                 ABCDABD
i:                 0

Một lần nữa, hai xâu trùng khớp đoạn kí tự "ABCDAB" nhưng ở kí tự tiếp theo, 'C', không trùng với 'D' trong W. Giống như trước, ta gán m = 15, và gán i = 2, và tiếp tục so sánh.

m:         _______________15
S:      ABC ABCDAB ABCDABCDABDE
W:                     ABCDABD
i:                     __2

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

THUẬT TOÁN VIẾT TRONG C++

Xem Thêm Bài Viết  Kế thừa lớp sinh viên Visual C++

#include <cstdio>

#include <cstring>

#include <string>
#include <iostream>
#include <conio.h>

using namespace std;
void FailureFunction(char P[], int F[],int m){
int i,j;
F[0]=0; // Nho gan cai nay
j=0;
i=1;
while(i<m){ //khi i dang nho hon do dai cua mau
if(P[i]==P[j]){
F[i]=j+1;
i++;
j++;
}else if(j>0){
j=F[j-1];
}else {
F[i]=0;
i++;
}
}
}
int KMP(char T[], char P[]){
int i,j,F[100]; // mau P khong qua 100 ky tu
int m=strlen(P);
int n=strlen(T);
FailureFunction(P,F,m);
i=0;
j=0;
while(i<n){
if(T[i]==P[j]){
if(j==m-1)
return i-j; // vi tri duoc tim thay la i-j
else{
i++;
j++;
}
}else if(j>0){
j=F[j-1];
}else{
i++;
}
}
return -1; // Tra ve -1 neu khong khop
}
int main()
{
char T[1000],P[100];
cout<<“———————— THUAT TOAN SO KHOP ————————– nn”;
cout<<“Moi nhap doan van ban (khong qua 1000 ky tu): n”;
gets(T);
cout<<“Moi nhap mau can tim kiem (khong qua 100 ky tu): n”;
gets(P);
int pos=KMP(T,P);
if(pos!=-1)
cout<<“Mau khop voi doan van tai vi tri: “<<pos<<“nn”;
else
cout<<“Mau khong khop voi doan vannn”;
cout<<“—————— CAM ON BAN DA SU DUNG CHUONG TRINH ———————- nn”;
getch();
return 0;
}

Lượt xem (2976)

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *