Nội dung

Giảng viên: Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến 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 Thuật toán Rabin-Karp Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com © FIT-HCMUS https://fb.com/tailieudientucntt 1  Đố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 2015  Ứ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 2015 CuuDuongThanCong.com © FIT-HCMUS https://fb.com/tailieudientucntt 2  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 2015  Đố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 + j] = P[j] với mọi 0 ≤ j ≤ m - 1.  T[i  Ví dụ: P = abbaba  T = ababaabbabaa => i = 5 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com © FIT-HCMUS https://fb.com/tailieudientucntt 3  Các thuật toán tiêu biểu:  Brute Force  Morris-Pratt  Knuth-Morris-Pratt  Rabin-Karp  Boyer-Moore … Cấu trúc dữ liệu và giải thuật - HCMUS 2015 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com © FIT-HCMUS https://fb.com/tailieudientucntt 4   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 2015 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 2015 CuuDuongThanCong.com © FIT-HCMUS https://fb.com/tailieudientucntt 5  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 2015     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 2015 CuuDuongThanCong.com © FIT-HCMUS https://fb.com/tailieudientucntt 6 Cấu trúc dữ liệu và giải thuật - HCMUS 2015  Đ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 2015 CuuDuongThanCong.com © FIT-HCMUS https://fb.com/tailieudientucntt 7  Ví dụ: T: 10101011101001;  P: 10100   Brute Force: i = 0, j = 4, T[i+j] != P[j] => i = 1, j = 0 T : 10101011101001  P: 10100   Cách khác? i = 0, j = 4, T[i+j] != P[j] => i = 2, j = 2   T : 10101011101001 P: 10100 Cấu trúc dữ liệu và giải thuật - HCMUS 2015    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 2015 CuuDuongThanCong.com © FIT-HCMUS https://fb.com/tailieudientucntt 8  Giả sử: 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 i Cấu trúc dữ liệu và giải thuật - HCMUS 2015  Tìm:  Vị trí mới i1 (trên T) và j1 (trên P) sao cho = i1+j1 (ngay tại 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.  i+j  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 2015 CuuDuongThanCong.com © FIT-HCMUS https://fb.com/tailieudientucntt 9  Vấn đề: giá trị j1 dựa trên j.  Tìm  Cách thức:  Tính  sẵn các giá trị của j1 ứng với mỗi vị trí j (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 2015  Bảng NEXT:  Bảng  chứa các giá trị j1 ứng với các giá trị j. Ví dụ: j j1 0 -1 1 0 2 1 3 1 4 0 5 3 6 2 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 CuuDuongThanCong.com © FIT-HCMUS https://fb.com/tailieudientucntt 10