Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán đối sánh chuỗi (Pattern Matching) - Nguyễn Tri Tuấn

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán đối sánh chuỗi (Pattern Matching) - Nguyễn Tri Tuấn

1. Data Structure & Algorithm Các thuật toán đối sánh chuỗi (Pattern Matching) Nguyễn Tri Tuấn Khoa CNTT – ĐH.KHTN.Tp.HCM Email: nttuan@ fit.hcmuns.edu.vn Pattern Matching Giới thiệu Các bước xử lý Các cách tiếp cận Brute-Force Knuth-Morris-Pratt Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM2 1
2. Giới thiệu ªCác thuật ngữ thường dùng: Pattern matching String matching String searching Text searching Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM3 Giới thiệu (tt) ª“Đối sánh chuỗi”làgì? Cho một chuỗi T vàmột chuỗi P, hãy xác định P có xuất hiện trong T hay không ? Tương tự như lệnh: strstr(T, P) [trong C++] m Pos(P, T) [trong Pascal] Pattern (P) n Text (T) Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM4 2
3. Giới thiệu (tt) ªĐối sánh chuỗi làmột trong những bài toán cơ bản và“tự nhiên”nhất của ngành Tin Học ªCông dụng: Chức năng search trong các trình soạn thảo văn bản vàWeb browser Các công cụ search (vd. Google) Sinh học phân tử (tìm kiếm các mẫu trong DNA / protein) Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM5 Giới thiệu (tt) ªLịch sử phát triển: Brute Force: Trong trường hợp xấu nhất thời gian thực hiện tỷ lệ với m*n Trong nhiều ứng dụng thực tế thời gian xử lý thực sự tỉ lệ với m+n Thích hợp với hầu hết các hệ máy tính Trong năm 1970, S.A.Cook đã chứng minh một kết quả lý thuyết giúp suy ra sự tồn tại của một thuật toán để giải bài toán đối sánh mẫu, cóthời gian tỷ lệ với M+N trong trường hợp xấu nhất Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM6 3
4. Giới thiệu (tt) ªLịch sử phát triển: D.E.Knuth và V.R.Pratt đã kiên trì theo đuổi kiến trúc mà Cook đã dùng để chứng minh cho cho định lý của ông vànhận được một thuật toán tương đối đơn giản. Đồng thời J.H.Morris cũng khám phára thuật toán này Knuth, Morris, Pratt đã không giới thiệu thuật toán của họ cho đến năm 1976, vàtrong thời gian này R.S.Boyer và J.S.Moore đã khám phára một thuật toán nhanh hơn nhiều Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM7 Giới thiệu (tt) ªLịch sử phát triển: Trong năm 1980, R.M.Karp và M.O.Rabin đã đi đến thuật toán đơn giản gần như thuật toán Brute Force, cóthời gian thi hành thường tỉ lệ với m+n Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM8 4
5. Giới thiệu (tt) ªCác thuật toán tiêu biểu: Brute Force Karp-Rabin Morris-Pratt Knuth-Morris-Pratt Boyer-Moore Boyer-Moore-Horspool Apostolico-Giancarlo Aho-Corasick Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM9 Các bước xử lý ªCácthuậttoán đốisánhchuỗithườngcó2 bước xử lýsau: Bướctiềnxửlý(Preprocessing Phase): Xử lýPattern Khởitạocấutrúcdữliệu Bướctìmkiếm(Searching Phase) TìmkiếmPattern trongText Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM10 5
6. Các cách tiếp cận ª Có4 cáchtiếpcậnchính để làmtăngtốcđộ thuật toán: Classical Algorithms Thuậttoánchủ yếudựavàophépso sánhgiữacáckýtự Thuậttoán: Quick Search, Brute Force Suffix Automata Algorithms Sử dụngSuffix Automaton Data Structure để nhậnratấtcảcác hậutốcủaPattern Thuậttoán: Knuth –Morris –Pratt Bit-Parallelism Algorithms Khai thác tính song song bản chất trong việc thao tác bit trên một máy tính Thuật toán: Shift-Or Hashing Algorithms Sử dụng kỹ thuật băm, tránh việc so sánh các ký tự có độ phức tạp bậc 2 Thuật toán: Karp-Rabin Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM11 Độ phức tạp ªĐộ phứctạpcủathuậttoánphụ thuộcvào3 yếu tố sau: ChiềudàicủaPattern ChiềudàicủaText Độ lớncủatậpcáckýtự: Binary, DNA, Alphabets Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM12 6
7. Pattern Matching Giới thiệu Các bước xử lý Các cách tiếp cận Brute-Force Knuth-Morris-Pratt Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM13 Brute-Force ªÝ tưởng: Đối với vị tríthứ i của văn bản T (i=0 n-m), ta so sánh các ký tự của P tương ứng từ trái sang phải: P[0] với T[i], P[1] với T[i+1], , P[m-1] với T[i+m-1] ªVídụ: T = “TWO RED ROADS CROSSING” n = length(T) = 22 P = “ROADS” m = length(P) = 5 Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM14 7
8. Brute-Force (tt) ªVídụ: Bước 1: TWO RED ROADS CROSSING ROADS Bước 2: TWO RED ROADS CROSSING ROADS Bước 5: TWO RED ROADS CROSSING ROADS Bước 9: TWO RED ROADS CROSSING ROADS Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM15 Brute-Force (tt) ªCài đặt bằng C: int stringSearchBF (char *P,char *T); Kết quả: -1 : nếu P không nằm trong T, hoặc >=0: vị trícủa P trong T Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM16 8
9. Brute-Force (tt) ªĐánh giá: Trường hợp xấu nhất O(m*n) – tự chứng minh Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM17 Brute-Force (tt) ªĐánh giá: Trường hợp tốt nhất O(n) – tự chứng minh Trường hợp trung bình O(n+m) – tự chứng minh Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM18 9
10. Pattern Matching Giới thiệu Các bước xử lý Các cách tiếp cận Brute-Force Knuth-Morris-Pratt Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM19 Đặt vấn đề ª Trong thuật toán Brute-force: khi cósựkhông so khớp tại một ký tự, ta đã xóa bỏ tất cả thông tin có được bởi các phép so sánh trước đóvàbắt đầu lại việc so sánh từ ký tự đầu tiên của mẫu P [i=i+1; j=0] ª Vídụ: T = 101010100111; P = 10100 101010100111 10100(không so khớp) 101010100111 10100(bắt đầu lại từ i=1; j=0) Dịch chuyển i và j ra sao cho cólợi ? 101010100111 ?? 10100 Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM20 10
11. Morris-Pratt ªHướng giải quyết của Morris-Pratt: Lợi dụng thông tin đã biết về các ký tự đã so sánh Trong quátrình chạy, biến j sẽ thể hiện số ký tự đã được so khớp giữa mẫu (P) và văn bản (T). Khi gặp vị tríkhông so khớp, ta không thay đổi i màgán cho j một giátrị thích hợp Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM21 Morris-Pratt (tt) ª Trạng thái không so khớp tại vị tríthứ j trên mẫu P Phần đầu của mẫu P khớp nhau v = đoạn so khớp giữa phần đầu P với phần cuối của P[0 j-1] à v là đoạn dịch chuyển của j Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM22 11
12. Morris-Pratt (tt) ªHướng giải quyết của Morris-Pratt: Xây dựng mảng NEXT[0 m-1] để lưu giữ các giátrị dịch chuyển v tương ứng với từng vị trí NEXT[j] chứa giátrị dùng để dịch chuyển con trỏ j khi xảy ra sự không khớp Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM23 Morris-Pratt (tt) ª Vídụ: T = AATAAAATA P = AAATA 0 1 2 3 4 NEXT -1 0 1 2 0 i=0 AATAAAATA j=0 AAATA i=0 AATAAAATA j=1 AAATA i=0 AATAAAATA j=2 AAATA (không so khớpà j=NEXT[j]=1) Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM24 12
13. Morris-Pratt (tt) ª Vídụ: i=1AATAAAATA j=1 AAATA (không so khớpà j=NEXT[j]=0) i=2AATAAAATA j=0 AAATA (không so khớpà j=NEXT[j]=-1) i=2AATAAAATA j=-1 AAATA i=3AATAAAATA j=0 AAATA(tiếp tục ) i=3AATAAAATA j=3 AAATA (không so khớpà j=NEXT[j]=2) Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM25 Morris-Pratt (tt) ªVídụ: i=4AATAAAATA j=2 AAATA(tiếp tục ) i=4AATAAAATA j=4 AAATA à so khớp ! Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM26 13
14. Morris-Pratt (tt) ªCách xây dựng bảng NEXT: NEXT[0] = -1 Với j>0, giátrị của NEXT[j] làsốk lớn nhất nhỏ hơn j sao cho k ký tự đầu tiên của mẫu P khớp với k ký tự cuối của P[0 j-1] Vídụ: P = AAATA NEXT[1] = 0 A A A T A (j=1) A A A T A NEXT[2] = 1 A A A T A (j=2) A A A T A Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM27 Morris-Pratt (tt) NEXT[3] = 2 A A A T A A A A T A A A A T A NEXT[4] = 0 A A A T A Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM28 14
15. Morris-Pratt (tt) // Tạo lập bảng NEXT void initNEXT(char *p, int NEXT[]) { int i, j; int m = strlen(p); i = 0; j = NEXT[0] = -1; while (i =0 : vị trícủa P trong T int stringSearchMP (char *P,char *T) { int n = strlen(T); int m = strlen(P); int *NEXT = new int[m]; initNEXT(p, NEXT); // Thực hiện đối sánh } Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM30 15
16. Morris-Pratt (tt) ªVídụ: Xây dựng bảng NEXT cho P = 10100 Xây dựng bảng NEXT cho P = ABACAB Xây dựng bảng NEXT cho P = GCAGAGAG Xây dựng bảng NEXT cho P = AABAABA Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM31 Morris-Pratt (tt) P = 10100 0 1 2 3 4 NEXT -1 0 0 1 2 P = ABACAB 0 1 2 3 4 5 NEXT -1 0 0 1 0 1 P = GCAGAGAG 0 1 2 3 4 5 6 7 NEXT -1 0 0 0 1 0 1 0 Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM32 16
17. Morris-Pratt (tt) ªĐộ phức tạp: Giai đoạn tiền xử lý: O(m) (tính NEXT) Giai đoạn tìm kiếm: O(n) Tổng: O(n+m) Số phép so sánh lớn nhất của một ký tự bị <= m Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM33 Knuth-Morris-Pratt ªKiểm tra điều kiện c ≠ b để tránh trường hợp “mis-match”ngay vị trí đầu tiên sau khi dịch chuyển j Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM34 17
18. Knuth-Morris-Pratt (tt) ªÝ tưởng thuật toán hoàn toàn giống với thuật toán Morris-Pratt Giai đoạn tìm kiếm thì tương tự Giai đoạn tiền xử lý cómột cải tiến nhỏ: Tính độ dịch chuyển tốt hơn à tránh so sánh cùng một ký tự trong T hai lần Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM35 Knuth-Morris-Pratt (tt) ª initNEXT (Morris-Pratt): NEXT[i] = j; ª initNEXT (Knuth-Morris-Pratt): if (p[i] != p[j]) NEXT[i] = j; else NEXT[i] = NEXT[j]; Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM36 18
19. Knuth-Morris-Pratt (tt) ªĐộ phức tạp: Giai đoạn tiền xử lý: O(m) (tính NEXT) Giai đoạn tìm kiếm: O(n) Tổng: O(n+m) Số phép so sánh lớn nhất của một ký tự <= logam 1+√5 với a = 2 Hiệu quả hơn so với Brute-Force trong các trường hợp mẫu cótính tự lặp cao Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM37 Thank you for your attention Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM38 19
20. QQ && AA Winter 2005Data Structure & Algorithm -Pattern Matching -Nguyen Tri Tuan, DH.KHTN Tp.HCM39 20