Bài giảng: Xữ lý tìm kiếm trên chuỗi kí tự

Đối tượng của bài toán string searching là tìm kiếm vị trí của một mẫu văn bản (text pattern) trong nội dung một văn bản lớn hơn (một câu, một đoạn hay một quyển sách, …)
Nội dung trích xuất từ tài liệu:
Bài giảng: Xữ lý tìm kiếm trên chuỗi kí tự 4/14/2011 Strings Strings and Pattern Matching Strings Strings and Pattern Matching Brute Brute Force,  Rabin Karp, Rabin-Karp, Knuth Knuth-Morris-Pratt Regular Expressions Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 2 1 4/14/2011 Bài toán tìm kiếm chuỗi ký tự Đối tượng của bài toán string searching là tìm  kiếm vị trí của một mẫu văn bản (text pattern) trong nội dung một văn bản lớn hơn (một câu, một đoạn hay một quyển sách, …) Cũng như phần lớn các thuật toán khác, quan tâm  chính của string searching là tốc độ và hiệu quả. Có nhiều thuật toán tìm kiễm chuỗi ký tự khác  nhau. Tuy nhiên, chúng ta sẽ chỉ khảo sát ba thuật toán là: Brute Force, Rabin-Karp và Knuth- Morris-Pratt.DöôngDöông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 3 Thuật toán Brute Force Brute Thuật toán Brute Force so sánh mẫu tìm kiếm với  văn bản, mỗi lần 1 ký tự, cho đến khi các ký tự không khớp được tìm thấy: Thuật toán có thể được thiết kế sao cho nó sẽ dừng  khi gặp sự xuất hiện đầu tiên của mẫu trong text hoặc cho đến khi đã xét đến cuoái text.DöôngDöông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 4 2 4/14/2011 Thuật toán Brute Force BruteDöôngDöông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 5 Thuật toán Brute Force Brute Algorithm Algorithm Brute Force(P);  Input:String mẫu P với m ký tự  Ouput:Vị trí chuỗi mẫu P trong T hoặc báo không có  do if (text letter == pattern letter)  so sánh text letter kế với pattern letter kế else  chuyển pattern dịch sang phải 1 letter   until (tìm thấy toàn bộ pattern hoặc đến cuối text)Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 6 3 4/14/2011 Thuaä Thuaät toaùn Brute ForceDöôngDöông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 7 Thuaä Thuaät toaùn Brute Force Độ phức tạp của thuật toán Brute Force: Giả  sử kích thước của mẫu là M ký tự và text có N ký tự  Trường hợp xấu nhất: so sánh mẫu với mọi chuỗi con chiều dài M trong text  Tổng số phép so sánh: M (N-M+1)  Độ phức tạp trong trường hợp xấu nhất : O(MN)Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 8 4 4/14/2011 Thuaä Thuaät toaùn Brute Force Độ phức tạp của thuật toán Brute Force: Giả sử  kích thước của mẫu là M ký tự và text có N ký tự hợp tốt nhất 1: mẫu xuất hiện ngay đầu  Trường text  Độ phức tạp trong trường hợp tốt nhất 1: O(M)  Trường hợp tốt nhất 2: mẫu không xuất hiện trong text  Độ phức tạp trong trường hợp tốt nhất 2: O(N)Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 9 Ví dụ, với M=5 ta có ví dụ sau: với M=5 taDöôngDöông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 10 5 4/14/2011 Thuật toán Rabin-Karp Karp Thuật toán Rabin-Karp tính các giá trị băm n (hash value) của mẫu tìm kiếm và của chuỗi con M ký tự cần so sánh trong văn bản. Nếu các giá trị băm không bằng nhau, thuật toán n sẽ tính giá trị băm cho chuỗi con M ký tự kế tiếp. ...