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

Chia sẻ: Pham Viet Hung | Ngày: | Loại File: DOC | Số trang:101

Thêm vào BST

Báo xấu

360
lượt xem 99
download

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

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 , đầ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ụ...

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 Bộ công cụ tìm kiếm thông tin trên mạng

 LUẬN VĂN Đề tài: Bộ công cụ tìm kiếm thông tin trên mạng Thành phố Hồ Chí Minh, tháng năm ….. 1
MỤC LỤC LỜI MỞ ĐẦU................................................................................................4 PHẦN I: MỞ ĐẦU........................................................................................6 1. Tính cấp thiết của luận văn.....................................................................6 2. 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 3. Phạm vi nghiên cứu..................................................................................7 4. 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 2
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 2.1.1 Cấu trúc của bảng chỉ mục.................................................................45 2.1.2 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 3.1 Mô đun lập chỉ mục..............................................................................62 3.1.1 Khái niệm chỉ mục................................................................................62 3.1.1 Các cấu trúc lưu chỉ mục....................................................................62 3.1.2 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 3.2 Mô đun tìm kiếm..................................................................................77 3
3.2.1 Các dạng truy vấn...............................................................................80 3.2.2 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 3.3 Mô đun sắp xếp....................................................................................82 Các mô hình sắp xếp và đánh giá........................................................82 1. Mô hình Boolean.................................................................................83 2. Mô hình không gian vector.................................................................84 PHẦN III: KẾT LUẬN...............................................................................90 1. Kết quả đạt được trong luận văn.......................................................90 2. Hướng phát triển trong tương lai......................................................91 TÀI LIỆU THAM KHẢO..........................................................................94 PHỤ LỤC.....................................................................................................98 4
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 Địa chỉ một trạm trên URL Uniform Resource Location Internet USER Người sử dụng UTILYTI INDEX Bảng chỉ mục tiện ích WEB CRAWLER Bộ thu hồi 5
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 6
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 7
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 8
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. 9
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 : 1. Kh¸i niÖm bé c«ng cô t×m kiÕm th«ng tin 10
3. M« h×nh bé c«ng cô t×m kiÕm th«ng tin truyÒn thèng 4. M« h×nh bé c«ng cô t×m kiÕm th«ng tin trªn m¹ng 5. CÊu tróc d÷ liÖu trong tæ chøc lu 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. Lu 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 : 1. M«®ul t×m kiÕm 2. M«®un s¾p xÕp 3. M«®ul lËp chØ môc 11
PHẦN II: NỘI DUNG CHƯƠNG I GIỚI THIỆU BỘ CÔNG CỤ TÌM KIẾM THÔNG TIN 1.1 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. 12
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 BiÓu diÔn Truy vÊn V¨n b¶n ®· chØ sè ho¸ So s¸nh C¸c v¨n b¶n ®îc Ph¶n håi t×m kiÕm H×nh 1: Quy tr×nh t×m kiÕm th«ng tin 13
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 14
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. 15
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 triệu người. Ta cũng có một vài trình duyệt Web đơn giản như Yahoo! Nhưng có rất nhiều người tìm kiếm thông tin lại thích sử dụng bộ công cụ tìm kiếm để bắt đầu trang Web của họ. Trong trường hợp này người 16
sử dụng đ ưa ra một truy vấn cụ thể là một vài từ khóa và nhận được một danh sách các trang Web có liên quan, đặc biệt là các trang chứa đựng các từ khóa đó. Ở phần này em sẽ trình bày một số phương pháp thiết kế tốt nhất cho bộ công cụ tìm kiếm và diễn tả một vài kỹ thuật phổ biến. Có nhiều công cụ sử dụng các thuật toán và các kỹ thuật thu hồi thông tin (information Retrieval - IR) truyền thống. Tuy nhiên các thuật toán IR được phát triển cho tập tài liệu nhỏ và không liên kết, ví dụ như tiêu đề của các bài báo, cuốn sách trong thư viện, trong khi đó Web lại là một khối dữ liệu cực kỳ lớn, thay đổi thường xuyên cộng với khả năng phân tán ở mọi nơi, điều đó đòi hỏi phải có một kỹ thuật mới hoặc là sự mở rộng của các kỹ thuật cũ để sao cho cấu trúc bảng chỉ mục (Index) của ta có thể thay đổi, cập nhật một cách dễ dàng tận dụng triệt để mối liên kết giữa các trang Web để xác đ ịnh một cách dễ nhất các trang liên quan. Không có một câu trả lời chính xác về độ lớn của các trang Web cũng như những thách thức của nó. Một số nghiên cứu đã ước lượng kích thước của cơ sở dữ liệu Web, trong khi đưa ra các số lượng khác nhau nhưng tất cả đều đồng ý rằng các trang Web có hiệu lực hiện nay, với kích thước trung bình của mỗi trang khoảng 5Kb tới 10Kb thì ta cũng có ít nhất là 10Tb dữ liệu, các tỷ lệ của các trang Web còn kinh khủng hơn, kích thước của trang Web sẽ tăng lên gấp đôi trong vòng hai năm và tỷ lệ đó sẽ tiếp tục tăng trong hai năm tiếp theo. Xong bên cạnh các trang vừa được tạo ra thì các trang đang tồn tại cũng luôn luôn được cập nhật, chẳng hạn, theo dõi hơn nửa triệu trang trong các miền như “.com” thì phải có đến 40% các trang được thay đổi hàng ngày. Cộng với kích thước rất lớn và tỷ lệ thay đổi liên tục của các trang 17
Web nó còn có một đặc trưng nữa đó là mối liên kết giữa các trang Web cho ta các tập tài liệu từ rất nhiều tập tài liệu khác. Một số nghiên cứu nhằm mục đích cho chúng ta hiểu liên kết giữa các trang Web được xây dựng như thế nào. Cho ví dụ, một nghiên cứu gần đây đã gợi ý rằng cấu trúc liên kết của các trang Web trong giống như một nơ con bướm. Có nghĩa là khoảng 28% các trang hình thành một lõi liên kết mạnh (tâm của nơ con bướm). Khoảng 22% hình thành nên một trong các vòng lặp của nơ, đó là các trang có thể được đ i từ lõi nhưng không thể ngược lại. Vòng lặp khác bao gồm 22% các trang có thể đi tới từ lõi nh ưng không thể được đi tới từ nó (còn lại một số nút không thể đi tới lõi mà cũng không thể được đi tới từ lõi). Kho lu tr÷ trang Ngêi sö dông Truy vÊn KÕt qu¶ Thu håi Module M« dule C«ng cô S¾p xÕp WWW LËp chØ Ph©n t×m kiÕm môc tÝch tËp hîp §iÒu khiÓn Thu Håi V¨n CÊu TiÖn B¶ng chØ môc : B¶n tróc Ých Ph¶n håi Hình 2 : Bộ công cụ tìm kiếm trang Web 18
Ở hình trên em đưa ra mô hình tổng quan của một bộ công cụ tìm kiếm Web. Mọi bộ công cụ đều sử dụng một mô đun Crawler để thu hồi tài liệu cung cấp cho các hoạt động của nó. Bộ thu hồi là một nhóm các chương trình thay mặt bộ công cụ để duyệt các trang Web, tương tự như một người sẽ kết nối để đi đến các trang khác, nhóm chương trình có đầu vào là một tập các giá trị khởi đầu URL mà các trang của nó sẽ được tìm kiếm từ Web. Bộ thu hồi trích các giá trị URL xuất hiện trong mỗi trang Web tìm kiếm được và gửi tới mô đun bộ điều khiển thu hồi. Mô đun này xác định liên kết nào được thăm tiếp theo, để cung cấp thông tin này tới các Crawlers (một vài chức năng cuả mô đun bộ điều khiển thu hồi có thể được thực hiện bởi chính các Crawler). Bộ thu hồi lưu các trang tìm kiếm được vào trong một kho lưu trữ trang (Page Repostory). Bộ thu hồi tiếp tục thăm các trang Web cho tới khi nguồn tài nguyên cục bộ bị cạn kiệt. Khi bộ công cụ tìm kiếm đã trải qua ít nhất một chu kỳ thu hồi (Crawling) thì mô đ un bộ điều khiển thu hồi có thể được hỗ trợ bởi các bảng chỉ mục được tạo ra trong quá trình bộ thu hồi trước. Ví dụ: Mô đun bộ điều khiển thu hồi có thể sử dụng đồ thị liên kết (bảng chỉ mục liên kết – Structure Index) của Craw trước để quyết định liên kết nào sẽ được sử dụng và liên kết nào sẽ bỏ qua. Bộ điều khiển thu hồi cũng có thể sử dụng các thông tin phản hồi để điều khiển quá trình xử lý Crawling (được nối kết giữa công cụ truy vấn và mô đun của bộ điều khiển thu hồi). Ở chương này em sẽ trình bày kỹ hơn về các hoạt động thu hồi. Trong môđun của bộ tạo chỉ mục (Indexer) trích tất cả các từ trong mỗi trang Web đồng thời ghi nhận giá trị URL nơi mỗi từ xuất hiện. Kết quả là thu được một “Bảng tìm kiếm” rất lớn cung cấp các giá trị URL trỏ tới các 19
trang chứa đựng từ tìm kiếm (đây chính là bảng chỉ mục văn bản – text index).Tuy nhiên phạm vi của bảng bị giới hạn trong nội dung các trang tìm thấy trong quá trình xử lý Crawling. Do kích thước rất lớn và sự thay đổi nhanh chóng của các trang Web đã làm cho việc lập chỉ mục văn bản trở nên khó khăn hơn nhiều. Ngoài ra chúng ta lại có thêm những bảng chỉ mục ít phổ biến, ví dụ như bảng chỉ mục cấu trúc (structure index) dùng để phản ánh mối liên kết giữa các trang. Mô đun phân tích tập hợp (Collection Analysis Module) sẽ tạo ra các bảng chỉ mục tiện ích khác hỗ trợ cho quá trình thu hồi thông tin. Bảng chỉ mục tiện ích (Utilyti index) được tạo ra bởi môđun phân tích tập hợp. Bảng chỉ mục tiện ích có thể cho phép việc truy cập tới các trang với độ dài cho trước, hoặc là các trang có mức độ quan trọng nào đó, hoặc là các trang với một số các hình ảnh trong chúng. Môđun phân tích tập hợp có thể sử dụng các bảng chỉ mục văn bản hoặc bản chỉ mục cấu trúc để tạo ra bản chỉ mục tiện ích. Trong suốt quá trình Crawling và Indexing, bộ công cụ tìm kiếm phải lưu trữ các trang tìm kiếm được. Kho lưu trữ trang sẽ phụ trách công việc này. Thỉnh thoảng bộ công cụ tìm kiếm phải duy trì một bộ nhớ đệm các trang đã thăm dựa theo thời gian xây dựng bảng chỉ mục. Bộ nhớ đệm này hỗ trợ cho việc đưa ra các trang kết quả một cách nhanh chóng và cung cấp các tiện ích tìm kiếm cơ bản. Một vài hệ thống, giống như Internet Archive đã duy trì một số lượng rất lớn các trang và lưu trữ chúng lâu dài. Vấn đề lưu trữ cũng phải đ ược xem xét một cách cẩn thận. Mô đun “công cụ truy vấn” (Query Engine) có nhiệm vụ nhận và tìm kiếm các yêu cầu từ người sử dụng. Bộ công cụ sẽ dựa vào bảng chỉ mục và 20