Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo chuyên đề Công nghệ phần mềm: Pattern searching

Nội dung nghiên cứu đề tài trình bày về tìm kiếm mẫu từ trái qua phải; tìm kiếm mẫu từ phải qua trái; tìm kiếm mẫu từ vị trí cụ thể; tìm kiếm mẫu từ vị trí bất kì. Mời các bạn cùng tham khảo! | Youtube.com PoppinKhiem HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG KHOA CÔNG NGHỆ THÔNG TIN 1 BÁO CÁO MÔN CHUYÊN ĐỀ CÔNG NGHỆ PHẦN MỀM CHỦ ĐỀ PATTERN SEARCHING Giảng viên Nguyễn Duy Phương Sinh viên Mã SV B52 Nhóm MH 1 Youtube.com PoppinKhiem Hà Nội 3 7 2021 2 Youtube.com PoppinKhiem Muc luc ̣ ̣ I. Tim kiêm mâu t ̀ ́ ̃ ừ trai qua phai ́ ̉ 1. Thuật toán Brute Force. 2. Thuật toán Knuth Morris Pratt. 3. Thuật toán Karp Rabin. 4. Thuật toán Morris Pratt. 5. Thuật toán Search with an automaton. II. Tìm kiêm mâu t ́ ̃ ừ phai qua trai ̉ ́ 1. Thuật toán Boyer Moore. 2. Thuật toán Turbo Boyer Moore. 3. Zhu Takaota. 4. Thuật toán Berry Ravindran . 5. Thuật toán Apostollico giancarlo. 6. Thuật toán Colussi. III. Tim kiêm mâu t ̀ ́ ̃ ừ vi tri cu thê ̣ ́ ̣ ̉ 1. Thuật toán Skip Search. 2. Thuật toán Galil Giancarlo. IV. Tim kiê ̀ ́m mâu t ̃ ư vi tri bât ki ̀ ̣ ́ ́ ̀ 1. Thuật toán Quick Search. 2. Thuật toán Smith. 3. Thuật toán Raita. 4. Thuật toán HorsePool. 3 Youtube.com PoppinKhiem I. Tìm kiếm mẫu từ trái qua phải 1. Thuật toán Brute Force Đặc điểm Không có giai đoạn tiền xử lý Bộ nhớ cần dùng cố định Luôn luôn dịch 1 bước sang phải Việc so sánh có thể phải dùng trong các trường hợp Độ phức tạp pha thực thi là O m x n So sánh khoảng 2n ký tự Trình bày thuật toán Thuật toán Brute Force kiểm tra ở tất cả các vị trí trong đoạn văn bản giữa 0 và n m không cần quan tâm liệu mẫu này có tồn tại ở vị trí đó hay không. Sau đó sau mỗi lần kiểm tra mẫu sẽ dịch sang phải một vị trí. Thuật toán Brute Force không cần giai đoạn tiền xử lý cũng như các mảng phụ cho quá trình tìm kiếm. Độ phức tạp tính toán của thuật toán này là O m.n . Code void BruteForce char x int m char y int n for int i 0 iYoutube.com PoppinKhiem Kiểm nghiệm thuật toán Xâu X AB Xâu Y ABDAAB 1 Y A B D A A B X A 1 B 2 2 Y A B D A A B X A B 3 Y A B D A A B X A 4 Y A B D A A B X A 1 B 5 Y A B D A A B X A 1 B 2 2. Thuật toán Knuth Morris Pratt Đặc điểm Thực hiện từ trái qua phải Pha tiền xử lý PreKMP có độ phức tạp không .