Luận văn Bộ công cụ tìm kiếm thông tin trên mạng

MỤC LỤC LỜI MỞ ĐẦU................................................................................................4 PHẦN I: MỞ ĐẦU........................................................................................6 Tính cấp thiết của luận văn.....................................................................6 Mục đích, nhiệm vụ của luận văn...........................................................7 Mục đích của luận văn............................................................................7 Nhiệm vụ của luận văn............................................................................7 Phạm vi nghiên cứu..................................................................................7 Nội dung luận văn....................................................................................8 PHẦN II: NỘI DUNG..................................................................................9 CHƯƠNG I: GIỚI THIỆU BỘ CÔNG CỤ TÌM KIẾM THÔNG TIN.......9 1.1 Khái niệm bộ công cụ tìm kiếm thông tin............................................9 1.2 Bộ công cụ tìm kiếm thông tin trên mạng..........................................13 1.3 Mô hình bộ công cụ tìm kiếm thông tin truyền thống......................18 1.4 cấu trúc dữ liệu trong tổ chức và tìm kiếm thông tin.......................20 1.4.1 Bảng băm.............................................................................................20 1.4.1.1 Khái niệm hàm băm........................................................................20 1.4.1.2 Khái niệm bảng băm......................................................................22 1.4.1.3 Giải quyết xung đột........................................................................23 1.4.2 Cây cân bằng nhiều đường B - Tree..................................................27 1.4.2.1 Định nghĩa cây B - Trees................................................................27 1.4.2.2 Cây B* - Tree.................................................................................29 1.4.2.3 Cây B+ - Tree..................................................................................29 1.4.2.4 Cây BLink – Trees.............................................................................31 1.4.2.5 Lựa chọn phương pháp dữ liệu tần số.............................................32 CHƯƠNG II: CÁC CÔNG CỤ TÌM KIẾM CƠ BẢN.............33 2.1 Thu hồi trang Web................................................................................33 2.1.1 Web Crawler.......................................................................................33 2.1.2 Chọn lựa các trang.............................................................................34 2.2 Lưu trữ...............................................................................................38 2.2.1 Sự phân tán trang theo các nút............................................................39 2.2.2 Các phương pháp tổ chức trang vật lý.................................................40 2.2.3 Các chiến thuật cập nhật......................................................................40 2.3 Lập chỉ mục........................................................................................43 Cấu trúc của bảng chỉ mục.................................................................45 Một số thách thức................................................................................46 2.3.3 Chia bảng chỉ mục................................................................................46 2.4 Sắp xếp và phân tích liên kết............................................................48 2.4.1 Phương pháp PageRank.......................................................................49 2.4.2 Phương pháp HIST..............................................................................54 CHƯƠNG III: THIẾT KẾ CÁC CÔNG CỤ TÌM KIẾM THÔNG TIN TRÊN MẠNG...............................................................................................61 Mô đun lập chỉ mục..............................................................................62 3.1.1 Khái niệm chỉ mục................................................................................62 Các cấu trúc lưu chỉ mục....................................................................62 Các bước xây dựng chỉ mục theo phương pháp Inverted files............68 3.1.4 Lập chỉ mục với nguồn dữ liệu đầu vào...............................................76 Mô đun tìm kiếm..................................................................................77 Các dạng truy vấn...............................................................................80 Phân tích cú pháp truy vấn.................................................................81 3.2.3 Các phương pháp giải quyết vấn đề....................................................83 Mô đun sắp xếp....................................................................................82 Các mô hình sắp xếp và đánh giá........................................................82 Mô hình Boolean.................................................................................83 Mô hình không gian vector.................................................................84 PHẦN III: KẾT LUẬN...............................................................................90 Kết quả đạt được trong luận văn.......................................................90 Hướng phát triển trong tương lai......................................................91 TÀI LIỆU THAM KHẢO..........................................................................94 PHỤ LỤC.....................................................................................................98 DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ TIẾNG ANH Thuật ngữ tiếng anh Tiếng Việt Viết tắt CONTENT INDEX Chỉ mục nội dung CRAWLER Bộ thu hồi COLLECTION ANALYSIS MODULE Mô đun phân tích tập hợp MATCHING PROCESS Quá trình đối sánh FULL - TEXT INDEX Chỉ mục toàn văn bản HASHING SCHEME Sơ đồ băm REVLEVANCE Mức độ liên quan INDEX Bảng chỉ mục INVERTED FILE Tập tin đảo INVERTED INDEX Chỉ mục ngược INFORMATION RETRIEVAL Hệ thống tìm kiếm IR PAGERANK STRUCTURE INDEX Cấu trúc bảng chỉ mục S EARCH ENGINE Hệ tìm kiếm SIGNATURE FILE STANDFORD WEBBSE QUERY FORMULATION PROCESS Biểu diễn truy vấn QUERY ENGINE Công cụ truy vấn Uniform Resource Location Địa chỉ một trạm trên Internet URL USER Người sử dụng UTILYTI INDEX Bảng chỉ mục tiện ích WEB CRAWLER Bộ thu hồi DANH MỤC CÁC HÌNH VẼ Hình 1: Quy trình tìm kiếm thông tin Hình 2: Bộ công cụ tìm kiếm trang Wed Hình 3: Mô hình bộ công cụ tìm kiếm truyền thống Hình 4: Cấu trúc bảng băm Hình 5: Giải thuật tìm kiếm và chèn một khóa vào bảng băm Hình 6: Cấu trúc cây B- tree Hình 7: Cấu trúc cây B+ - Tree Hình 9: Kiến trúc cây lưu trữ Hình 10: Mô hình lập chỉ mục Web Hình 11: Minh họa các giá trị PageRank Hình 12: Thuật toán HITS Hình 13: Mô hình tạo nhã với mỗi khối Lôgíc Hình 14: Cấu trúc File dạng SSF Hình 15: Inverted File sử dụng mảng sắp xếp Hình 16: Khái quát mô hình lập chỉ mục Hình 17: Mô hình bộ phân tích Hình 18: Cấu trúc bộ đệm chỉ mục LỜI MỞ ĐẦU Trong xã hội phát triển thông tin thực sự trở thành nguồn tài nguyên quan trọng, nguồn của cải to lớn của xã hội. Các mối quan hệ, tính trật tự của tổ chức là những thuộc tính căn bản của mọi hệ thống kinh tế - xã hội. Hệ thống càng phát triển tức là càng có nhiều yếu tố tạo thành mối quan hệ giữa chúng càng phức tạp do đó lượng thông tin càng phong phú. Chính vì vậy mà ngày nay cùng với sự phát triển của Công nghệ Thông tin cũng như sự phát triển nhanh chóng của mạng máy tính toàn cầu và sự bùng nổ thông tin, các kho dữ liệu số đã được hình thành ở khắp mọi nơi và không ngừng gia tăng về dung lượng, nhưng thông tin thì vẫn luôn là cần thiết thậm chí thiếu với họ. Các kho dữ liệu này ẩn chứa một hàm lượng thông tin vô cùng lớn. Nhưng vấn đề đặt ra là làm thế nào để “khai thác, tìm kiếm” tổng hợp kho thông tin đó để cho nó trở nên hiệu quả và có giá trị đối với người dùng. Những thông tin này được lưu trữ và biểu diễn ở rất nhiều dạng khác nhau như văn bản, âm thanh, hình ảnh vv... có thể nói : “khối lượng dữ liệu khổng lồ mà người sử dụng có thể truy xuất nếu không được tổ chức lưu trữ tốt và kèm theo một phương thức xử lý hiệu quả để có thể khai thác và tìm kiếm lượng thông tin trong đó thì chúng cũng chỉ là những thông tin chết chứ không mang lại chút lợi ích nào cả ”. Để giải quyết vấn đề này, người ta đã xây dựng các hệ thống tìm kiếm thông tin. Nó giúp con người tìm kiếm và chọn lọc ra những tài liệu có chứa thông tin cần thiết. Do người sử dụng luôn yêu cầu kết quả tìm kiếm chính xác, đầy đủ và với các vận tốc tìm kiếm nhanh nên các hệ thống tìm kiếm thông tin luôn được nghiên cứu và phát triển cùng với các kỹ thuật, thuật toán tìm kiếm hiệu quả và tối ưu nhất. Luận văn “Bộ công cụ tìm kiếm thông tin trên mạng ” không đặt mục tiêu chính là xây dựng một hệ thống hoàn chỉnh, mà trình bày phần lý thuyết để đảm bảo cho một hệ thống tìm kiếm. Với hy vọng là tìm hiểu các chiến thuật, thuật toán để tổ chức một bộ công cụ tìm kiếm tối ưu, đưa ra đáp ứng người dùng với thời gian ngắn nhất và các kết quả có độ liên quan tới truy vấn cao nhất và có nhiều lựa chọn để người dùng có thể can thiệp vào hệ thống. Để xây dựng được luận văn này em đã được sự quan tâm hướng dẫn chỉ bảo tận tình của PGS – TS KH Vũ Đình Hòa, cùng với sự giúp đỡ của bạn bè đã tạo điều kiện thuận lợi cho em được hoàn thành nhiệm vụ. Em xin trân thành cảm ơn sự giúp đỡ quý báu này. Hà Nội, ngày tháng năm 2006 Người thực hiện Bùi Thị Minh Tuyết PHẦN I : MỞ ĐẦU 1.Tính cấp thiết của luận văn: Ngày nay, do nhu cầu học tập, giải trí, trao đổi thông tin của con người là rất lớn. Để đáp ứng nhu cầu đó thì con người đã đạt được những tiến bộ công nghệ cùng với sự phát triển của những lý thuyết trong lĩnh vực xử lý thông tin đã giải quyết được phần nào các vấn đề đặt ra. Chẳng hạn, như các bài toán trong xử lý văn bản như tìm kiếm, phân lớp, phân cụm văn bản, vv... Information retrieval (IR) là một trong vấn đề quan tâm hiện nay. Nghiên cứu về vấn đề IR có rất nhiều khó khăn, bởi ngay cả với những hệ tìm kiếm nổi tiếng mà chúng ta thấy thường xuyên trên mạng Internet như Gooogle, Altaarista, Yahoo,... là các hệ tìm kiếm tự động nhưng vai trò của người dùng rất hạn chế, các hạn chế tiêu biểu thường gặp có thể được liệt kê ra như sau: Khi người sử dụng đưa ra một vấn đề truy vấn, thì hệ thống sẽ trả ra kết quả thường là hàng nghìn tài liệu hoặc thậm trí là lớn hơn rất nhiều, khi đó người sử dụng sẽ phải mất thời gian đọc nội dung của từng loại tài liệu để tìm kiếm thông tin mà mình quan tâm và đặc biệt người sử dụng không thể can thiệp để có thể tìm kiếm tài liệu theo ý muốn của mình. Một bài toán khác trong tìm kiếm thông tin - Vấn đề sắp xếp các tài liệu theo độ liên quan (Relevancy ranking) cũng là một vấn đề đang được quan tâm và phát triển. Đặc biệt trong những năm gần đây cùng với sự gia tăng của các nguồn thông tin điện tử sẵn dùng đã dẫn đến việc tìm kiếm tài liệu phù hợp nhất trong tập tài liệu nguồn ngày càng trở nên khó khăn đối với con người và máy tính. 2. Mục đích , nhiệm vụ của luận văn 2.1. Mục đích của luận văn: Luận văn tập chung nghiên cứu các mô hình tìm kiếm thông tin truyền thống và mô hình tìm kiếm thông tin trên mạng bên cạnh đó cũng tập chung nghiên cứu và phân tích các đặc tính cấu trúc chung của một mô hình tìm kiếm thông tin dựa trên cơ sở lý thuyết. 2.2. Nhiệm vụ của luận văn: Luận văn phải thực hiện được các nhiệm vụ sau: 2.2.1.Nghiên cứu về bộ công cụ tìm kiếm thông tin . 2.2.2.Nghiên cứu các mô hình bộ công cụ tìm kiếm thông tin truyền thống. 2.2.3.Nghiên cứu các mô hình bộ công cụ tìm kiếm thông tin trên mạng. 3. Phạm vi nghiên cứu Kết quả đề tài là bước đầu nghiên cứu, tổng hợp các vấn đề lý thuyết tron bài toán “Bộ công cụ tìm kiếm thông tin trên mạng”. Dựa vào mô hình lý thuyết để tiến hành cài đặt một số chức năng hỗ trợ cho việc thiết kế bộ công cụ tìm kiếm trên mạng. 4. Nội dung luận văn : Luận văn gồm 3 chương CHƯƠNG 1: GIỚI THIỆU BỘ CÔNG CỤ TÌM KIẾM THÔNG TIN Gồm các nội dung sau : Kh¸i niÖm bé c«ng cô t×m kiÕm th«ng tin M« h×nh bé c«ng cô t×m kiÕm th«ng tin truyÒn thèng M« h×nh bé c«ng cô t×m kiÕm th«ng tin trªn m¹ng CÊu tróc d÷ liÖu trong tæ chøc l­u tr÷ vµ t×m kiÕm th«ng tin CHƯƠNG 2: CÁC CÔNG CỤ CƠ BẢN Gồm các nội dung sau : 1. Thu håi trang Web 2. L­u tr÷ 3. LËp chØ môc 4. S¾p xÕp vµ ph©n tÝch liªn kÕt CHƯƠNG 3 :THIẾT KẾ CÁC CÔNG CỤ HỖ TRỢ TÌM KIẾM THÔNG TIN TRÊN MẠNG Gồm các nội dung sau : M«®ul t×m kiÕm 2. M«®un s¾p xÕp 3. M«®ul lËp chØ môc PHẦN II: NỘI DUNG CHƯƠNG I GIỚI THIỆU BỘ CÔNG CỤ TÌM KIẾM THÔNG TIN Khái niệm bộ công cụ tìm kiếm thông tin Thuật ngữ tìm kiếm thông tin xuất hiện từ khá sớm, các thông tin thể hiện ở nhiều dạng khác nhau, có thể là dạng văn bản, âm thanh hoặc hình ảnh,vv... Mà phổ biến nhất là tìm kiếm văn bản (bao gồm việc tìm kiếm hoặc sắp xếp văn bản), đặc biệt là trong các công cụ tìm kiếm. Nhiều lúc, thuật ngữ này được dùng như là toàn bộ quá trình từ việc xử lý văn bản tới việc phân lớp và tìm kiếm văn bản. Với đề tài này, em sử dụng thuật ngữ tìm kiếm văn bản theo nghĩa bao gồm việc lập chỉ mục tài liệu, tìm kiếm và sắp xếp các văn bản tìm kiếm theo thứ tự liên quan đến yêu cầu người sử dụng (văn bản ở đây có thể là một File hoặc là một trang Web) . Một hệ thống tìm kiếm thông tin là một chương trình phần mềm dùng để lưu trữ và quản lý thông tin nằm trong các tài liệu. Hệ thống này giúp người sử dụng tìm kiếm thông tin mà họ quan tâm. Các hệ thống này không giống như các hệ thống trả lời câu hỏi, nó chỉ ra sự tồn tại và vị trí các tài liệu có chứa thông tin cần thiết. Một số tài liệu “tìm kiếm được” thỏa mãn yêu cầu của người sử dụng gọi là các tài liệu phù hợp hay tài liệu liên quan (relevanl document). Một hệ thống tìm kiếm hoàn hảo sẽ chỉ tìm và đưa ra các tài liệu liên quan mà không đưa ra các tài liệu không liên quan. Tuy nhiên các hệ thống này không tồn tại bởi các thể hiện tìm kiếm là không đầy đủ mà mức độ liên quan phụ thuộc vào quan điểm chủ quan của từng người. Hai người sử dụng có thể đưa ra cùng một truy vấn với một hệ thống tìm kiếm thông tin và sau đó sẽ có những đánh giá khác nhau về mức độ liên quan trên các tài liệu đã tìm được. Tìm kiếm trên các thông tin nói chung giải quyết các vấn đề như biểu diễn, lưu trữ, tổ chức và truy cập đến các mục thông tin. Việc tổ chức và biểu diễn thông tin giúp người sử dụng dễ dàng truy cập thông tin mà mình quan tâm. Nhưng để mô tả đặc điểm thông tin yêu cầu của người sử dụng không phải dễ dàng. Vì thế, hệ thống tìm kiếm thông tin bao gồm ba quá trình cơ bản sau: Biểu diễn nội dung các tài liệu, biểu diễn yêu cầu của người sử dụng và so sánh hai biểu diễn này. Bµi to¸n th«ng tin V¨n b¶n BiÓu diÔn Truy vÊn V¨n b¶n ®· chØ sè ho¸ So s¸nh BiÓu diÔn C¸c v¨n b¶n ®­îc t×m kiÕm Ph¶n håi H×nh 1: Quy tr×nh t×m kiÕm th«ng tin Quá trình biểu diễn tài liệu được gọi là quá trình chỉ số hóa (indexing). Quá trình này có thể lưu trữ thực sự các tài liệu trong hệ thống, thông thường chỉ lưu trữ một phần tài liệu, chẳng hạn như phần tiêu đề và tóm tắt. Quá trình biểu diễn yêu cầu người sử dụng gọi là quá trình biểu diễn truy vấn (query formulation process). Truy vấn biểu thị sự tương tác giữa hệ thống và người sử dụng, do đó quá trình này không chỉ đưa ra một truy vấn phù hợp mà còn phải thể hiện được sự hiểu biết về yêu cầu của người sử dụng. Sự thiết lập tự động các truy vấn liên tiếp được gọi là phản hồi độ liên quan (relevance feedback). Việc so sánh truy vấn với tài liệu cũng được gọi là quá trình đối sánh (matching process) và cho kết quả là một danh sách các tài liệu được sắp xếp theo mức độ liên quan tới truy vấn. Vậy, để mô tả thông tin một cách rõ ràng đầy đủ, người sử dụng không thể trực tiếp yêu cầu thông tin sử dụng các giao diện hiện thời của hệ thống tìm kiếm. Thay vì người sử dụng đầu tiên phải chuyển đổi thông tin yêu cầu này thành một truy vấn mà có thể được xử lý bởi hệ thống tìm kiếm (hoặc hệ thống IR). Thường thì phép chuyển đổi này tạo ra một tập hợp các từ khóa (hoặc các term chỉ số) mô tả khái quát yêu cầu của người sử dụng. cho một truy vấn người dùng, mục đích chính của một hệ thống IR là tìm kiếm thông tin mà có thể trở thành hữu ích hoặc phù hợp với người sử dụng. Điều quan trọng nhất ở đây là việc phục hồi thông tin trái với phục hồi dữ liệu. Trong ngữ cảnh của hệ thống IR, nhiệm vụ của phục hồi dữ liệu chính là việc xác định các tài liệu chứa các từ khóa xuất hiện thường xuyên nhất trong truy vấn người dùng mà không cần thỏa mãn yêu cầu của người dùng. Trong thực tế, người sử dụng của một hệ thống IR quan tâm nhiều đến việc khôi phục thông tin về một chủ đề hơn là việc khôi phục dữ liệu mà đáp ứng một truy vấn đưa ra. Một ngôn ngữ phục hồi dữ liệu hướng vào việc khôi phục dữ liệu mà đáp ứng một truy vấn đưa ra. Một ngôn ngữ phục hồi dữ liệu hướng vào việc khôi phục tất cả các đối tượng thỏa mãn các điều kiện đã được xác định rõ ràng như một biểu thức chính tắc hoặc biểu thức đại số quan hệ. Do vậy, với một hệ thống khôi phục dữ liệu, một đối tượng đơn lẻ bị lỗi trong số hàng nghìn đối tượng được tìm kiếm là không thực hiện được. Tuy nhiên, với một hệ thống khôi phục thông tin, các đối tượng tìm kiếm có thể không chính xác và cho phép các lỗi nhỏ. Nguyên nhân chính của sự khác nhau này là việc khôi phục thông tin luôn xử lý với văn bản ngôn ngữ tự nhiên thường không có cấu trúc và không thể rõ nghĩa. Nói cách khác, hệ thống khôi phục dữ liệu (như một cơ sở dữ liệu quan hệ ) xử lý dữ liệu có cấu trúc và ngữ nghĩa đã được xác định. Việc khôi phục dữ liệu không giải quyết vấn đề trong khôi phục thông tin về một chủ đề hoặc một lĩnh vực cụ thể. Để đạt được hiệu quả đáp ứng thông tin yêu cầu của người dùng, hệ thống IR phải bằng cách nào “hiểu” được các nội dung của thông tin (các văn bản) trong một tập hợp và sắp xếp chúng theo mức độ phù hợp với truy vấn. Sự “hiểu biết” về nội dung văn bản này bao gồm sự trích chọn cú pháp và ngữ nghĩa thông tin từ văn bản và sử dụng thông tin này để so khớp với thông tin người dùng. Cái khó là không chỉ hiểu để trích chọn thông tin này như thế nào mà còn là hiểu cách sử dụng nó để quyết định mối liên quan như thế nào. Do vậy khái niệm mức độ liên quan (revlevance) cũng là một phần quan trọng trong tìm kiếm tất cả các tài liệu liên quan với một truy vấn người dùng mặc dù việc tìm kiếm có thể đưa ra một tài liệu không thích hợp. Vậy, khôi phục thông tin là một quá trình nhận dạng, xác định và chỉ ra các tài liệu liên quan dựa trên mô tả yêu cầu thông tin của người sử dụng. Việc tìm kiếm các tài liệu dựa trên nội dung thực sự của văn bản mà không phụ thuộc vào các từ khóa gắn với văn bản đó. Các công cụ văn bản nổi tiếng hiện nay như Google, Altaavista, Yohoo,... là những hệ tìm kiếm đưa ra danh sách các văn bản theo độ quan trọng của câu hỏi đưa vào, Để xây dựng một hệ tìm kiếm văn bản có hiệu quả cao, trước hết các văn bản và truy vấn ở dạng ngôn ngữ tự nhiên phải được tiền xử lý và chuẩn hóa. Một mô hình của quá trình thiết lập truy vấn được chuẩn hóa thành hai vấn đề: Đầu tiên là chọn các ternm truy vấn và thứ hai là lựa chọn các phép toán truy vấn. Dưới đây em đưa ra hai mô hình chi tiết cho bộ công cụ tìm kiếm thông tin truyền thống và bộ công cụ tìm kiếm thông tin trên mạng. 1.2 Bộ công cụ tìm kiếm thông tin trên mạng Do các trang Web phân tán trên mọi nơi nên việc đầu tiên là chúng ta phải thu thập tất cả các dữ liệu Web có liên quan tới truy vấn, lập chỉ mục, sau đó thực hiện tìm kiếm để đưa ra tập kết quả có liên quan tới nội dung truy vấn, trước khi được đưa tới người sử dụng cuối tập kết quả này phải được sắp xếp theo thứ tự độ liên quan. Trong phần này em đưa ra một mô hình tìm kiếm thông tin trên Web, một kho dữ liệu rất lớn với tỷ lệ thay đổi cao. Word – Wide – Web là kho thông tin khổng lồ của nó được quảng bá tới hàng tr