Các thuật toán đối sánh mẫu và ứng dụng tìm kiếm trên website.

- BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI PHẠM CÔNG HỒNG CÁC THUẬT TOÁN ĐỐI SÁNH MẪU VÀ ỨNG DỤNG TÌM KIẾM TRÊN WEBSITE LUẬN VĂN THẠC SĨ KỸ THUẬT TOÁN TIN Hà Nội – Năm 2014 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI PHẠM CÔNG HỒNG CÁC THUẬT TOÁN ĐỐI SÁNH MẪU VÀ ỨNG DỤNG TÌM KIẾM TRÊN WEBSITE Chuyên ngành: TOÁN TIN Mã đề tài: TOAN-VINH06 LUẬN VĂN THẠC SĨ KỸ THUẬT TOÁN TIN NGƯỜI HƯỚNG DẪN KHOA HỌC TIẾN SĨ: NGUYỄN THỊ THANH HUYỀN Hà Nội – Năm 2014 LỜI CẢM ƠN Trước hết em xin gửi lời cảm ơn chân thành đến toàn thể các thầy cô giáo Viện Toán ứng dụng và Tin học đã tận tình dạy dỗ chúng em trong suốt quá trình học tập tại Viện.
- Hà Nội, ngày 12 tháng 03 năm 2014 Phạm Công Hồng DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT Các ký hiệu ε Xâu rỗng wi Kí tự thứ i của xâu w Pi Kí tự thứ i của xâu P Sj Kí tự thứ j của xâu S Ci,j Là độ dài dãy con lớn nhất của hai dãy P1..i và S1..j Các chữ viết tắt CSDL Cơ sở dữ liệu DFA Otomat đơn định hữu hạn NFA Otomat đa định hữu hạn KMP Knuth–Morris–Pratt BM Boyer–Moore DANH MỤC CÁC HÌNH VẼ Hình 2.1.
- Sự thay đổi trạng thái mờ khi gặp kí tự b Hình 4.1.
- Mô hình lập trình của ứng dụng MỤC LỤC MỞ ĐẦU.
- 2 Chương 1: TỔNG QUAN VỀ VẤN ĐỀ ĐỐI SÁNH MẪU.
- Đối sánh mẫu.
- Bài toán đối sánh mẫu và tình hình nghiên cứu hiện nay.
- Các dạng của bài toán đối sánh mẫu.
- Đối sánh mẫu mở rộng.
- Đối sánh mẫu xấp xỉ.
- Phát biểu bài toán.
- Các tiếp cận giải bài toán đối sánh mẫu xấp xỉ.
- CÁC THUẬT TOÁN ĐỐI SÁNH MẪU CHÍNH XÁC.
- Thuật toán KMP ( Knuth- Morris- Pratt.
- Thuật toán BM ( Boyer- Moore.
- Thuật toán KMP mờ.
- 24 2.3.3 Thuật toán.
- ĐỐI SÁNH MẪU XẤP XỈ.
- 29 3.1 Vấn đề đối sánh mẫu xấp xỉ.
- 30 3.2.1 Phát biểu bài toán.
- 30 3.2.2 Otomat đối sánh mẫu: mô hình và cơ sở toán học.
- 31 3.2.3 Thuật toán.
- Đánh giá thuật toán.
- 40 3.3.1 Bài toán tìm dãy con chung dài nhất.
- 40 3.3.2 Thuật toán quy hoạch động.
- 40 3.3.3 Thuật toán quy hoạch động tìm dãy con chung dài nhất.
- SỬ DỤNG THUẬT TOÁN ĐỐI SÁNH MẪU TRONG TÌM KIẾM TRÊN WEBSITE.
- 46 4.2.2 Nền tảng ứng dụng.
- Kịch bản tìm kiếm.
- Kết quả tìm kiếm trên website.
- 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.
- Ngày nay số lượng thông tin cũng như kích thước của hệ thống tin càng ngày càng lớn, trong khi nhu cầu tìm kiếm của con người dùng đòi hỏi ngày càng cao và phức tạp.
- Để nâng cao tốc độ tìm kiếm và đáp ứng yêu cầu người dùng.
- Vậy việc nghiên cứu tìm hiểu các thuật toán đối sánh mẫu để ứng dụng trong công việc rất cần thiết.
- Để 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 tôi chọn đề tài này cụ thể Các thuật toán đối sánh mẫu và ứng dụng tìm kiếm trên website.
- Mục tiêu và nội dung Luận văn tập trung nghiên cứu các thuật toán đối sánh mẫu và ứng dụng tìm kiếm trên website.
- Tìm hiểu về vấn đề tìm kiếm thông tin và đối sánh mẫu - Nghiên cứu một số thuật toán đối sánh mẫu chính xác và xấp xỉ - Cài đặt một số thuật toán đối sánh mẫu và ứng dụng xây dựng tính năng tìm kiếm trên một website 2 3.
- 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: Tổng quan về vấn đề tìm kiếm, các thuật toán tìm kiếm mẫu theo cách tiếp cận quy hoạch động và otomat mờ.
- cài đặt thuật toán và ứng dụng tìm kiếm trên website http://truongthcsdaiminh.edu.vn/ Nội dung luận văn gồm 4 chương, phần kết luận, tài liệu tham khảo và phụ lục: Chương 1: Tổng quan về vấn đề đối sánh mẫu Giới thiệu chung về bài toán đối sánh mẫu (hay đối sánh mẫu), tập trung vào trường hợp mẫu là một xâu và nhắc lại một số khái niệm cơ sở có liên quan đến luận văn Chương 2: Các thuật toán đối sánh mẫu chính xác Chương này trình bày nội dung của một số thuật toán kinh điển về đối sánh mẫu chính xác về hai thuật KMP và BM Chương 3.
- Thuật toán đối sánh mẫu xấp xỉ Chương này trình bày các kết quả của luận văn về đối sánh mẫu xấp xỉ ứng dụng thuật toán kinh điển là thuật toán quy hoạch động để tìm dãy con chung lớn nhất giữa hai xâu Chương 4: Ứng dụng thuật toán đối sánh mẫu để tìm kiếm trên website 3 Chương 1: TỔNG QUAN VỀ VẤN ĐỀ ĐỐI SÁNH MẪU 1.1.
- Đối sánh mẫu Đối sánh mẫu, hay so mẫu (pattern matching), là một bài toán quan trọng được ứng dụng trong nhiều lĩnh vực khoa học và xử lý thông tin, ví dụ như: công cụ tìm kiếm của các hệ điều hành.
- tìm kiếm mẫu lặp trong nén dữ liệu.
- tìm kiếm thông tin trong thư viện điện tử, bách khoa toàn thư điện tử.
- tìm kiếm tương tự trong CSDL gen.
- tìm kiếm tự động các luật trong CSDL.
- Vấn đề đặt ra trong bài toán so xâu mẫu là cần phát hiện được sự xuất hiện của xâu mẫu trong một chuỗi (xâu) các kí hiệu cho trước (gọi là xâu đích, trong thực tế xâu đích có thể là một văn bản).
- Phụ thuộc vào đặc tính của mẫu, ta có thể phân thành bốn dạng bài toán cụ thể: so đơn mẫu, so đa mẫu, đối sánh mẫu mở rộng và so biểu thức chính qui.
- Dạng đơn giản nhất song phổ dụng nhất và cũng được quan tâm nhiều nhất là bài toán so đơn mẫu, với mẫu là một xâu (điều này được thể hiện bởi sự phong phú của các thuật toán so đơn mẫu).
- Khi mẫu là một tập các từ khoá, ta có bài toán so đa mẫu.
- Trong bài toán đối sánh mẫu mở rộng, mẫu không đơn giản là một dãy kí tự mà được mở rộng theo nhiều kiểu khác nhau.
- Cuối cùng, dạng tổng quát nhất bao hàm cho tất cả các loại bài toán kể trên là so biểu thức chính qui.
- Một vấn đề kinh điển khác của khoa học máy tính là tìm kiếm xấp xỉ, được đặt ra từ các ứng dụng nhận dạng tiếng nói, sinh–tin học, xử lý tín hiệu, so sánh 4 tệp.
- Ngày nay, việc xây dựng công cụ tìm kiếm hiệu quả, đặc biệt là tính năng tìm kiếm xấp xỉ, trong các hệ thống trích rút văn bản đang được rất nhiều người quan tâm.
- Nhu cầu tìm kiếm văn bản xấp xỉ thể hiện rõ nhất ở các ứng dụng như: thư viện điện tử, máy tìm kiếm (search engine) trên mạng.
- Cho đến nay đã có rất nhiều máy tìm kiếm trên Internet, www.bing.com, Yahoo (www.yahoo.com), Netscape (www.netscape.com.
- Còn trong các hệ quản trị cơ sở dữ liệu, khả năng tìm kiếm thông tin gần đúng duy nhất của truy vấn SQL là dùng toán tử “like”, cho phép tìm kiếm bản ghi phù hợp với thông tin đưa vào theo một khuôn dạng khá “cứng nhắc”, xâu mẫu chỉ chấp nhận hai loại kí tự thay thế cho một kí tự và một xâu kí tự.
- Vậy việc tiếp tục nghiên cứu về các giải pháp tìm kiếm xấp xỉ là cần thiết.
- Bài toán đối sánh mẫu và tình hình nghiên cứu hiện nay Đối sánh mẫu, hay so mẫu (pattern matching), là bài toán tìm sự xuất hiện của 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.
- 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.
- Dạng đơn giản nhất của bài toán đối sánh mẫu 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 đòi hỏi có sự đối sánh mẫu ở một dạng nào đó.
- Các phương pháp đối sánh mẫu 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 (search) của hệ điều hành Windows, các hệ thống trích rút dữ liệu, trình soạn thảo vãn bản, máy tìm kiếm (search engine) 5 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 mẫu 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 trích rút thông tin và các hệ thống sinh–tin học.
- Một lý do nữa, đó là vì 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 và các biểu thức chính qui.
- Từ đó nảy sinh một hướng nghiên cứu hết sức thú vị là "so xâu mẫu xấp xỉ" (approximate string matching) hiện nay đang được quan tâm rất nhiều và những dạng phức tạp khác của bài toán đối sánh mẫu là đối sánh mẫu mở rộng, so đa mẫu và so biểu thức chính qui.
- Các kết quả đạt được hiện nay về đối sánh mẫu chủ yếu tập trung vào trường hợp đơn giản nhất là tìm ra một xâu mẫu trong văn bản, còn với những dạng phức tạp khác, cho đến nay vẫn chưa có nhiều công trình được công bố.
- Tuy nhiên, ta có thể phân loại các thuật toán đối sánh mẫu theo hai 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à các thuật toán off–line, sử dụng 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).
- Mặc dù đã có những thuật toán trực tuyến nhanh, song với nhiều ứng dụng 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ả.
- Khi đó, giải pháp được lựa chọn là sử dụng các thuật toán off–line.
- Tìm kiếm trên chỉ mục thực ra cũng dựa trên tìm kiếm on–line.
- Các dạng của bài toán đối sánh mẫu Dựa trên đặc tính của mẫu, bài toán đối sánh mẫu được phân loại như sau: so đơn mẫu, so đa mẫu, đối sánh mẫu mở rộng, so biểu thức chính qui theo hai hướng chính xác và xấp xỉ.
- Nội dung của luận văn tập trung giải quyết bài toán so đơn mẫu, chính xác và xấp xỉ, mỗi khi nhắc đến đối sánh mẫu sẽ ngầm hiểu mẫu là một xâu kí tự.
- So đơn mẫu Bài toán 1.1.
- Trong các thuật toán đối sánh 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.
- Thuật toán đơn giản nhất là Brute–Force, cho phép tìm được tất cả các xuất hiện của mẫu trong thời gian cỡ O(m.n).
- Cho đến nay, rất nhiều thuật toán so đơn mẫu hiệu quả hơn được đưa ra, trong đó kinh điển nhất là KMP (do D.E.
- Dựa vào cách duyệt tìm mẫu trong văn bản, ta có thể xem như có ba tiếp cận chung cho các thuật toán đối sánh mẫu.
- 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à đối sánh mẫu trong cửa sổ này.
- 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à thuật toán 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.
- 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à thuật toán BNDM.
- Với những mẫu dài, thuật toán BOM được đánh giá là nhanh nhất Ngoài ba tiếp cận trên cũng có một vài thuật thoán khác, chẳng hạn các phương pháp dựa trên hàm băm, song chúng không hiệu quả lắm nên ít phổ dụng.
- So đa mẫu Bài toán 1.2.
- Một cách đơn giản để tìm nhiều từ khóa 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á.
- 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 Aho–Corasick, có tốc độ cải thiện đáng kể khi số từ khoá nhiều và thuật 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ỏ.
- Theo tiếp cận thứ hai có các thuật toán Commentz–Walter , Set Horspool, Wu–Manber,… Thuật toán Commemtz–Walter là sự kết hợp ý tưởng của Boyer– Moore và Aho–Corasick, còn Set Horspool là một mở rộng của thuật toán Horspool.
- Hiện nay, thuật toán Wu–Manber được đánh giá là nhanh trong thực hành, trong đó có sự 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.
- 8 Một số thuật toán theo tiếp cận thứ ba được mở rộng từ thuật toán BOM, SBOM và Shift–Or BNDM.
- Đối sánh mẫu mở rộng Trong nhiều ứng dụng, xâu mẫu được đưa vào để tìm kiếm không chỉ đơn giản là dãy các kí tự.
- Khi đó, 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.
- Kiểu mở rộng như vậ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.
- Theo hướng mở rộng thứ ba, mẫu bao gồm cả các kí tự tuỳ chọn và kí tự lặp.
- Trong một 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 lại 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ó thể được giải quyết bằng cách điều chỉnh lại thuật toán Shift–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.
- So biểu thức chính qui Biểu thức chính qui cung cấp một phương pháp mạnh để biểu diễn một tập các mẫu tìm kiếm, bao gồm tất cả các loại bài toán kể trên

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt