Luận văn Thạc sĩ Khoa học máy tính: Bài toán đối sánh mẫu sử dụng giải thuật di truyền

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:71

Thêm vào BST

Báo xấu

30
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài “Bài toán đối sánh mẫu sử dụng giải thuật di truyền” nhằm mục đích nghiên cứu bài toán đối sánh mẫu, giải thuật di truyền và ứng dụng của giải thuật di truyền trong đối sánh mẫu và tìm kiếm văn bản. Để hiểu rõ hơn mời các bạn cùng tham khảo nội dung chi tiết của luận văn này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Bài toán đối sánh mẫu sử dụng giải thuật di truyền

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG NGÂN HOÀNG MỸ LINH BÀI TOÁN ĐỐI SÁNH MẪU SỬ DỤNG GIẢI THUẬT DI TRUYỀN LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG NGÂN HOÀNG MỸ LINH BÀI TOÁN ĐỐI SÁNH MẪU SỬ DỤNG GIẢI THUẬT DI TRUYỀN Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Ngƣời hƣớng dẫn khoa học: TS. VŨ MẠNH XUÂN THÁI NGUYÊN - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
i LỜI CAM ĐOAN Tôi xin cam đoan luận văn này của tự bản thân tôi tìm hiểu, nghiên cứu dƣới sự hƣớng dẫn của TS Vũ Mạnh Xuân. Các chƣơng trình thực nghiệm do chính bản thân tôi lập trình, các kết quả là hoàn toàn trung thực. Các tài liệu tham khảo đƣợc trích dẫn và chú thích đầy đủ. TÁC GIẢ LUẬN VĂN Ngân Hoàng Mỹ Linh Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
ii LỜI CẢM ƠN Tôi xin bày tỏ lời cảm ơn chân thành tới tập thể các thầy cô giáo Viện công nghệ thông tin – Viện Hàn lâm Khoa học và Công nghệ Việt Nam, các thầy cô giáo Trƣờng Đại học Công nghệ thông tin và truyền thông - Đại học Thái Nguyên đã dạy dỗ chúng tôi trong suốt quá trình học tập chƣơng trình cao học tại trƣờng. Đặc biệt tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo TS Vũ Mạnh Xuân đã quan tâm, định hƣớng và đƣa ra những góp ý, gợi ý, chỉnh sửa quý báu cho tôi trong quá trình làm luận văn tốt nghiệp. Cuối cùng, tôi xin chân thành cảm ơn các bạn bè đồng nghiệp, gia đình và ngƣời thân đã quan tâm, giúp đỡ và chia sẻ với tôi trong suốt quá trình làm luận văn tốt nghiệp. Thái Nguyên, tháng 08 năm 2015 Ngân Hoàng Mỹ Linh Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
iii MỤC LỤC MỞ ĐẦU .....................................................................................................................1 CHƢƠNG 1 MỘT SỐ THUẬT TOÁN ĐỐI SÁNH MẪU .......................................3 1.1. Giới thiệu về bài toán đối sánh mẫu.....................................................................3 1.2. Phát biểu bài toán .................................................................................................3 1.3. Một số thuật toán đối sánh mẫu cơ bản................................................................4 1.3.1. Thuật toán Brute Force......................................................................................4 1.3.2. Thuật toán Knuth-Morris-Pratt .........................................................................4 1.3.3. Thuật toán Automat hữu hạn.............................................................................5 1.3.4. Thuật toán Boyer-Moore ...................................................................................7 1.3.5. Thuật toán Karp-Rabin ....................................................................................10 1.3.6. Một số thuật toán khác ....................................................................................11 CHƢƠNG 2 GIỚI THIỆU VỀ GIẢI THUẬT DI TRUYỀN ...................................13 2.1. Tổng quan chung về giải thuật di truyền (GA) ..................................................13 2.1.1. Giới thiệu .........................................................................................................13 2.1.2. Các vấn đề cơ bản của GA ..............................................................................15 2.1.3. Sự khác biệt của GA với các giải thuật khác ..................................................18 2.2. Giải thuật di truyền kinh điển.............................................................................20 2.2.1. Giới thiệu .........................................................................................................20 2.2.2. Các toán tử di truyền .......................................................................................21 2.2.3. Các bƣớc quan trọng trong việc áp dụng giải thuật di truyền kinh điển. ........26 2.2.4. Ví dụ ................................................................................................................27 CHƢƠNG 3 BÀI TOÁN ĐỐI SÁNH MẪU SỬ DỤNG GIẢI THUẬT DI TRUYỀN ...................................................................................................................30 3.1. Bài toán đối sánh mẫu trên một file văn bản......................................................30 3.1.1. Phân tích thuật toán .........................................................................................31 3.1.2. Các quá trình hoạt động của chƣơng trình ......................................................36 3.1.3. Kết quả và đánh giá .........................................................................................40 3.2. Bài toán đối sánh mẫu trên nhiều file văn bản ...................................................55 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
iv 3.2.1. Phát biểu bài toán ............................................................................................55 3.2.2. Kết quả thử nghiệm .........................................................................................56 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ................................................................63 *) Kết luận .................................................................................................................63 *) Hƣớng nghiên cứu phát triển ................................................................................63 TÀI LIỆU THAM KHẢO .........................................................................................64 DANH MỤC THUẬT NGỮ, TỪ VIẾT TẮT, KÍ HIỆU GA Giải thuật di truyền NST Nhiễm sắc thể Population Quần thể Pattern matching Đối sánh mẫu TSP Bài toán ngƣời bán hàng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
v DANH MỤC CÁC HÌNH VẼ Hình 1.1 : Sơ đồ automat ............................................................................................6 Hình 1.2. Mis-match trong khi đang so sánh tại vị trí j ..............................................8 Hình 1.3. Good-suffix shift, trƣờng hợp u lại xuất hiện trong x .................................8 Hình 1.4. Good-suffix shift, trƣờng hợp chỉ có suffix của u xuất hiện trong x ..........8 Hình 1.5. Bad-character shift ......................................................................................9 Hình 1.6. ......................................................................................................................9 Hình 2.1. Sơ đồ giải thuật GA ...................................................................................14 Hình 3.1. Giao diện chƣơng trình .............................................................................40 Hình 3.2. Giao diện chƣơng trình mở rộng ...............................................................57 DANH MỤC BẢNG BIỂU Bảng 2.1. Bảng quần thể khởi tạo ban đầu ...............................................................28 Bảng 3.1. Ví dụ về biểu diễn cá thể ..........................................................................36 Bảng 3.2. Kết quả chƣơng trình với độ chính xác 100% ..........................................42 Bảng 3.3. Kết quả chƣơng trình với độ chính xác 90% ............................................43 Bảng 3.4. Kết quả chƣơng trình với độ chính xác 80% ............................................44 Bảng 3.5. Kết quả chƣơng trình với tỉ lệ a – b: 0.5 – 0.5 ..........................................46 Bảng 3.6. Kết quả chƣơng trình với tỉ lệ a – b: 0.6 – 0.4 ..........................................46 Bảng 3.7. Kết quả chƣơng trình với tỉ lệ a – b: 0.8 – 0.2 ..........................................47 Bảng 3.8. Kết quả chƣơng trình với tỉ lệ a – b: 0.9 – 0.1 ..........................................48 Bảng 3.9. Kết quả chƣơng trình mở rộng với độ chính xác 100% ...........................58 Bảng 3.10. Kết quả chƣơng trình mở rộng với độ chính xác 90% ...........................59 Bảng 3.11. Kết quả chƣơng trình mở rộng với độ chính xác 80% ...........................60 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
1 MỞ ĐẦU Hiện nay, cùng với sự phát triển không ngừng của ngành khoa học máy tính chính là việc hệ thống thông tin đƣợc lƣu trữ ngày càng đồ sộ. Đối với một kho thông tin lớn nhƣ vậy, việc ngƣời dùng muốn tra cứu, truy vấn dữ liệu cũng ngày càng khó khăn hơn. Bên cạnh đó, khi lƣợng thông tin phát triển quá nhiều, việc tổ chức, quản lí chúng để làm sao kiểm soát đƣợc việc bùng nổ thông tin cũng là một trong những vấn đề cần quan tâm của các nhà quản lí. Hiện nay đã có rất nhiều công cụ truy vấn có thể hỗ trợ cho ngƣời dùng phần nào trong việc tìm kiếm: * Công cụ tìm kiếm của wikipedia: Chỉ tìm ra tên tựa bài của văn bản nào trùng hợp với từ khóa. * Công cụ tìm kiếm của phần mềm ứng dụng Microsoft word: Công cụ FIND cho phép ngƣời dùng tìm kiếm cụm từ nội bên trong một hồ sơ, văn bản. * Công cụ tìm kiếm của hệ điều hành Microsoft Windows và Adobe Reader: Cả hai công cụ này cho phép tìm kiếm các hồ sơ có chứa từ khóa trong một hồ sơ, một thƣ mục hay trong các ổ đĩa của máy tính. Tuy nhiên, các công cụ trên vẫn tồn tại những hạn chế nhất định.Trong khi đó, công việc tìm kiếm, truy vấn dữ liệu làm sao để nhanh chóng và hiệu quả vẫn đang là một vấn đề cấp thiết đang đƣợc rất nhiều ngƣời dùng quan tâm. Các thông tin đƣợc lƣu trữ trên máy tính tuy lớn nhƣng đa số đều đƣợc lƣu dƣới dạng văn bản, và mặc dù có rất nhiều công cụ tìm kiếm nhƣng cơ chế chung của chúng vẫn là dựa trên phƣơng pháp sử dụng chuỗi. Đối sánh mẫu (pattern matching) là một bài toán quan trọng trong việc hỗ trợ tìm kiếm văn bản đƣợc áp dụng để tìm một xâu khớp với mẫu trong văn bản hoặc tìm các văn bản có chứa mẫu. Giải thuật di truyền (GA – Genetic Algorithms) là một kỹ thuật cơ bản của tính toán mềm nhằm tìm kiếm giải pháp thích hợp cho các bài toán tối ƣu tổ hợp, nó vận dụng các nguyên lý của tiến hóa nhƣ lai ghép, đột biến, chọn lọc. Ngày nay, Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
2 giải thuật di truyền đƣợc ứng dụng rộng rãi trên mọi lĩnh vực nhƣ tin sinh học, khoa học máy tính, trí tuệ nhân tạo, tài chính và một số ngành khác. Đề tài “Bài toán đối sánh mẫu sử dụng giải thuật di truyền” nhằm mục đích nghiên cứu bài toán đối sánh mẫu, giải thuật di truyền và ứng dụng của giải thuật di truyền trong đối sánh mẫu và tìm kiếm văn bản. Ngoài 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.lrc.tnu.edu.vn
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. 1.1. 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 .[6] 1.2. 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.lrc.tnu.edu.vn
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. 1.3. Một số thuật toán đối sánh mẫu cơ bản 1.3.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ả. 1.3.2. 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.H.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.lrc.tnu.edu.vn
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]. Khi đó x[1…i] = y[j…i+j-1] = u và a = x[i] y[i+j] = b. 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. 1.3.3. 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.lrc.tnu.edu.vn
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.lrc.tnu.edu.vn
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). 1.3.4. 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). Đối với mẫu x[0…m-1], ta dùng 01 biến số chỉ số i chạy từ cuối về đầu, đối với chuỗi y[0…n-1], ta dùng 01 biến j để chốt ở phía đầu. Giả sử trong quá trình so sánh, ta gặp 1 mis-match tại vị trí x[i] = a của mẫu và y[i+j] = b trong khi đang thử khớp tại vị trí j. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
8 Hình 1.2. Mis-match trong khi đang so sánh tại vị trí j Khi đó, x[i+1...m-1] = y[j+i+1…j+m-1] = u và x[i] ≠ y[i+j]. Bây giờ ta đi xét đối với từng trƣờng hợp, 2 hàm trên sẽ thực hiện việc di chuyển nhƣ thế nào: - Phép dịch chuyển good-suffix shift sẽ dịch cửa sổ sang bên phải cho đến khi gặp 1 kí tự khác với x[i] trong trƣờng hợp đoạn u lại xuất hiện trong x. Hình 1.3. Good-suffix shift, trường hợp u lại xuất hiện trong x - Nếu đoạn u không xuất hiện lại trong x, mà chỉ có 1 phần cuối (suffix) của u khớp với phần đầu (prefix) của x, thì ta sẽ dịch 1 đoạn sao cho phần suffix dài nhất v của y[j+i+1…j+m-1] khớp với prefix của x. Hình 1.4. Good-suffix shift, trường hợp chỉ có suffix của u xuất hiện trong x - Phép dịch chuyển bad-character shift sẽ khớp kí tự y[i+j] với 1 kí tự (bên trái nhất) trong đoạn x[0…m-2]. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
9 Hình 1.5. Bad-character shift - Nếu y[i+j] không xuất hiện trong x, ta thấy ngay rằng không có xuất hiện nào của x trong y mà chứa y[i+j], do đó ta có thể đặt cửa sổ ngay sau y[i+j], tức là y[j+i+1]. Hình 1.6. Thuật toán Boyer-Moore sẽ chọn đoạn dịch chuyển dài nhất trong 2 hàm dịch chuyển good-suffix và bad-character shift. Hai hàm này đƣợc định nghĩa nhƣ sau: Hàm good-suffix shift đƣợc lƣu trong bảng bmGs có kích thƣớc m+1. Ta định nghĩa 2 điều kiện sau: + Cs(i,s): với mỗi k mà i < k < m, s ≥ k hoặc x[k-s] = x[k] + Co(i,s): nếu s < i thì x[i-s] ≠ x[i]. Khi đó, với 0 ≤ i < m: bmGs[i+1] = min{s>0: Cs(i,s) and Co(i,s) hold} Và chúng ta định nghĩa bmGs[0] là độ dài chu kỳ của x. Việc tính toán bảng bmGs sử dụng 1 bảng suff đƣợc định nghĩa nhƣ sau: Với 1 ≤ i < m, suff[i] = max{k: x[i-k+1…i] = x[m-k…m-1]} Hàm bad-character shift đƣợc lƣu trong bảng bmBc có kích thƣớc . Cho c trong ∑: bmBc[c] = min{i: 1 ≤ i
10 Bảng bmGs và bmBc đƣợc tính toán trong thời gian O(m+ ) trƣớc khi thực hiện tìm kiếm và cần 1 không gian phụ là O(m+ ). Giai đoạn tìm kiếm có độ phức tạp thời gian bậc 2 nhƣng lại chỉ có 3n phép so sánh khi tìm kiếm 1 chuỗi không có chu kì. Đối với việc tìm kiếm trong một khối lƣợng lớn các chữ cái, thuật toán có thể thực hiện với một tốc độ rất nhanh. Khi tìm kiếm chuỗi am-1 trong bn chuỗi, thuật toán chỉ sử dụng O(m/n) phép so sánh, là chi phí thấp nhất của các thuật toán tìm kiếm hiện đại có thể đạt đƣợc [2]. 1.3.5. Thuật toán Karp-Rabin Thuật toán mang tên hai nhà khoa học phát minh ra nó là Richard M.Karp (sinh năm 1931,ngƣời Mỹ) và Michael O.Rabin (sinh năm 1931,ngƣời Đức). Tƣ tƣởng chính của phƣơng pháp này là sử dụng phƣơng pháp băm (hashing). Tức là mỗi một xâu sẽ đƣợc gán với một giá trị của hàm băm (hash function). Ví dụ, có xâu “hello” đƣợc gán với giá trị bằng 5, và hai xâu đƣợc gọi là bằng nhau nếu giá trị hàm băm của nó bằng nhau.Nhƣ vậy, thay vì việc phải đối sánh các xâu con của T với mẫu P, ta chỉ cần so sánh giá trị hàm băm của chúng và đƣa ra kết luận. Trong thuật toán này, hàm băm phải thỏa mãn một số tính chất nhƣ phải dễ dàng tính đƣợc trên chuỗi, và đặc biệt công việc tính lại phải đơn giản để ít ảnh hƣởng đến thời gian thực hiện của thuật toán. Chẳng hạn hàm băm đƣợc chọn ở đây là: hash(w[i…i+m-1]) = h = (w[i]*dm-1 + w[i+1]*dm-2 + … w[i+m-1]*d0) mod q. Việc tính lại hàm băm sau khi dịch cửa sổ đi một ký tự chỉ đơn giản nhƣ sau: h = ((h – w[i]*dm-1)*d + w[i+m] Trong bài toán này ta có thể chọn d = 2 để tiện cho việc tính toán a*2 tƣơng đƣơng a shl 1. Và không chỉ thế ta chọn q = MaxLongint khi đó phép mod q không cần thiết phải thực hiện vì sự tràn số trong tính toán chính là một phép mod có tốc độ rất nhanh. Thuật toán Karp-Rabin sử dụng hàm băm tính toán nhanh, không phụ thuộc vào chiều dài chuỗi cần tìm kiếm; tiết kiệm bộ nhớ vì không lƣu trữ nhiều kết quả Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
11 tìm kiếm trƣớc đó; không sử dụng các phƣơng pháp nhận biết, loại trừ các kết quả xấu cho các bƣớc tiếp theo. 1.3.6. Một số thuật toán khác Một số thuật toán nêu trên chƣa phải là tất cả các thuật toán đối sánh mẫu hiện có. Nhƣng chúng đã đại diện cho đa số các tƣ tƣởng dùng để giải bài toán đối sánh. Các thuật toán so sánh mẫu lần lượt từ trái sang phải thƣờng là các dạng của thuật toán Knuth-Morris-Pratt và thuật toán sử dụng Automat nhƣ: Forward Dawg Matching, Apostolico-Crochemore, Not So Naive, … Các thuật toán so sánh mẫu từ phải sang trái đều là các dạng của thuật toán Boyer-Moore. Phải nói lại rằng thuật toán BM là thuật toán tìm kiếm rất hiệu quả trên thực tế nhƣng độ phức tạp tính toán lý thuyết lại là O(m*n). Chính vì vậy những cải tiến của thuật toán này cho độ phức tạp tính toán lý thuyết tốt nhƣ: thuật toán Apostolico-Giancarlo đánh dấu lại những ký tự đã so sánh rồi để khỏi bị so sánh lặp lại, thuật toán Turbo-BM đánh giá chặt chẽ hơn các thông tin trƣớc để có thể dịch đƣợc xa hơn và ít bị lặp, … Còn có một số cải tiến khác của thuật toán BM không làm giảm độ phức tạp lý thuyết mà dựa trên kinh nghiệm để có tốc độ tìm kiếm nhanh hơn trong thực tế. Ngoài ra, một số thuật toán kết hợp quá trình tìm kiếm của BM vào hệ thống Automat mong đạt kết quả tốt hơn. Các thuật toán so sánh mẫu theo thứ tự đặc biệt: - Thuật toán Galil-Seiferas và Crochemore-Perrin chia mẫu thành hai đoạn, đầu tiên kiểm tra đoạn ở bên phải rồi mới kiểm tra đoạn bên trái với chiều từ trái sang phải. - Thuật toán Colussi và Galil-Giancarlo lại chia mẫu thành hai tập và tiến hành tìm kiếm trên mỗi tập với một chiều khác nhau. - Thuật toán Optimal Mismatch và Maximal Shift sắp xếp thứ tự mẫu dựa vào mật độ của ký tự và khoảng dịch đƣợc. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
12 - Thuật toán Skip Search, KMP Skip Search và Alpha Skip Search dựa sự phân bố các ký tự để quyết định vị trí bắt đầu của mẫu trên văn bản. Các thuật toán so sánh mẫu theo thứ tự bất kỳ: Đó là các thuật toán có thể tiến hành so sánh mẫu với cửa sổ theo một thứ tự ngẫu nhiên. Những thuật toán này đều có cài đặt rất đơn giản và thƣờng sử dụng chiêu ký tự không khớp của thuật toán Boyer-Moore. Có lẽ loại thuật toán này dựa trên ý tƣởng càng so sánh loạn càng khó kiếm test chết. Vì dựa hoàn toàn trên vị trí đƣợc lấy ngẫu nhiên nên kết quả chỉ là mong đợi ngẫu nhiên chứ không có một cơ sở toán học nào để lấy vị trí ngẫu nhiên sao cho khả năng xuất hiện mẫu cần tìm là lớn. Các thuật toán đối sánh mẫu trình bày ở trên đã đƣợc sử dụng phổ biến, tƣ tƣởng chủ đạo vẫn là tìm kiếm từ đầu văn bản tới cuối văn bản. Trong đề tài này hƣớng đến một cách tiếp cận mới là sử dụng giải thuật di truyền thuộc lớp giải thuật xác suất, phƣơng pháp mô phỏng theo quá trình chọn lọc tự nhiên của sinh vật. Từ một quần thể ban đầu, các cá thể đƣợc đánh giá qua sự thích nghi tốt hay xấu, từ đó quyết định cá thể đó có thể tồn tại hay không. Áp dụng với bài toán này, từ một tập các vị trí trong văn bản tìm kiếm ban đầu, các vị trí trong tập ban đầu đƣợc chọn lọc qua nhiều bƣớc, các vị trí tốt đƣợc giữ lại và tiến hóa tới khi đạt độ chính xác tốt nhất, đồng thời các vị trí xấu bị loại bỏ. Trong các chƣơng tiếp theo sẽ trình bày cụ thể về giải thuật di truyền và cài đặt thực nghiệm giải thuật di truyền giải bài toán đối sánh mẫu. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
13 CHƢƠNG 2 GIỚI THIỆU VỀ GIẢI THUẬT DI TRUYỀN Chương này giới thiệu tổng quan về giải thuật di truyền. Các toán tử của giải thuật di truyền và những điểm khác biệt của giải thuật di truyền với các giải thuật khác.[1],[3],[4],[5],[9] 2.1. Tổng quan chung về giải thuật di truyền (GA) 2.1.1. Giới thiệu Lí thuyết về giải thuật di truyền trong những năm qua đã phát triển rất mạnh và theo nhiều hƣớng tiếp cận khác nhau. Sở dĩ nhƣ vậy là do tính hiệu quả của giải thuật này so với các giải thuật khác. Giải thuật di truyền đã thể hiện rõ tính ƣu việt trong tìm kiếm tiến hoá và tính mềm dẻo trong khả năng thích nghi với yêu cầu của bài toán đặt ra, đặc biệt đối với các bài toán khó, có không gian tìm kiếm lớn và có nhiều ràng buộc phức tạp. Giải thuật di truyền đƣợc J.H.Holland và các đồng nghiệp của ông tại trƣờng đại học Michigan giới thiệu năm 1975, và đã có rất nhiều công trình nghiên cứu về lí thuyết cũng nhƣ ứng dụng của nó đƣợc công bố trong những năm gần đây. GA đƣợc ứng dụng trong nhiều lĩnh vực khác nhau nhƣ: Sinh học, khoa học cơ bản, khoa học máy tính, trí tuệ nhân tạo. Giải thuật di truyền là kỹ thuật phỏng theo quá trình thích nghi tiến hoá của các quần thể sinh học dựa trên học thuyết Darwin. Cũng nhƣ các thuật toán tiến hoá khác, GA đƣợc hình thành dựa trên một quan niệm đƣợc coi là một tiên đề phù hợp với thực tế khách quan. Đó là quan niệm “quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu”. Quá trình tiến hoá thể hiện tối ƣu ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trƣớc. Tƣ tƣởng của GA là mô phỏng các hiện tƣợng tự nhiên: kế thừa và đấu tranh sinh tồn. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn