phần mở đầu và kết luận, luận văn gồm có 3 chƣơng: - Chƣơng 1: Một số thuật toán đối sánh mẫu - Chƣơng 2: Giới thiệu về giải thuật di truyền - Chƣơng 3: Bài toán đối sánh mẫu sử dụng giải thuật di truyền Phƣơng pháp nghiên cứu Trong luận văn, học viên đã sử dụng các phƣơng pháp nghiên cứu chính sau: - Phƣơng pháp nghiên cứu lý thuyết: Tìm tòi, tổng hợp tài liệu, hệ thống lại các kiến thức, tìm hiểu các khái niệm, thuật toán sử dụng trong luận văn. - Lập trình thử nghiệm: Luận văn sử dụng ngôn ngữ lập trình là Visual Studio C# 2012 để viết chƣơng trình thử nghiệm. - Các phƣơng pháp so sánh. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 3 CHƢƠNG 1 MỘT SỐ THUẬT TOÁN ĐỐI SÁNH MẪU Chương này giới thiệu và phát biểu bài toán đối sánh mẫu, tìm hiểu một số thuật toán đã và đang được sử dụng để giải bài toán đối sánh mẫu.
Giới thiệu về bài toán đối sánh mẫu Trong khoa học máy tính, đối sánh mẫu là hành động kiểm tra xem một trình tự các kí tự có hiện diện trong một xâu cho trƣớc hay không. Ngƣợc lại với nhận dạng mẫu, đối sánh mẫu thƣờng có sự chính xác hơn. Dạng phổ biến nhất của bài toán đối sánh mẫu là: Cho trƣớc nguồn tìm kiếm là một tập D các văn bản, cho một câu hỏi dạng văn bản q (thƣờng là một từ, một xâu văn bản ngắn), hãy tìm tất cả các văn bản thuộc D mà có chứa q. Trong nhiều trƣờng hợp (chẳng hạn, tìm kiếm thông qua máy tìm kiếm) q còn đƣợc gọi là “truy vấn” và bài toán còn có tên gọi là “tìm kiếm theo truy vấn”.
Để tìm đƣợc các văn bản có chứa văn bản truy vấn q, hệ thống tìm kiếm cần phải kiểm tra văn bản truy vấn q có là một xâu con của các văn bản thuộc tập D hay không (sánh mẫu) và đƣa ra các văn bản đáp ứng. Trong nhiều trƣờng hợp, bài toán còn đòi hỏi tìm tất cả các vị trí của các xâu con trong văn bản trùng với q. Đồng thời, điều kiện tìm kiếm có thể đƣợc làm “xấp xỉ” theo nghĩa văn bản kết quả có thể không cần chứa q mà chỉ cần “liên quan” tới q, nghĩa là có xâu con trong văn bản xấp xỉ q. Có thể thấy, các máy tìm kiếm sử dụng cả cơ chế tìm kiếm xấp xỉ khi mà văn bản kết quả tìm kiếm không chứa hoàn toàn chính xác văn bản truy vấn.
Phát biểu bài toán Đối sánh mẫu là một bài toán cơ bản trong xử lý văn bản, bài toán yêu cầu tìm ra một hoặc nhiều vị trí xuất hiện của mẫu q trên một văn bản S. Mẫu q và văn bản S là các chuỗi có độ dài M và N (M ≤ N); q và S là các xâu ký tự trên cùng một bảng chữ cái Σ có δ ký tự. Bài toán sánh mẫu tổng quát đƣợc phát biểu nhƣ sau: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 “Cho mẫu q độ dài M và văn bản S độ dài N trên cùng bảng chữ Σ. Tìm một (hoặc tất cả) các lần xuất hiện của mẫu q trong S”.
Trong bài toán tìm kiếm văn bản trên tập văn bản D, bài toán sánh mẫu đƣợc thực hiện đối với mọi cặp gồm mẫu q và mọi văn bản d D. Trong trƣờng hợp độ dài N của d rất lớn và số lƣợng văn bản trong D rất nhiều thì thời gian tìm kiếm văn bản phù hợp với truy vấn q sẽ là rất tốn kém. Một số thuật toán đối sánh mẫu cơ bản 1. Thuật toán Brute Force Thuật toán Brute Force là dạng thuật toán tìm kiếm tuần tự, nó thử kiểm tra tất cả các vị trí trên văn bản từ 1 cho đến n – m + 1.
Sau mỗi lần thử, thuật toán Brute Force dịch mẫu sang phải một ký tự cho đến khi kiểm tra hết văn bản. Thuật toán Brute Force không cần công việc chuẩn bị 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(n*m). Thuật toán đƣợc xây dựng đơn giản, nhƣng với văn bản lớn thì thuật toán này tỏ ra không hiệu quả.
Thuật toán Knuth-Morris-Pratt Thuật toán đƣợc phát minh năm 1977 bởi hai giáo sƣ của ĐH Stanford, Hoa Kỳ (một trong số ít các trƣờng đại học xếp hàng số một về khoa học máy tính trên thế giới, cùng với trƣờng MIT, CMU cũng của Hoa Kỳ và Cambrige của Anh) là Donal Knuth và Vaughan Ronald Pratt. Giáo sƣ Knuth (giải Turing năm 1971) còn rất nổi tiếng với cuốn sách “Nghệ thuật lập trình” (The Art of Computer Programming), hiện nay đã có đến tập 6. Ba tập đầu tiên đã xuất bản ở Việt Nam, là một trong những cuốn sách gối đầu giƣờng cho bất kì lập trình viên nói riêng và những ai yêu thích lập trình máy tính nói chung trên toàn thế giới. Thuật toán này còn có tên là KMP, tức là lấy tên viết của ba ngƣời đồng phát minh ra nó, chữ “M” là chỉ giáo sƣ J.Morris, cũng là một giáo sƣ rất nổi tiếng trong ngành khoa học máy tính.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 Ý tƣởng chính của phƣơng pháp này nhƣ sau: Trong quá trình tìm kiếm vị trí của mẫu P trong xâu gốc T, nếu tìm thấy một vị trí sai, ta chuyển sang vị trí tìm kiếm tiếp theo và quá trình tìm kiếm này sẽ đƣợc tận dụng thông tin từ quá trình tìm kiếm trƣớc để tránh việc phải xét lại các trƣờng hợp không cần thiết. Thuật toán Knuth-Morris-Pratt là thuật toán có độ phức tạp tuyến tính đầu tiên đƣợc phát hiện ra, nó dựa trên thuật toán Brute force với ý tƣởng lợi dụng lại những thông tin của lần thử trƣớc cho lần sau. Trong thuật toán Brute force vì chỉ dịch cửa sổ đi một ký tự nên có đến m-1 ký tự của cửa sổ mới là những ký tự của cửa sổ vừa xét. Trong đó có thể có rất nhiều ký tự đã đƣợc so sánh giống với mẫu và bây giờ lại nằm trên cửa sổ mới nhƣng đƣợc dịch đi về vị trí so sánh với mẫu.
Việc xử lý những ký tự này có thể đƣợc tính toán trƣớc rồi lƣu lại kết quả. Nhờ đó lần thử sau có thể dịch đi đƣợc nhiều hơn một ký tự, và giảm số ký tự phải so sánh lại. Xét lần thử tại vị trí j, khi đó cửa sổ đang xét bao gồm các ký tự y[j…j+m-1], giả sử sự khác biệt đầu tiên xảy ra giữa hai ký tự x[i] và y[j+i-1]. Với trƣờng hợp này, dịch cửa sổ phải thỏa mãn v là phần đầu của xâu x khớp với phần đuôi của xâu u trên văn bản.
Hơn nữa ký tự c ở ngay sau v trên mẫu phải khác với ký tự a. Trong những đoạn nhƣ v thoả mãn các tính chất trên ta chỉ quan tâm đến đoạn có độ dài lớn nhất. Thuật toán Knuth-Morris-Prath sử dụng mảng Next để lƣu trữ độ dài lớn nhất của xâu v trong trƣờng hợp xâu u=x[1…i-1]. Mảng này có thể tính trƣớc với chi phí về thời gian là O(m).
Thuật toán này có chi phí về thời gian là O(m+n) với nhiều nhất là 2n-1 lần số lần so sánh kí tự trong quá trình tìm kiếm. Thuật toán Automat hữu hạn Trong thuật toán này, quá trình tìm kiếm đƣợc đƣa về một quá trình biến đổi trạng thái automat. Hệ thống automat trong thuật toán DFA sẽ đƣợc xây dựng dựa Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 trên xâu mẫu. Mỗi trạng thái (nút) của automat lúc sẽ đại diện cho số ký tự đang khớp của mẫu với văn bản.
Các ký tự của văn bản sẽ làm thay đổi các trạng thái. Và khi đạt đƣợc trạng cuối cùng có nghĩa là đã tìm đƣợc một vị trí xuất hiện ở mẫu. Thuật toán này có phần giống thuật toán Knuth-Morris-Pratt trong việc nhảy về trạng thái trƣớc khi gặp một ký tự không khớp, nhƣng thuật toán DFA có sự đánh giá chính xác hơn vì việc xác định vị trí nhảy về dựa trên ký tự không khớp của văn bản (trong khi thuật toán KMP lùi về chỉ dựa trên vị trí không khớp). Ví dụ: Ta có xâu mẫu là GCAGAGAG với hệ automat sau : Hình 1.1 : Sơ đồ automat Với ví dụ ở trên ta có: Nếu đang ở trạng thái 2 gặp ký tự A trên văn bản sẽ chuyển sang trạng thái 3.
Nếu đang ở trạng thái 6 gặp ký tự C trên văn bản sẽ chuyển sang trạng thái 2. Trạng thái 8 là trạng thái cuối cùng, nếu đạt đƣợc trạng thái này có nghĩa là đã tìm thấy một xuất hiện của mẫu trên văn bản. Trạng thái 0 là trạng thái mặc định (các liên kết không đƣợc biểu thị đều chỉ về trạng thái này), ví dụ ở nút 5 nếu gặp bất kỳ ký tự nào khác G thì đều chuyển về trạng thái 0. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 Việc xây dựng hệ automat khá đơn giản khi đƣợc cài đặt trên ma trận kề.
Khi đó thuật toán có thời gian xử lý là O(n); thời gian và bộ nhớ để tạo ra hệ automat là O(m* ) (tùy cách cài đặt). Thuật toán Boyer-Moore Thuật toán Boyer Moore là thuật toán tìm kiếm chuỗi rất có hiệu quả trong thực tiễn, các dạng khác nhau của thuật toán này thƣờng đƣợc cài đặt trong các chƣơng trình soạn thảo văn bản. Các đặc điểm chính của nó: - Thực hiện việc so sánh từ phải sang trái. - Giai đoạn tiền xử lý (preprocessing) có độ phức tạp thời gian và không gian là O(m + ).
- Giai đoạn tìm kiếm có độ phức tạp O(m*n). - So sánh tối đa 3n kí tự trong trƣờng hợp xấu nhất đối với mẫu không có chu kỳ (non periodic pattern). - Độ phức tạp O(m/n) trong trƣờng hợp tốt nhất. Trong cài đặt ta dùng mảng bmGs để lƣu cách dịch 1, mảng bmBc để lƣu phép dịch thứ 2 (ký tự không khớp).
Thuật toán sẽ quét các kí tự của mẫu (pattern) từ phải sang trái, bắt đầu từ phần tử cuối cùng. Trong trƣờng hợp mis-match (hoặc là trƣờng hợp đã tìm đƣợc 01 đoạn khớp với mẫu), nó sẽ dùng 2 hàm đƣợc tính toán trƣớc để dịch cửa sổ sang bên phải. Hai hàm dịch chuyển này đƣợc gọi là good-suffix shift ( còn đƣợc biết với cái tên phép dịch chuyển khớp) và bad-character shift (hay phép dịch chuyển xuất hiện).