Bài giảng Thuật toán Karp-Rabin

TRÍ TUỆ NHÂN TẠOThuật toán Karp-Rabin 
Giảng viên hướng dẫn : TS. Từ Minh Phương 
Lớp: Hệ thống thông tin 
Nhóm 3: 
Trần Thị Hạnh 
Mẫn Hồng Dương 
Dương Văn Đoàn 
Nội dung 
Giới thiệu thuật toán Karp-Rabin 
Ý tưởng thuật toán Karp-Rabin 
Giải thuật thuật toán 
Mã hóa thuật toán 
Độ phức tạp của thuật toán 
Kiểm nghiệm thuật toán 
Giới thiệu thuật toán Karp-Rabin 
Thuật toán mang tên hai nhà khoa học phát minh ra nó Michael O. Rabin (sinh năm 1931, người Đức) and Richard M. Karp (sinh năm 1931, người Mỹ), đều được giải Turing Award, giải th ưở ng uy tín nhất trong nghành khoa học máy tính và công nghệ thông tin . 
Ý tưởng thuật toán 
Hàm băm: 
hash(w[0m-1]) = h = (w[0]*2m-1 + w[1]*2m-2 + w[m-1]*20) mod q 
Việc tính lại hàm băm như sau: 
 Rehash(a,b,h)=h = ((h – a*2m-1)*2 + b)mod q 
Hàm băm tốt: 
các thao tác cơ bản được thực hiện hiệu quả 
khi băm hai xâu con khác nhau có cùng độ dài mm, xác suất hai giá trị băm giống nhau là nhỏ. 
Giải thuật thuật toán(1) 
Giải thuật thuật toán(2) 
1. function Rabin_Karp(string T[1..n], string P[1..m])2. hsub := hash(P[1..m]) // giá trị băm của xâu P3. hs := hash(T[1..m]) // giá trị băm của xâu T4. for i from 1 to n-m+15. if hs = hsub6. if T[i..i+m-1] = P7. return i8. hs := hash(T[i+1..i+m]) // giá trị băm của xâu T[i+1..i+m]9. return not found 
Mã hóa thuật toán 
Độ phức tạp thuật toán Karp-Rabin 
Độ phức tạp về thời gian trong giai đoạn tiền xử lý là O(M) 
Khi tính giá trị băm cho T[i+1..i+m] ta mất thời gian là O(m), do công việc này được thực hiện trong (n-m+1) lần. 
Độ phức tạp trong giai đoạn tìm mẫu là O(M*N) 
Kiểm nghiệm thuật toán(1) 
Kiểm nghiệm thuật toán(2) 
CẢM ƠN THẦY VÀ CÁC BẠN ĐÃ THEO DÕI !!!