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

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 có nội dung trình bày về đối sánh chuỗi, thuật toán Brute-Force, thuật toán Morris-Pratt, cải tiến với Knuth-Morris-Pratt,... Mời các bạn cùng tham khảo!
Nội dung trích xuất từ 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ươngCấutrúcdữliệuvàgiảithuật ĐỐI SÁNH CHUỖI Giảng viên: Đậu Ngọc Hà Dương Nội dung trình bày2 CấutrúcdữliệuvàgiảithuậtHCMUS2010 Giới thiệu3  Đốisánhchuỗ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ấutrúcdữliệuvàgiảithuậtHCMUS2010 Giới thiệu4  Ứngdụngcủađốisánhchuỗ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ấutrúcdữliệuvàgiảithuậtHCMUS2010 Giới thiệu5  Mụctiê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). Cấutrúcd ữliệuvàgiảithuậtHCMUS2010  P và T có cùng tập hữu hạn ký tự ∑. (∑ = {0, 1}; Giới thiệu6  Đốisánhchuỗ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 => C i = 5ữliệuvàgiảithuậtHCMUS2010 ấutrúcd Giới thiệu7  Cácthuậttoántiêubiểu:  Brute Force  Karp-Rabin  Morris-Pratt  Knuth-Morris-Pratt  Boyer-Moore  … CấutrúcdữliệuvàgiảithuậtHCMUS2010 Thuật toán Brute-ForceCấutrúcdữliệuvàgiảithuậtHCMUS2010 Ý tưởng9  LầnlượtkiểmtrađiềukiệnP[0…m1]=T[i… i+m1]tạimọivịtrícóthểcủai.  Vídụ  Tìm kiếm P = aab trong T = acaabc CấutrúcdữliệuvàgiảithuậtHCMUS2010 Cài đặt10 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ấutrúcdữliệuvàgiảithuậtHCMUS2010 Đánh giá11  Trườnghợptốtnhất–khôngtìmthấy:O(n).  Trườnghợpxấunhất–khôngtìmthấy:O(n*m).  Trườnghợptrungbình:O(n+m). CấutrúcdữliệuvàgiảithuậtHCMUS2010 Đặc điểm chính12  KhôngcầnthaotáctiềnxửlýtrênP.  Luônluôndịchchuyểnmẫu(cửasổ)sangphải mộtvịtrí.  Thaotácsosánhcóthểthựchiệntheobấtkỳ chiềunào. Trườữngh ấutrúcd C ợpx liệuvàgi ấậunh ảithu ất:O((nm+1)*m). tHCMUS2010 Thuật toán Morris-PrattCấutrúcdữliệuvàgiảithuậtHCMUS2010 Đặt vấn đề14  ĐiểmhạnchếcủathuậttoánBruteForce:  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ấutrúcdữliệuvàgiảithuậtHCMUS2010 Đặt vấn đề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 CấutrúcdữliệuvàgiảithuậtHCMUS2010  Đề xuất của thuật toán16  GhinhậnlạinhữngphầncủaTđãtrùngvớiP trướcđó.  CốgắngtăngsốbướcdịchchuyểnPtrênT (thayvì01đơnvị).  CốgắngbỏquamộtsốbướcsosánhgiữaP vàTtạivịtrímới(thayvìj=0,gánjbằngmộtsố thíchhợp). CấutrúcdữliệuvàgiảithuậtHCMUS2010 Đề xuất của thuật toán17  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ấutrúcdữliệuvàgiảithuậtHCMUS2010 Đề xuất của thuật toán18  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ấutrúcdữliệuvàgiảithuậtHCMUS2010 Đề xuất của thuật toán19  Vấnđề:  Tìm giá trị j1 dựa t ...