›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Đối sánh chuỗi - Đậu Ngọc Hà Dương

pptx 41 trang Gia Huy 16/05/2022 4370
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Đối sánh chuỗi - Đậu Ngọc Hà Dương", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptxbai_giang_cau_truc_du_lieu_va_giai_thuat_doi_sanh_chuoi_dau.pptx

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Đối sánh chuỗi - Đậu Ngọc Hà Dương

  1. Giảng viên: Đậu Ngọc Hà Dương
  2. 2 Giới thiệu Thuật toán Brute-Force Thuật toán Morris-Pratt Cải tiến với Knuth-Morris-Pratt Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  3. 3  Đối sánh chuỗi  Từ khóa: String matching, String searching, Pattern searching, Text Searching  Một trong những thuật toán quan trọng và có ứng dụng rộng rãi. Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  4. 4  Ứng dụng của đối sánh chuỗi:  Máy tìm kiếm  Trình soạn thảo văn bản  Trình duyệt web  Sinh học phân tử (Tìm mẫu trong dãy DNA).  Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  5. 5  Mục tiêu:  Kiểm tra sự tồn tại của một chuỗi ký tự (mẫu, pattern) trong một chuỗi ký tự có kích thước lớn hơn nhiều (văn bản, text).  Nếu tồn tại, trả về một (hoặc nhiều) vị trí xuất hiện.  Quy ước:  Mẫu cần tìm: P (chiều dài m).  Văn bản: T (chiều dài n).  P và T có cùng tập hữu hạn ký tự ∑. (∑ = {0, 1}; ∑={A, ,Z}, )  m ≤ n Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  6. 6  Đối sánh chuỗi:  Bằng cách lần lượt dịch chuyển (cửa sổ) P trên T.  P tồn tại trên T tại vị trí bắt đầu là i (0 ≤ i ≤ n – m) nếu ◼ T[i + j] = P[j] với mọi 0 ≤ j ≤ m - 1.  Ví dụ:  P = abbaba  T = ababaabbabaa => i = 5 Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  7. 7  Các thuật toán tiêu biểu:  Brute Force  Karp-Rabin  Morris-Pratt  Knuth-Morris-Pratt  Boyer-Moore  Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  8. Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  9. 9  Lần lượt kiểm tra điều kiện P[0 m-1] = T[i i+m-1] tại mọi vị trí có thể của i.  Ví dụ  Tìm kiếm P = aab trong T = acaabc Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  10. 10 bruteForceMatcher(T, P) n ← length[T] m ← length[P] for i ← 0 to n - m if P[0 m-1] = T[i i+m-1] return i Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  11. 11  Trường hợp tốt nhất – không tìm thấy: O(n).  Trường hợp xấu nhất – không tìm thấy: O(n*m).  Trường hợp trung bình: O(n+m). Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  12. 12  Không cần thao tác tiền xử lý trên P.  Luôn luôn dịch chuyển mẫu (cửa sổ) sang phải một vị trí.  Thao tác so sánh có thể thực hiện theo bất kỳ chiều nào.  Trường hợp xấu nhất: O((n-m+1)*m). Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  13. Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  14. 14  Điểm hạn chế của thuật toán Brute-Force:  Không ghi nhớ được thông tin đã trùng khớp (trước) khi xảy ra tình trạng không so khớp.  Phải so sánh lại từ đầu (trên P) trong tất cả trường hợp Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  15. 15  Ví dụ:  T: 10101011101001;  P: 10100  Brute Force: s = 0, j = 4, T[s+j] != P[j] => s = 1, j = 0 ◼ T : 10101011101001 ◼ P: 10100  Cách khác? s = 0, j = 4, T[s+j] != P[j] => s = 2, j = 2 ◼ T : 10101011101001 ◼ P: 10100 Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  16. 16  Ghi nhận lại những phần của T đã trùng với P trước đó.  Cố gắng tăng số bước dịch chuyển P trên T (thay vì 01 đơn vị).  Cố gắng bỏ qua một số bước so sánh giữa P và T tại vị trí mới (thay vì j=0, gán j bằng một số thích hợp). Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  17. 17  Giả sử:  i là vị trí bắt đầu sự đối sánh (trên T).  j là vị trí đang so sánh (trên P). (Ký tự tương ứng trên T tại vị trí i+j).  T[i+j] != P[j] => không so khớp Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  18. 18  Tìm:  Vị trí mới i1 (trên T) và j1 (trên P) sao cho ◼ i+j = i1+j1 (vị trí đang xem xét) ◼ v =T[i1 i1+j1–1] là đoạn so khớp mới giữa P và T.  Khi đó:  Đoạn dịch chuyển cửa sổ: j – j1.(do j1 < j)  Có thể tìm i1 dựa trên j1. Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  19. 19  Vấn đề:  Tìm giá trị j1 dựa trên j.  Cách thức:  Tính sẵn các giá trị của j1 ứng với mỗi giá trị j (dựa trên P).  Câu hỏi:  Có thể làm được không? Tại sao? Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  20. 20  Bảng NEXT:  Bảng chứa các giá trị j1 ứng với các giá trị j.  Ví dụ: j 0 1 2 3 4 5 6 j1 -1 0 1 1 0 3 2 Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  21. 21  Hoàn toàn dựa trên P.  Cách thức:  NEXT[0] = -1  Với mỗi j > 0, giá trị của NEXT[j] (j1) là số k lớn nhất (k < j) sao cho: ◼ k ký tự đầu tiên khớp với k ký tự cuối trước vị trí j. ◼ Nghĩa là P[0 k-1] = P[j-k j-1] Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  22. 22  Ví dụ:  P = AAATA  Bảng NEXT: ◼ NEXT[0] = -1 Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  23. 23  P = AAATA  j = 1  NEXT[1] = 0 A A A T A A A A T A Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  24. 24  P = AAATA  j = 2  NEXT[2] = 1 A A A T A A A A T A Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  25. 25  P = AAATA  j = 3  NEXT[3] = 2 A A A T A A A A T A Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  26. 26  P = AAATA  j = 4  NEXT[4] = 0 A A A T A A A A T A Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  27. 27  P = AAATA  Bảng NEXT ◼ NEXT[0] = -1 ◼ NEXT[1] = 0 ◼ NEXT[2] = 1 ◼ NEXT[3] = 2 ◼ NEXT[4] = 0 0 1 2 3 4 NEXT -1 0 1 2 0 Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  28. 28  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 Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  29. 29  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 Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  30. 30  Mục tiêu :  Xác định vị trí mới i1 (trên T) và j1 (trên P) sao cho ◼ i+j = i1+j1 (vị trí đang xem xét) ◼ v =T[i1 i1+j1–1] là đoạn so khớp mới giữa P và T.  Đã có j1 = NEXT[j]  Vậy, i1 = i + j – NEXT[j] Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  31. 31  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 Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  32. 32  Ví dụ:  T = AATAAAATA  P = AAATA 0 1 2 3 4 NEXT -1 0 1 2 0  i = 0 AATAAAATA  j = 2 AAATA  i = 1 AATAAAATA (i = 0 + 2 – 1)  j = 1 AAATA (j = 1) Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  33. 33  Ví dụ:  T = AATAAAATA  P = AAATA 0 1 2 3 4 NEXT -1 0 1 2 0  i = 2 AATAAAATA (i = 1 + 1 – 0)  j = 0 AAATA (j = 0)  i = 3 AATAAAATA (i = 2 + 0 – (-1))  j = 0 AAATA (j = 0) Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  34. 34  Ví dụ:  T = AATAAAATA  P = AAATA 0 1 2 3 4 NEXT -1 0 1 2 0  i = 3 AATAAAATA  j = 3 AAATA  i = 4 AATAAAATA (i = 3 + 3 – 2)  j = 2 AAATA (j = 2) Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  35. 35  Ví dụ:  T = AATAAAATA  P = AAATA 0 1 2 3 4 NEXT -1 0 1 2 0  i = 4 AATAAAATA  j = 4 AAATA (Hoàn toàn so khớp, vị trí xuất hiện của P trong T tại i=4) Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  36. 36  Tính NEXT: O(m)  Tìm kiếm: O(n)  Tổng: O(n+m) Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  37. 37 Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  38. 38  Thuật toán Knuth-Morris-Pratt cải tiến Morris- Pratt bằng cách  bổ sung thêm điều kiện a ≠ c (vì nếu a =c sẽ không so khớp ngay sau khi dịch chuyển). Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  39. 39  Thay đổi cách tính bảng NEXT:  Nếu p[i] ≠ p[j] thì NEXT[i] = j  Ngược lại NEXT[i] = NEXT[j]  Thao tác tìm kiếm vẫn không thay đổi Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  40. 40  P = 10100 0 1 2 3 4 MP -1 0 0 1 2 KMP -1 0 -1 0 2  P = ABACAB 0 1 2 3 4 5 MP -1 0 0 1 0 1 KMP -1 0 -1 1 -1 0 Cấu trúc dữ liệu và giải thuật - HCMUS 2010
  41. Cấu trúc dữ liệu và giải thuật - HCMUS 2010