Tài liệu Tìm kiếm mờ và ứng dụng tìm kiếm thông tin trong các văn bản nén

ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN ĐỖ THỊ HẠNH TÌM KIẾM MỜ VÀ ỨNG DỤNG TÌM KIẾM THÔNG TIN TRONG CÁC VĂN BẢN NÉN Chuyên ngành: Khoa học máy tính Mã số: 60 48 35 01 LUẬN VĂN THẠC SĨ Người hướng dẫn: PGS.TS. ĐOÀN VĂN BAN Thái Nguyên - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN ĐỖ THỊ HẠNH TÌM KIẾM MỜ VÀ ỨNG DỤNG TÌM KIẾM THÔNG TIN TRONG CÁC VĂN BẢN NÉN Chuyên ngành: Khoa học máy tính Mã số: 60 48 35 01 LUẬN VĂN THẠC SĨ Người hướng dẫn: PGS.TS. ĐOÀN VĂN BAN Thái Nguyên - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CẢM ƠN Em xin chân thành cảm ơn các thầy, cô khoa Công nghệ thông tin trường Đại học Thái Nguyên đã tạo điều kiện giúp đỡ và truyền đạt cho em những kiến thức về chuyên ngành và những kiến thức xã hội. Đặc biệt, em xin bày tỏ lòng biết ơn sâu sắc đến PGS.TS. Đoàn Văn Ban - Viện Khoa học Công nghệ Việt Nam. Thầy đã trực tiếp hướng dẫn và giúp đỡ em hoàn thành luận văn. Mặc dù, trong quá trình làm luận văn em đã gặp nhiều khó khăn nhưng thầy luôn động viên, chia sẻ, đó là nguồn động lực lớn giúp em vượt qua. Thầy chính là tấm gương cho em trong công tác giảng dạy, nghiên cứu khoa học, cũng như trong cuộc sống. Em xin cảm ơn thầy. Em không quên sự động viên, khích lệ của gia đình, bạn bè và những người thân đã giúp đỡ em vượt qua mọi khó khăn để em hoàn thành khoá học. Em xin chân thành cảm ơn! Thái Nguyên, tháng 11 năm 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MỤC LỤC MỞ ĐẦU ............................................................................................... 1 Chương 1. TÌM KIẾM MẪU TRONG VĂN BẢN THEO CÁCH TIẾP CẬN OTOMAT MỜ .................................................................. 5 1.1. Tổng quan về tìm kiếm mẫu trên văn bản .................................... 5 1.1.1 Giới thiệu chung về vấn đề tìm kiếm văn bản ............................ 5 1.1.2. Các dạng tìm kiếm và các kết quả nghiên cứu .......................... 7 1.1.2.1. Tìm đơn mẫu ..................................................................... 7 1.1.2.2. Tìm đa mẫu ........................................................................ 8 1.1.2.3. Tìm mẫu mở rộng .............................................................. 9 1.1.2.4. Tìm kiếm xấp xỉ ............................................................... 10 1.1.2.4.1. Phát biểu bài toán ..................................................... 10 1.1.2.4.2. Các tiếp cận tìm kiếm xấp xỉ ..................................... 11 1.1.2.4.3. Độ tương tự giữa hai xâu .......................................... 12 1.1.3. Tìm kiếm trong văn bản nén và mã hoá .................................. 14 1.2. Hệ mờ ........................................................................................ 15 1.3. Ý tưởng chung của tiếp cận otomat mờ...................................... 15 1.4. Khái niệm otomat mờ ................................................................ 17 1.5. Một số thuật toán so mẫu ........................................................... 18 1.5.1. Thuật toán KMP ( Knuth- Morris- Pratt) ................................ 18 1.5.2. Thuật toán BM ( Boyer- Moor) ............................................... 22 1.6. Kết luận chương 1 ..................................................................... 26 Chương 2. BÀI TOÁN SO MẪU THEO CÁCH TIẾP CẬN OTOMAT MỜ.................................................................................... 27 2.1. Bài toán so mẫu chính xác ......................................................... 27 2.1.1. Phát biểu bài toán ................................................................... 27 2.1.2. Độ mờ của mô hình ................................................................ 27 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2.1.3. Thuật toán KMP mờ ............................................................... 28 2.1.3.1. Otomat so mẫu ................................................................. 28 2.1.3.2. Tính đúng đắn của thuật toán ........................................... 29 2.1.3.3. Thuật toán ........................................................................ 29 2.1.3.4. So sánh KM P và thuật toán KMP mờ ............................. 32 2.1.4. Thuật toán KMP - BM mờ ...................................................... 33 2.1.4.1. Ý tưởng của thuật toán ..................................................... 33 2.1.4.2. Otomat mờ so mẫu ........................................................... 35 2.1.4.3. Thuật toán 2.4 .................................................................. 37 2.2. Bài toán so mẫu xấp xỉ............................................................... 38 2.2.1. Đặt vấn đề............................................................................... 38 2.2.2. Bài toán .................................................................................. 39 2.2.3. Độ tương tự dựa trên độ dài khúc con chung của hai xâu ........ 40 2.2.3.1. Phát biểu bài toán............................................................. 40 2.2.3.2. Otomat so mẫu ................................................................. 42 2.2.4. Độ gần tựa ngữ nghĩa.............................................................. 43 2.2.4.1. Ý tưởng về độ gần ........................................................... 43 2.2.4.2. Thuật toán sơ bộ tính độ gần ............................................ 44 2.2.4.2.1. Ý tưởng ..................................................................... 44 2.2.4.2.2. Thuật toán chi tiết ..................................................... 44 2.2.4.3. Giải thích độ mờ của mô hình .......................................... 45 2.3. Kết luận chương 2 ..................................................................... 46 Chương 3. TÌM KIẾM MẪU TRONG VĂN BẢN NÉN VÀ MÃ HOÁ .................................................................................................... 47 3.1. Tiếp cận tìm kiếm tổng quát trên văn bản nén và mã hoá ........... 47 3.2. Tìm kiếm trên văn bản nén ........................................................ 50 3.2.1. Các mô hình nén văn bản ........................................................ 50 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 3.2.2. Thuật toán tìm kiếm trên dữ liệu nén dạng text ....................... 50 3.3. Tìm kiếm trên văn bản mã hóa................................................... 55 3.3.1. Tìm kiếm trên văn bản mã hóa dạng khối kí tự ....................... 55 3.3.2. Mã đàn hồi .............................................................................. 55 3.3.3. Tìm kiếm trên văn bản mã hóa bởi mã đàn hồi ....................... 58 3.3.3.1. Ý tưởng chung ................................................................. 58 3.3.3.2. Phương pháp đánh giá độ mờ xuất hiện mẫu trên văn bản mã hóa .......................................................................................... 59 3.3.3.2.1. Bài toán .................................................................... 59 3.3.3.2.2. Mô tả phương pháp ................................................... 59 3.3.3.2.3. Chi tiết hóa các otomat trong thuật toán ................... 60 3.3.3.2.4. Thuật toán tìm kiếm mẫu dựa trên otomat ................. 61 3.3.4. Tìm kiếm trên văn bản mã hóa hai tầng .................................. 63 3.4. Kết luận chương 3 ..................................................................... 64 KẾT LUẬN ......................................................................................... 65 TÀI LIỆU THAM KHẢO.................................................................. 67 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Các ký hiệu  Xâu rỗng wi Ký tự thứ i của xâu w w(f, d) Xâu con (hay khúc con) độ dài f của xâu w, kết thúc ở vị trí d trên w w1 ≤ s w2 Xâu w1 là khúc đuôi của w2 w1 ≤ ls w2 Xâu w1 là khúc đuôi dài nhất của w2 w(t) hoặc preft(w) Khúc đầu độ dài t của xâu w suft(w) Khúc cuối độ dài t của xâu w |A| Lực lượng của tập A Các chữ viết tắt NFA Otomat đa định hữu hạn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn DANH MỤC CÁC HÌNH VẼ Hình 1.1. Ý nghĩa của mảng next ......................................................... 19 Hình 1.2. Ý nghĩa của mảng next tại vị trí m + 1 .................................. 19 Hình 2.1. Dịch chuyển con trỏ trên mẫu ............................................... 32 Hình 2.2. Ý tưởng chung của thuật toán KMP-BM mờ ........................ 35 Hình 2.3. Một ví dụ với các khối độ dài t = 3 ....................................... 44 Hình 2.4. Tập mờ mô tả độ gần tựa ngữ nghĩa của mẫu P so với xâu đích S................................................................. 45 Hình 3.1. Phương pháp so mẫu trên miền nén có sử dụng otomat mờ .. 48 Hình 3.2. Phương pháp so mẫu không giải mã ..................................... 49 Hình 3.3. Queue trước (a) và sau (b) khi thực hiện thủ tục Decompress 52 Hình 3.4. Queue trước (a) và sau (b) bước nhảy n2‟ ............................. 53 Hình 3.5. Đồ thị xây dựng khái niệm tích đàn hồi ................................ 56 Hình 3.6. Đồ thị xác định mã đàn hồi ................................................... 58 Hình 2.7. Quá trình mã hóa hai tầng ..................................................... 64 Hình 2.8. Quá trình giải mã hai tầng ..................................................... 64 Hình 2.9. Quá trình tìm kiếm mẫu trên văn bản mã hóa hai tầng .......... 64 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MỞ ĐẦU 1. Lý do chọn đề tài Bộ não của con người có thể xử lý thông tin ở hai mức: - Mức định lượng (chính xác) - Mức định tính (không chính xác, bất định, mơ hồ, không chắc chắn, nhập nhằng, không rõ ràng, mờ) Tính thông minh trong quá trình xử lý thông tin thể hiện ở khả năng xử lý thông tin định tính. Đây là điều mà thế hệ máy tính hiện nay đang hướng tới. Máy tính ngày nay đã được sử dụng trong hầu hết các lĩnh vực và đã góp phần quan trọng vào việc thúc đẩy sự phát triển kinh tế, xã hội, khoa học kỹ thuật, … Máy tính ra đời nhằm phục vụ cho những mục đích nhất định của con người. Với tất cả sự xử lý của máy tính để lấy thông tin hữu ích và trong quá trình xử lí đó một vấn đề đặc biệt quan trọng là tìm kiếm thông tin với khối lượng lớn, độ chính xác cao, thời gian nhanh nhất. Tìm kiếm thông tin thì bài toán đóng vai trò quan trọng là bài toán so mẫu, với mẫu có thể ở bất kỳ kiểu dữ liệu nào, từ văn bản đến các loại dữ liệu đa phương tiện khác (ảnh, video, âm thanh, …). Trên thực tế có rất nhiều ứng dụng tìm kiếm thông tin như: công cụ tìm kiếm của các hệ điều hành, khai phá web trên Internet, ... Để tìm kiếm thông tin thì cần phải xem thông tin đó lưu trữ dưới dạng dữ liệu nào? Dữ liệu được lưu trữ dưới nhiều dạng, song phổ biến nhất vẫn là dạng text nên chúng tôi chọn đề tài này cụ thể là tìm kiếm văn bản text. Tìm kiếm văn bản text nếu như những văn bản có khối lượng lớn thì có thể mất nhiều thời gian với những thuật toán kinh điển. Vậy đặt ra vấn đề tìm kiếm văn bản nhưng ở dạng nén sẽ nhanh hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 Nên chúng tôi đi vào làm cụ thể là tìm kiếm mẫu trong văn bản nén. Ngoài ra, văn bản nén cũng là văn bản mã hoá nhưng dung lượng giảm nhiều so với văn bản nguồn nên chúng tôi đi nghiên cứu mở rộng thêm văn bản mã hoá. Trong các bài toán tìm kiếm, để tìm kiếm nhanh đáp ứng được nhu cầu và không chỉ tìm kiếm cứng nhắc trong với từ khoá đưa ra. Người dùng mong muốn có thể tìm được cả những thông tin liên quan gợi ý cho người dùng. Vậy bài toán đó thì việc tìm kiếm theo hệ mờ là rất cần thiết. Vì vậy cần phải xây dựng các thuật toán mềm dẻo cho phép phát huy được sức mạnh của tìm kiếm mờ và đặc biệt cho phép sử dụng được nguồn tri thức giàu tính chuyên gia trong những tính huống tìm kiếm phức tạp. 2. Mục đích nghiên cứu Luận văn tập trung nghiên cứu về tiếp cận otomat mờ và xây dựng một số giải thuật tiếp cận otomat mờ để tìm kiếm mẫu của văn bản nén. 3. Đối tượng nghiên cứu - Tìm hiểu về otomát mờ. - Tìm hiểu về văn bản nén và mã hoá. - Cách so mẫu theo hướng tiếp cận otomát mờ. 4. Giả thuyết khoa học Nếu chúng ta sử dụng tiếp cận otomát mờ thì chúng ta không những tìm kiếm được những thông tin chính xác mong muốn mà còn tìm kiếm được những thông tin liên quan trong thời gian nhanh nhất, đáp ứng nhu cầu người dùng. 5. Nhiệm vụ nghiên cứu - Nghiên cứu về otomat mờ. - Nghiên cứu về nén và mã hoá. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 - Đưa ra các thuật toán tìm kiếm, các kết quả nghiên cứu trên. - Luận văn cũng mong muốn nêu ra được một số hướng nghiên cứu mở rộng về tìm kiếm mẫu theo hướng tiếp cận otomat mờ. 6. Phạm vi nghiên cứu Luận văn tập trung nghiên cứu các kiến thức có liên quan, các cơ sở lý thuyết: Hệ mờ, otomat mờ, các thuật toán tìm kiếm mẫu, các thuật toán tìm kiếm mẫu theo cách tiếp cận otomat mờ. 7. Phương pháp nghiên cứu Otomat mờ được xem là sự tổng quát hoá của otomat hữu hạn. Trong đó tập trạng thái là các tập mờ, hàm chuyển trạng thái và trạng thái kết thúc được biểu diễn qua các quan hệ mờ. Theo đánh giá của các chuyên gia, các hệ hình thức otomat mờ là mô hình toán học thích hợp với một số hệ thống quyết định, điều khiển, nhận dạng và đặc biệt được dùng trong đoán nhận mẫu. Tận dụng những ưu điểm trên và sự kết hợp với lý thuyết mờ, sử dụng một số hệ hình thức otomat mờ để giải bài toán so xâu mẫu. Để thấy rõ được tiếp cận otomat mờ chúng tôi chọn một bài toán cụ thể là tìm kiếm mẫu trong văn bản nén và mã hoá. Trong phạm vi luận văn, bài toán có thể làm với các tệp dữ liệu nén mà không cần giải nén toàn bộ. Ý tưởng cơ bản là đọc tuần tự trên tệp nén và mở nén một số mã nén, lưu kết quả giải nén cục bộ vào vùng đệm và áp dụng thuật toán theo tiếp cận mờ trên vùng đệm này. Nội dung luận văn gồm có phần mở đầu, 3 chương, phần kết luận, tài liệu tham khảo và phụ lục. Chương 1- Giới thiệu chung về vấn đề tìm kiếm văn bản, trọng tâm là bài toán so xâu mẫu. Hướng tiếp cận của luận văn cho bài toán so mẫu, chính xác và xấp xỉ, trên môi trường nén và mã hoá hoặc không sử dụng một số hệ hình thức otomat mờ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Chương 2 - Đưa ra ví dụ về bài toán so mẫu xấp xỉ và chính xác.... Chương 3- Giới thiệu một số thuật toán tìm kiếm mẫu trên môi trường văn bản nén và mã hoá. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Chương 1. TÌM KIẾM MẪU TRONG VĂN BẢN THEO CÁCH TIẾP CẬN OTOMAT MỜ 1.1. Tổng quan về tìm kiếm mẫu trên văn bản 1.1.1 Giới thiệu chung về vấn đề tìm kiếm văn bản Kiểu văn bản (Text) là dạng biểu diễn dữ liệu hay gặp nhất trong các hệ thống thông tin. Tìm kiếm văn bản (text searching) là vấn đề chủ yếu thuộc lĩnh vực quản lý văn bản. Một dạng cơ bản và tổng quát hơn là tìm kiếm chuỗi (hay xâu) (String searching) hay đối sánh chuỗi (string matching). Khái niệm “chuỗi” ở đây khá rộng, có thể là chuỗi văn bản gồm một dãy các chữ, số và ký tự đặc biệt, có thể là chuỗi nhị phân hay chuỗi gene,… Tìm kiếm chuỗi là bài toán tìm ra một mẫu (pattern) với một số đặc tính nào đó trong chuỗi các ký hiệu cho trước, vì thế bài toán này còn được gọi là so xâu mẫu hay có thể gọi ngắn gọn là so mẫu (string pattren matching). Dạng đơn giản nhất là tìm sự xuất hiện một xâu cho trước trong một chuỗi (còn gọi là xâu đích). Thực ra, đây là một trong những bài toán kinh điển nhất và phổ dụng nhất của khoa học máy tính, bởi hầu hết các ứng dụng đều có sự đối sánh chuỗi ở một dạng nào đó. Các phương pháp tìm kiếm văn bản và tìm kiếm chuỗi chính là cốt lõi trong rất nhiều loại phần mềm khác nhau như: các tiện ích của hệ điều hành, các hệ thống trích rút dữ liệu (data retrieval system), trình soạn thảo văn bản (text editors), máy tìm kiếm (search engine) trên internet, phân tích và tìm kiếm chuỗi gene trong sinh vật học, xử lý ngôn ngữ tự nhiên, tìm kiếm text trong các hệ cơ sở dữ liệu,… Thời gian gần đây, vấn đề đối sánh chuỗi càng trở nên quan trọng và được quan tâm nhiều do sự tăng trưởng nhanh chóng của các hệ thống Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 trích rút thông tin và các hệ thống sinh- tin học. Một lý do nữa, bởi con người ngày nay không chỉ đối mặt với một lượng thông tin khổng lồ mà còn đòi hỏi những yêu cầu tìm kiếm ngày càng phức tạp. Các mẫu đưa vào không chỉ đơn thuần là một xâu ký tự mà còn có thể chứa các ký tự thay thế (wild card), các khoảng trống (gaps) và các biểu thức chính quy (regular expresions). Sự “tìm thấy” không đơn giản là xuất hiện chính xác mẫu mà còn cho phép có “một ít sai khác” giữa mẫu và xuất hiện của nó trong văn bản. Từ đó, bên cạnh vấn đề kinh điển là “tìm kiếm chính xác”, nảy sinh một hướng nghiên cứu hết sức thú vị đó là “tìm kiếm xấp xỉ” (approximate matching, approximate searching). Cho đến nay, đã có nhiều hướng tiếp cận giải các bài toán so mẫu được đưa ra, từ những phương án rất lý thuyết đến các phương án rất thực dụng. Hướng nghiên cứu lý thuyết đã nêu ra nhiều thuật toán quan trọng, song lại chưa đạt hiệu quả cao trong thực hành, nếu không tận dụng được những khả năng trong đặc điểm của kiến trúc máy tính. Hiện nay, tiêu biểu cho những thuật toán mang tính chất thực hành theo hướng nâng cao khả năng tận dụng kiến trúc máy tính là tiếp cận song song bit (bit- parallelism) 1, 2, 3. Có thể phân các loại thuật toán so mẫu theo 2 hướng. Thứ nhất là các thuật toán trực tuyến (on-line), trong đó chỉ mẫu được tiền xử lý (thường sử dụng otomat hoặc dựa trên các đặc tính kết hợp trên xâu), còn văn bản thì không. Thứ hai là giải pháp tiền xử lý văn bản theo cách xây dựng một cấu trúc dữ liệu trên văn bản (lập chỉ mục). Nhiều ứng dụng cần sử dụng giải pháp này mặc dù đã có những thuật toán trực tuyến nhanh bởi chúng cần phải điều khiển một lượng văn bản quá lớn nên không có thuật toán trực tuyến nào có thể thực hiện một cách hiệu quả. Tìm kiếm trên chỉ mục thực ra cũng dựa trên tìm kiếm on-line. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 1.1.2. Các dạng tìm kiếm và các kết quả nghiên cứu Phân loại các thuật toán tìm kiếm dựa trên các đặc tính của mẫu ta có các dạng: tìm đơn mẫu, tìm đa mẫu (mẫu là tập các xâu), tìm mẫu mở rộng (extended strings), tìm biểu thức chính qui (regular expressions) với hai hướng tiếp cận là tìm kiếm chính xác và xấp xỉ. Nội dung của luận văn chỉ tập trung giải quyết vấn đề để tìm đơn mẫu, chính xác và xấp xỉ. 1.1.2.1. Tìm đơn mẫu Bài toán 1.1: Cho xâu mẫu P dộ dài m, P = P1 P2… Pm , và xâu độ dài n, S = S1 S 2… Sn (S thường dài, là một văn bản) trên cùng một bảng chữ A. Tìm tất cả các xuất hiện của xâu P trong S. Trong các thuật toán so mẫu thường sử dụng các khái niệm: Khúc đầu, khúc cuối, khúc con hay xâu con của một xâu, được định nghĩa như sau: Cho 3 xâu x, y, z. Ta nói x là khúc đầu (prefix) của xâu xy, là khúc cuối (suffix) của xâu yx và là khúc con hay xâu con (factor) của xâu yxz. Thuật toán “thô” nhất và đã được sử dụng rộng rãi là Brute- Force. Phương pháp này đơn giản chỉ là lần lượt bắt đầu từ vị trí trong S để đối sánh với mẫu P. Mặc dù có tốc độ chậm, thời gian xấu nhất tỉ lệ với tích m.n, song trong nhiều ứng dụng thực tế các chuỗi phát sinh ra thường có thời gian xử lý thực sự luôn tỷ lệ với m + n. Ngoài ra, một ưu điểm khác là nó thích hợp với cấu trúc của hầu hết các hệ máy tính. Cho đến nay, rất nhiều thuật toán so đơn mẫu được đưa ra 4 5, 2, trong đó kinh điển nhất là KMP. Có thể xem như có ba tiếp cận chung cho các thuật toán so mẫu, phụ thuộc vào cách duyệt tìm mẫu trong văn bản. Việc đánh giá tốc độ của các thuật toán dựa trên kích cỡ của mẫu P và bảng chữ A. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 Trong tiếp cận thứ nhất, lần lượt từng ký tự của văn bản S được đọc và tại mỗi vị trí, sau khi đối sánh với một ký tự của mẫu sẽ cập nhật sự thay đổi để nhận ra một khả năng xuất hiện mẫu. Hai thuật toán điển hình theo tiếp cận này là KMP và Shift - Or. Tiếp cận thứ hai sử dụng một “cửa sổ trượt” trên xâu S và tìm kiếm mẫu trong cửa sổ này. Tại mỗi vị trí trong cửa sổ, cần tìm một khúc cuối của cửa sổ mà là khúc cuối của xâu mẫu P. Thuật toán BM là một điển hình cho tiếp cận này và một biến thể đơn giản hoá của nó là Horspool. Tiếp cận thứ ba mới xuất hiện gần đây cho ra đời các thuật toán hiệu quả về thực hành đối với mẫu P đủ dài. Cũng tương tự như tiếp cận thứ hai, song tại mỗi thời điểm sẽ tìm khúc cuối dài nhất của cửa sổ mà là khúc con của mẫu. Thuật toán đầu tiên theo tiếp cận này là BDM và khi P đủ ngắn, một phiên bản đơn giản hơn, hiệu quả hơn là BNDM. Với những mẫu dài, thuật toán BOM được đánh giá là nhanh nhất 2. 1.1.2.2. Tìm đa mẫu Bài toán 1.2: Cho một mẫu P gồm tập các từ khoá w 1 , w 2 ,….,w k và xâu vào S = S 1 S 2 …S n trên cùng bảng chữ A. Tìm sự xuất hiện của các từ khoá w i trong S. Một cách đơn giản để tìm nhiều từ khoá trong một xâu đích là sử dụng thuật toán so đơn mẫu nhanh nhất đối với mỗi từ khoá. Rõ ràng phương pháp này không hiệu quả khi số lượng từ khoá lớn. Cả ba tiếp cận tìm đơn mẫu ở trên đều được mở rộng cho tìm đa mẫu. Hai điển hình theo tiếp cận thứ nhất là thuật toán nổi tiếng AhoCorasisk 4, có tốc độ cải thiện đáng kể khi số từ khoá nhiều và thuật Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 toán Multiple Shift- And, được sử dụng hiệu quả khi tổng độ dài của mẫu P rất nhỏ 2. Theo tiếp cận thứ hai có thuật toán nổi tiếng Commentz - Walter 4, trong đó kết hợp ý tưởng của Boyer - Moore và Aho- Corasisk , nhanh về lý thuyết, song lại không hiệu quả trong thực hành [2]. Một mở rộng của thuật toán Horspool là Set Horspool. Cuối cùng là thuật toán Wu-Manber, một phương pháp pha trộn giữa tiếp cận tìm kiếm hậu tố (suffix search approach) và một kiểu hàm băm, được đánh giá là nhanh trong thực hành. Trong tiếp cận thứ ba đã có những mở rộng từ thuật toán BOM và SBOM; tương tự với Shift- Or BNDM là Multiple BNDM 2. 1.1.2.3. Tìm mẫu mở rộng Trong nhiều ứng dụng, tìm kiếm mẫu không chỉ đơn giản là dãy các ký tự. Sau đây là một số mở rộng thường thấy trong các ứng dụng: Mở rộng đơn giản nhất cho phép mẫu là một dãy các lớp hay các tập ký tự, giả sử được đánh số thứ tự là 1,2,…,m. Bất kỳ ký tự nào trong lớp thứ i cũng có thể được xem là ký tự thứ i của mẫu. Mở rộng thứ hai là giới hạn khoảng trên độ dài: Một số vị trí trên mẫu được ấn định để khớp với một dãy văn bản nào đó có độ dài nằm trong một khoảng xác định trước. Điều này thường được sử dụng trong các ứng dụng sinh- tin học, chẳng hạn tìm mẫu PROSITE. Mở rộng thứ ba sử dụng các ký tự tùy chọn và ký tự lặp. Trong xuất hiện của mẫu trên văn bản, các ký tự tuỳ chọn có thể có hoặc không có, còn các ký tự lặp có thể có một hoặc lặp nhiều lần. Các vấn đề nảy sinh từ ba hướng mở rộng trên và những kết hợp từ ba hướng này được giải quyết bằng cách điều chỉnh lại thuật toán Shift Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Or và BNDM, trong đó có sử dụng cơ chế song song bit để mô phỏng otomat đa định, cho phép tìm tất cả các xuất hiện của mẫu. 1.1.2.4. Tìm kiếm xấp xỉ 1.1.2.4.1. Phát biểu bài toán Tìm kiếm xấp xỉ là bài toán tìm sự xuất hiện của một mẫu trong văn bản, trong đó sự “khớp” giữa mẫu và xuất hiện của nó có thể chấp nhận k “lỗi” (k là một giới hạn cho trước). Có thể kể ra một vài kiểu “lỗi”, như những lỗi đánh máy hay lỗi chính tả trong hệ thống trích rút thông tin, những sự biến đổi chuỗi gen hay các lỗi đo đạc trong sinh- tin học và những lỗi truyền dữ liệu trong các hệ thống xử lý tín hiệu,… Vì trong các hệ thống tin học khó có thể tránh được các “lỗi” nên vấn đề tìm kiếm xấp xỉ càng trở nên quan trọng. Đặc biệt, khi sử dụng các hệ thống trích rút thông tin, người dùng ngày nay còn đòi hỏi cả những kết quả gần giống hoặc có được kết quả phù hợp trả về nếu có sự sai sót trong mẫu hay văn bản. Trong trường hợp này “lỗi” có thể do nhiều nguyên nhân khác nhau, có thể kể ra như sau: - Câu truy vấn sai chính tả, xâu tìm kiếm không đúng cú pháp so với văn bản. - Lỗi in ấn, sai lỗi chính tả, sử dụng dấu chấm sai,… - Do sự biến đổi hình thái từ trong một số ngôn ngữ. - Dữ liệu đưa vào cơ sở dữ liệu không chính xác, thường xảy ra với tên người, địa chỉ… - Thông tin người tìm đưa vào không chính xác, chỉ “đại loại”. Vì vậy, một vấn đề đặt ra cho các hệ thống trích rút thông tin ngày nay là đáp ứng được nhu cầu tìm kiếm “mềm dẻo” này của người sử dụng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 Bài toán so mẫu xấp xỉ tổng quát được phát biểu như sau: Bài toán 1.3. Cho văn bản T độ dài n và xâu mẫu P độ dài m trên cùng một bảng chữ A. Tìm các vị trí trong văn bản khớp với mẫu, cho phép nhiều nhất k lỗi. 1.1.2.4.2. Các tiếp cận tìm kiếm xấp xỉ Trong 2, tác giả chia các thuật toán tìm kiếm xấp xỉ hiện nay ra thành 4 loại. 1) Các thuật toán dựa trên quy hoạch động: Đây là tiếp cận xuất hiện đầu tiên và đã được dùng để tính khoảng cách soạn thảo (Edit Distance) (như trong 4). 2) Các thuật toán sử dụng otomat tìm kiếm: Trước tiên xây dựng một hàm của mẫu P và số lỗi k, sau đó tạo otomat đa định hữu hạn (như trong 9, 1). Đây là hướng tiếp cận được quan tâm nhiều vì có độ phức tạp thời gian trong trường hợp xấu nhất là O(n) (tuy nhiên đòi hỏi độ phức tạp không gian lớn hơn). 3) Các thuật toán sử dụng cơ chế song song bit (bit- parallelism): cách tiếp cận này cho ra rất nhiều thuật toán hiệu quả nhờ khai thác bản chất song song của các phép toán bit trên một từ máy trong bộ vi xử lý. Nói chung song song bit được dùng để song song hoá các kỹ thuật khác, như tạo otomat đa định, lập ma trận quy hoạch động. Nói chung kỹ thuật này làm việc khá tốt với mẫu ngắn và tăng tốc đáng kể so với những cài đặt không tận dụng khả năng song song của thanh ghi. Trong 2 các tác giả cũng chỉ ra một số thuật toán dùng cơ chế song song bit là BPR và BPD để tái tạo một otomat đa định hữu hạn và BDM để tái tạo các thuật toán quy hoạch động. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11