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 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 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. M« dule Ph©n tÝch tËp hîp WWW Module LËp chØ môc C«ng cô t×m kiÕm S¾p xÕp Ng­êi sö dông §iÒu khiÓn Thu Håi Kho l­u tr÷ trang Thu håi Truy vÊn KÕt qu¶ B¶ng chØ môc : TiÖn Ých Ph¶n håi CÊu tróc V¨n B¶n 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 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). M« dule Ph©n tÝch tËp hîp WWW Module LËp chØ môc C«ng cô t×m kiÕm S¾p xÕp Ng­êi sö dông §iÒu khiÓn Thu Håi Kho l­u tr÷ trang Thu håi Truy vÊn KÕt qu¶ B¶ng chØ môc : TiÖn Ých Ph¶n håi CÊu tróc V¨n B¶n Hình 2 : Bộ công cụ tìm kiếm trang Web Ở 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 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à thỉnh thoảng là các kho lưu trữ trang. Bởi kích thước lớn của Web thêm vào nữa khi người sử dụng chỉ đưa vào một hoặc là hai từ khóa thì sẽ nhận được một tập rất lớn các trang kết quả. Do vậy phải có một môđun Ranking thực hiện việc sắp xếp kết quả sao cho các kết quả ở gần đầu sẽ giống với nội dung đang được tìm kiếm hơn. Môđun truy vấn được quan tâm một cách đặc biệt, bởi vì: Với các kỹ thuật truyền thống ta chỉ dựa vào sự đo lường về độ tương quan giữa văn bản trong tập tài liệu. Trong khi đó, đối với bộ công cụ tìm kiếm Web, các truy vấn thì rất nhỏ còn tập dữ liệu thì lại rất lớn, nó đã ngăn chặn sự đánh giá về độ tương quan dựa trên phép tính gần đúng từ việc lọc số lượng các trang không liên quan ra khỏi kết quả tìm kiếm. 1.3 Mô hình bộ công cụ tìm kiếm thông tin truyền thống Vào những năm 70, khi các mô hình tìm kiếm thông tin chủ yếu được xử lý với các truy vấn không có cấu trúc thì các hệ thống truy vấn tự động đã mở thành một sự kiện. Nguyên tắc hoạt động của các hệ thống truy vấn tự động là chỉ số hóa và thiết lập công thức truy vấn, kết quả đưa ra là một biểu diễn có ý nghĩa gần với thực của văn bản, loại bỏ các từ không theo quy tắc trong ngôn ngữ tự nhiên đến mức có thể. Sau đây em đưa ra một mô hình tổng quát của hệ thống tìm kiếm thông tin truyền thống. TËp tµi liÖu Giao diÖn sö dông Ng­êi sö dông C¬ Së D÷ LiÖu T×m KiÕm T¸ch tõ §¸nh chØ sè tµi liÖu Lo¹i bá StopList ChuÈn hãa tõ ChuÈn hãa tõ Ph©n tÝch có ph¸p truy vÊn Ho¹t ®éng Boolean §¸nh träng sè Ph¶n håi ®é liªn quan S¾p xÕp V¨n b¶n Tõ ChØ sè tµi liÖu, ChØ sè tr­êng Tµi liÖu Tõ kh«ng n»m trong StopList Tõ ®· chuÈn ho¸ Tõ, träng sè TËp tµi liÖu liªn quan Tõ truy vÊn TËp tµi liÖu thu håi ®­îc TËp tµi liÖu ®· s¾p xÕp TËp tµi liÖu t×m kiÕm Truy vÊn Truy vÊn H×nh 3 : M« h×nh bé c«ng cô t×m kiÕm truyÒn thèng Khi xây dựng cơ sở dữ liệu, nội dung của tập tài liệu được tách thành các từ. Các từ này được so sánh với Stoplist - một danh sách các từ không được lập chỉ mục (nó không có giá trị nội dung trong nhận dạng văn bản, ví dụ a, an, the, about....). Các từ không nằm trong Stoplist sẽ được chiết lọc để lấy gốc (stemming). Các từ có thể thống kê tần suất xuất hiện để hỗ trợ cho việc sắp xếp các tài liệu thu hồi được. Cuối cùng các từ cùng với các thông tin kết hợp với chúng (ví dụ: định danh tài liệu, định danh trường nằm trong tài liệu và các giá trị thống kê...vv) được dặt vào kho cơ sở dữ liệu. Kho cơ sở dữ liệu có thể bao gồm các cặp giá trị định danh tài liệu và các từ khóa. Cấu trúc này được gọi là tập tin đảo (Inverted File). Để tìm kiếm trong cơ sở dữ liệu, người sử dụng đưa vào một truy vấn bao gồm một tập các từ khóa được nối kết với nhau bởi các toán hạng logic (And, Or, Not). Truy vấn được phân tách thành các từ liên tiếp và các toán hạng lôgic của chúng. Các từ này được tìm kiếm trong tập tin đảo, sau đó được kết hợp với nhau dựa theo các toán hạng logic. Dựa vào thông tin thống kê, tập thu hồi trên có thể được sắp xếp theo thứ tự có liên quan đến nội dung. Kết quả này được đưa đến người sử dụng. Trong một số hệ thống, người sử dụng có thể đưa ra một số đánh giá về độ liên quan của tài liệu tìm kiếm được và những thông tin này được sử dụng để tự động thay đổi truy vấn bằng cách thêm vào các từ từ những tài liệu liên quan và xóa đi các từ từ những tài liệu không liên quan. Cấu trúc dữ liệu trong tổ chức lưu trữ và tìm kiếm thông tin 1.4.1 Bảng băm 1.4.1.1 Khái niệm hàm băm (Hash function) Hàm băm h là một ánh xạ từ tập L đến tập các giá trị M nào đó. Thông thường M là một tập các số nguyên giả sử từ 0 tới m, khi đó với mỗi giá trị xi thuộc L sẽ tương ứng với một số h(xi) thỏa mãn: Một trong những hàm băm được đề cập rất sớm và thường xuyên trong các giáo trình phổ thông là hàm lấy phần dư trong đó các giá trị băm của khóa xi được tính theo công thức: Với m là một số nguyên tố phù hợp, chữ phù hợp ở đây mang ý nghĩa là một số nguyên tố lớn. Hệ số a = n/m được gọi là hệ số tải với n là số khóa trong tập L. Giá trị này càng nhỏ thì khả năng hai khóa khác nhau có cùng một giá trị băm càng nhỏ (hiện tượng này được gọi là xung đột). Hàm băm h được gọi là một hàm băm hoàn hảo nếu nó thỏa mãn tính chất vì mọi xi, xj thuộc L ta có: h(xi) = h(xj) khi v à ch ỉ khi xi = xj. Tính chất này đảm bảo không xảy ra đụng độ như đã nói ở trên, dễ thấy rằng để thỏa mãn điều kiện này thì trước hết phải có a £ 1. Khi a =1 (tức là với mỗi giá trị khóa tương ứng duy nhất một giá trị băm và ngược lại) ta nói hàm băm khi đó có tính chất tối ưu. Việc thiết kế một hàm băm hoàn hảo tối ưu là tương đối phức tạp, hơn nữa hàm băm này chỉ là tối ưu hoàn hảo đối với tập dữ liệu này chứ không phải là tối ưu hoàn hảo với tập dữ liệu khác nên mặc dù việc sử dụng một hàm băm dạng này tương đối thuận lợi nhưng nó không phải là giải pháp có hiệu quả khi thiết kế chương trình. Thay vào đó, với việc sử dụng các phương pháp giải quyết xung đột sẽ được trình bày dưới đây thì các hàm băm thông thường tỏ ra có ưu thế hơn cả về thời gian thực hiện lẫn mức độ đơn giản trong cài đ Khái niệm bảng băm Bảng băm là một mảng các phần tử trong đó có sử dụng một cơ cấu hàm băm cho phép tăng tốc quá trình tìm kiếm những thông tin tương ứng với một phần tử nào đó của mảng. Giả sử ta có một tập rất lớn các khóa như là một tập số nguyên không âm N và tồn tại một hàm h ánh xạ từ tập N tới tập M = {0,1..............,m} với m >1. T là một tập với m phần tử được đánh số từ 0 đến m-1, với các phần tử của T hoặc là chứa một bản ghi hoặc có giá trị Void (giá trị Void chỉ ra rằng phần tử đó không chứa một bản ghi nào cả). Ta có thể biểu diễn một tập bản ghi A bằng cách đặt T[h(a)] = r Trong đó a = key(r) là khóa của bản ghi r, với mọi r Î A. Ví dụ với m = 12, A = {22,39,46,54,79,198} và h(i) =i mod 13 với mọi i Î N xem như các bản ghi ở đây chính là khóa của nó). Khi đó : h(22) = 22 mod 13 = 9 => T [9] = 22 h(39) = 39 mod 13 = 0 => T [0] = 39 h(46) = 46 mod 13 = 7 => T [7] = 46 h(54) = 54 mod 13 = 2 => T [2] = 54 h(79) = 79 mod 13 = 1 => T [1] = 79 h(198) = 198 mod 13 = 3 => T [3] = 198 Ta gọi h là hàm băm (hash function), T là bảng băm (hash table) và h(i) là giá trị băm của i Nếu tập A có thêm phần tử {14} thì ta có h(14) = 14 mod 13 = 1Þ T[1] =14 Như vậy 79 và 14 sẽ chiếm cùng một phần tử T[1]. Từ đây ta có hai hướng để giải quyết, thứ nhất là tránh xung đột bằng cách xây dựng hàm băm hoàn hảo hoặc cũng có thể tránh xung đột bằng cách mở rộng kích thước bảng băm. Thứ hai là chấp nhận xung đột và áp dụng một số giải pháp giải quyết xung đột. Như phần trên đã chứng minh, hướng thứ nhất thực hiện rất phức tạp và có thể vẫn xảy ra xung đột, nên sang phần sau em sẽ trình bày hướng giải quyết thứ hai. 1.4.1.3 Giải quyết xung đột * Phương pháp Chaining: Phương pháp này cho ta thấy khá đơn giản, mỗi phần tử của bảng băm được gắn với một danh sách liên kết, các bản ghi có cùng giá trị băm của khóa được đặt vào danh sách liên kết đó. Chaining dễ dàng trong việc cài đặt, mặt khác danh sách liên kết trong bảng băm thường là ngắn, nên việc tìm kiếm, chèn xóa được thực hiện một cách nhanh chóng. Thông thường để thuận tiện trong việc tìm kiếm cũng như xóa, bổ xung, danh sách được sắp xếp theo thứ tự tăng dần của các khóa ( nếu các khóa có thể so sánh được). Computer Science Null Stop Null Data Null Null Null Null Hình 4: Cấu trúc bảng băm Giải thuật tìm kiếm và chèn một bản ghi vào bảng băm được tổ chức theo phương pháp Chaining: C1. Hash C2 . Is there a list ? C3. Compare C4 .Advance to next C5. Insert new key End Of List No Yes Success Hình 5: Giải thuật tìm kiếm và chèn một khóa vào bảng băm Giải thuật tìm kiếm một khóa K cho trước trong một mảng m phần tử. Nếu k không có trong bảng, có thể xin cấp phát trong bộ nhớ và K được chèn vào bảng. Trong thuật toán kí hiệu Table[i] chỉ phần tử thứ i của bảng băm (với 0 i m), và chúng có hai giá trị empty và occupied. Một phần tử nhận giá trị là occupied chứa một trường Key, một trường Link, ngoài ra còn có một số trường khác. Giải thuật sử dụng hàm băm h(K). C1. [Hash] : I ß h(K) C2. [is there a list] if Table[i] = empty goto C5 Else (Table[i] = occupied) Ptr = Linklist[i] (trá tíi nót ®Çu tiªn cña danh s¸ch øng víi Table[i]) C3. [Compare] if K = ptr à key return Successfully C4. [Advace to Next] if ptr à Link Null Ptr ß ptràLink Goto C3 C5 [Insert new key] : if Table = empty Table[i] = occupyed New(Node) Node.Key ß K Node.Link ß Null Ptr àlink ß Node Return successfully * Phương pháp Open Addressing Phương pháp này sẽ tiến hành kiểm tra nhiều phân tử của bảng băm, việc kiểm tra được thực hiện với từng phần tử một cho đến khi hoặc là khóa K cần tìm được hoặc là tìm thấy một vị trí trống trong bảng băm (void). Ý tưởng của phương pháp này là định ra một số luật, bằng các luật đó với mọi khóa K xác định được một chuỗi các vị trí trong bảng băm mà tại đó K có thể được chèn vào hay tiến hành kiểm tra, thì được gọi là “dãy thăm dò”. Cơ chế đơn giản nhất của Open Addressing là thăm dò tuyến tính với dãy thăm dò được xây dựng như sau: h(K), h(K) – 1,..., 0, m-1,m-2,..........h(K) + 1 trong đó m là số phần tử của bảng băm. Dưới đây chúng ta sẽ xem xét giải thuật tìm kiếm và chèn một khóa K và bảng băm được tổ chức với cơ chế thăm dò tuyến tính. Giải thuật: Giải thuật tiến hành tìm kiếm khóa K cho trước, nếu K không có trong bảng băm và bảng băm chưa đầy thì K sẽ được chèn vào. Kí hiệu Table[i] chỉ phần tử thứ i của bảng băm và giá trị mà nó có thể nhận là emty và occupied. Một phần tử nhận giá trị occupied chứa một trong trường Key[i] và có thể có thêm một số trường khác. Một biến phụ N chỉ số phần tử của C1 . Hash C3. Compare C4. Advance to next C4. Insert new key No Success yes H×nh 6: Gi¶i thuËt t×m kiÕm vµ chÌn mét kho¸ vµo b¶ng b¨m bảng băm có giá trị occupied, N được tăng lên 1 mỗi khi có một khóa mới được chèn vào. Giải thuật sử dụng hàm băm h(K) và sử dụng dãy thăm dò. L1. [Hash] : I ß h(K) L2.[Compare] : if Table[i] = empty goto L4 Else if Key[i] = K Return Successfully L3. [Advance to next] : I:= I-1 If (I < 0 ) I = I+m Goto L2 L4. [Insert] : If (N = m-1) Hash Table full, return Else N = N+1 Table[i] = occupied Key[i] = K return Xây dựng dãy thăm dò bằng cơ chế thăm dò tuyến tính như trên có ưu điểm là đơn giản, nhưng hiệu năng của hệ thống sẽ giảm nhanh chóng khi hệ số tải tăng, vì thế mà cơ chế thăm dò hiện nay hầu như chỉ dùng để minh họa cho ý tưởng của phương pháp Open – Addressing, thay vào đó người ta sử dụng cơ chế băm kép với việc sử dụng hai hàm băm thay vì một như ở trên. Một hàm dùng để tính địa chỉ gốc ( là địa chỉ của K nếu khe tương tự với K trong bảng băm chưa có phần tử nào), một để tính giá trị ra tăng (khoảng cách giữa địa chỉ thật và địa chỉ gốc). Cây cân bằng nhiều đường B – Tree Định nghĩa cây B- Trees Cây B- Trees là sự mở rộng của cây nhị phân mà mỗi nút của nó chứa đựng nhiều khóa. Một cây B-Trees cấp m thỏa mãn những tính chất sau: Mọi nút có ít hơn hoặc bằng m con Mọi nút ngoại trừ gốc và các nút lá có nhiều hơn hoặc bằng m/2 con Gốc có ít nhất là 2 con (trừ khi nó là nút lá) Tất cả các lá có cùng một cấp Một nút không phải lá với k con chứa đựng k-1 khóa 23 234 6 12 19 37 102 157 308 322 351 369 31 32 35 99 100 132 141 147 154 170 216 232 Hình 7: Cấu trúc cây B – Tree ( m = 4) P0, K1, P1, K2,……………, Pj – 1, Kj, Pj Một trang chứa đựng j khóa và j+1 con trỏ có thể được diễn tả như sau Trong đó K1 Kj, và Pi (0 < i < j ) trỏ tới cây con có các khóa K sao cho: Ki < K < Ki+1. *Tìm kiếm trong cây B- Trees: Sau khi một trang được tìm kiếm và nạp vào trong bộ nhớ trong, ta tiến hành tìm kiếm giữa các khóa K1, K2,...Kj. nếu khóa tìm kiếm bằng với Ki thì quá trình tìm kiếm hoàn thành. Ngược lại, nếu khóa nằm giữa Ki và Ki+1 thì trang trỏ bởi Pi sẽ được tòm và nạp và quá trình sử lý được tiếp tục. nếu khóa nhỏ hơn K1 thì sử dụng P0 còn nếu khóa lớn hơn kj thì sử dụng pj. Nếu Pi là một con trỏ rỗng, thì việc tìm kiếm không thành công. P0, K1,……, Kém/2ù -1 , Pém/2ù -1 Pém/2ù , Kém/2ù +1, Pém/2ù + 1,……, Km , Pm Thuật toán chèn cũng rất đơn giản. Trong hầu hết các trường hợp, khóa mới sẽ được chèn vào trong một nút lá tương ứng, nhưng nếu nút lá đó đầy thì phải tách ra làm hai, và khóa ở giữa của nút phải được chèn vào trong nút cha. Việc chèn này có thể gây cho nút cha có quá nhiều khóa và cũng phải tách ra làm hai, quá trình tách này có thể lan truyền tới gốc. Nếu nút gốc phải tách ra thì phải tạo ra một nút gốc mới với chỉ một giá trị khóa K[m/2], thuật toán chèn vẫn luôn giữ được các thuộc tính của cây B- Tree. Để đảm bảo được thuộc tính của cây trong thuật toán xóa ta phải xử lí nhiều phép lan truyền trên cây, do không có đủ thời gian, thuật toán lại quá phức tạp mà hiện nay đã có thuật toán xóa mới trên cây B+ -Tree rất đơn giản nhưng vẫn giữ được tính chất của cây B-Tree. Em xin không trình bày thuật toán xóa ở đây, mà em trình bày thuật toán xóa của cây B+ - Tree ở phần sau. Cây B* - Tree Cây B* - Tree giống với cây B-Tree ban đầu, tuy nhiên mỗi nút chứa ít nhất 2/3 m khóa (m là số lượng khóa lớn nhất mà mỗi nút có thể chứa được). Thuộc tính của cây B*- Tree như sau: Mọi nút có ít hơn hoặc bằng m con Mọi nút ngoại trừ gốc và lá có nhiều hơn (2m-1)/3 Gốc có ít nhất 2 con và nhiều nhất 2[(2m-2)/3] +1 con Tất cả lá có cùng cấp bậc Nút không phải lá với k con chứa đựng k-1 khóa Tuy cây B* - Tree có thể làm cho chiều cao của cây giảm nhưng thuật toán chèn vào xóa lại rất phức tạp, mỗi lần xử lý ta không chỉ chỉnh sửa nút cha của nút hiện thời mà còn phải duyệt cả nút anh của nó nữa. Có nghĩa là, nếu nút cần chèn đã đầy, ta duyệt nút anh của nó, nếu không đầy thì ta chuyển dữ liệu của nút sang nút anh, còn nếu cả hai nút cùng đầy thì ta phải tách cả hai nút đó ra. Do tính chất phức tạp của thuật toán mà ta xin không trình bày ở đây. – Tree ( m = 4) 29 281 6 12 19 99 132 170 308 322 351 369 31 32 35 99 100 132 141 147 154 170 216 272 D÷ liÖu kÕt hîp víi kho¸ 1.4.2.3 Cây B+ - Tree H ình 8: Cấu trúc cây B+ - Tr ee (m =4) Thông thường ta phải thêm một số loại dữ liệu đi cùng với khóa trong cây B-Tree, ví dụ như địa chỉ của khóa trong dữ liệu, tần xuất của khóa...vv.Cây B+- Trees là một biến thể của cây B-Trees, trong đó các khóa tại nút lá sẽ được kết hợp với dữ liệu của nó,và một vài khóa được sao chép lên cấp bậc cao hơn. Một nút không phải lá trong B+- Tree có dạng P0, K1, P1, K2,……………,Pj – 1, Kj, Pj Trong đó K1 là bản sao khóa đầu tiên của nút trỏ bởi P1, K2 là khóa đầu tiên của nút trỏ bởi P2...vv. Cây con trỏ tới bởi Pi chứa đựng tất cả các khóa K: KiK<Ki+1. cây con trỏ tới bởi P0 chỉ chứa đựng các khóa K<K1, và cây con trỏ tới Pj chỉ chứa đựng các khóa KKj. K1, D1 , K2 , D2 , ………………., Dj – 1, Kj , Dj Nút lá trong cây B+ - Tree được diễn tả như sau Trong đó Di là dữ liệu kết hợp với khóa Ki. Thuật toán chèn trong cây B+- Tree tương tự như thuật toán chèn trong cây B-Tree thông thường, tuy nhiên khi một nút bị tách thành hai thì khóa đầu tiên của nút sau sẽ được sao chép lên nút cha. Giải thuật chèn trên cây B+ - Tree: Tìm nút lá nơi khóa sẽ được chèn chèn khóa và dữ liệu vào vị trí tương trong nút If (nút quá đầy) Then Begin Tách nút thành hai Chèn khóa đầu tiên của nút sau lên cha End Thuật toán xóa trong cây B+-Trees dễ hơn rất nhiều so với thuật toán xóa trên cây B-Tree. Với những đánh giá và phân tích thì thuật toán chèn và xóa trên cây sẽ làm cho các nút trên cây luôn luôn chứa khoảng 68% dữ liệu tối đa, và thậm chí các nút chỉ tự do khi chúng rỗng. Giải thuật xóa trên cây B+- Tree Tìm nút lá chứa khóa bị xóa Xóa khóa và dữ liệu của nó từ nút If (Nút rỗng sau khi xóa) Then begin Giải phóng nút Xóa cặp(Ki, Pi ) cho nút này trong nút cha End Với những tính chất của mình cây B+ - trees đã trở thành một cấu trúc tối ưu trong các ứng dụng cơ sở dữ liệu. Điều khiển cây B+ -Tree cũng dễ dàng hơn rất nhiều so với cây B-Tree, và nó cũng rất dễ dàng làm cho các nút có cùng một cấp bậc. Cây BLink – Trees Với định nghĩa được nêu ở trên, ta có được đầy đủ những tính chất tối ưu của cây B+ - Tree, xong ta nhận thấy rằng các trang lá trên cây tạo thành một mảng sắp xếp nhưng lại là một mảng rời rạc, vì vậy mà nó gây khó khăn cho quá trình tìm kiếm khi mà phạm vi tìm kiếm được nằm trên nhiều hơn hai trang, ví dụ như ta lấy 4 giá trị liền nhau trong một lần truy cập nhưng 4 giá trị này được nằm trên hai lá liền nhau của cây. Để khắc phục vấn đề này em xin đưa ra cấu trúc cây BLink – Tree, trong đó mỗi trang có thêm một con trỏ trỏ tới ngay trang liền kề với nó. 29 281 6 12 19 99 132 170 308 322 351 369 31 32 35 99 100 132 141 147 154 170 216 272 D÷ liÖu kÕt hîp víi kho¸ Hình 9: Cấu trúc cây B+ – Tree ( m = 4) 1.4.2.5 Lựa chọn phương pháp lưu trữ dữ liệu tần số Trong tài liệu các từ thường xuất hiện rất nhiều lần, vì vậy mà hệ thống lập chỉ mục phải có khả năng lưu trữ dữ liệu tần xuất một cách hiệu quả. Dưới đây em đưa ra một số phương pháp duy trì dữ liệu này cho các khóa: * Mỗi tần xuất có thể được lưu trữ như một khóa trong bảng chỉ mục. Phương pháp này gây lãng phí không gian bộ nhớ và gây phức tạp cho thuật toán B-Tree * Dữ liệu tần suất có thể được lưu trữ trong nút cùng với khóa. Nhưng do sự giới hạn về kích thước của nút nên chỉ có một số hữu hạn tần xuất được lưu trong nút. * Mỗi khóa trong bảng chỉ mục có thể chứa đựng một con trỏ tới một khối lưu trữ dữ liệu tần xuất ở bên ngoài. Nó đòi hỏi thời gian truy cập đĩa khi một khóa được thêm vào hay được truy cập đến. Kích thước của khối ngoại vi có thể được nhân đôi khi nó trở nên đầy, ít nhất một nửa không gian trong khối luôn được sử dụng. * Một vài dữ liệu tần số được lưu cùng với khóa,và khi dữ liệu đẫ được tập hợp đủ, một số trong chúng được gửi ra khối bên ngoài. Kỹ thuật này được gọi là Pulsing. CHƯƠNG II CÁC CÔNG CỤ TÌM KIẾM CƠ BẢN 2.1 Thu hồi trang Web 2.1.1 Bộ thu hồi Web Các Web Crawler có nhiệm vụ thu hồi các trang Web site khác nhau trên Internet về cho bộ Indexer. Web Crawler đầu tiên được thiết kế bởi Matthew Gray năm 1993 và được đặt tên là Wanderer. Web Crawler có đầu vào là một tập các giá trị khởi tạo URL – S0. Đầu tiên nó đặt S0 trong một hàng, nơi lưu trữ tất cả các giá trị URL thu được và sắp xếp chúng theo một thứ tự ưu tiên nào đó. Từ hàng lưu trữ này, Crawler lấy một giá trị URL, tải trang tương ứng xuống rồi trích tất cả giá trị URL nằm trong trang và đặt chúng vào hàng. Quá trình xử lý này được lặp đi lặp lại cho tới khi Web Crawler quyết định dừng. Các địa chỉ mới tìm thấy có thể được sử dụng ngay để bộ thu hồi Web tìm ra trang Web mới hoặc chúng có thể được lưu trữ vào cơ sở dữ liệu của bộ thu hồi Web để nó lập lịch tìm kiếm sau này. Các Web Crawler xem Internet như một đồ thị với các Site là các đỉnh của đồ thị và duyệt đồ thị theo chiều rộng hoặc chiều sâu để thu thập thông tin cần thiết. Nó cũng cho phép người sử dụng đăng ký các trang Web của mình bằng cách thêm địa chỉ URL của họ vào tập S0 các URL ban đầu. Nhờ vậy mà các thông tin về trang Web của họ được cập nhật sớm hơn, trước khi Web Crawler được tìm thấy, Có hai vấn đề mà Web Crawler cần phải đối phó: Thứ nhất là các trang Web luôn thay đổi, vì thế các trang mà chỉ mục trỏ đến có thể không còn tồn tại nữa. Thứ hai là vấn đề cập nhật lại các trang Web khi chúng đã lỗi thời. Web Crawler có thể tìm kiếm hàng triệu trang Web mỗi ngày. Để nghiên cứu một Web Crawler người ta thường tìm hiểu các vấn đề sau: 2.1.2 Chọn lựa các trang Ở đây, Crawler luôn muốn chọn lọc các trang quan trọng, để thu thập được một tập dữ liệu có chất lượng cao, để xem Crawler hoạt động và gợi ý như thế nào để thăm các trang tốt , chúng ta đi tìm hiểu vấn đề này. * Ma trận độ quan trọng Cho một trang Web P, chúng ta có thể định nghĩa độ quan trọng của trang theo một trong các cách sau. 1.Mức độ quan tâm: Mục đích đặt ra là thu được các trang liên quan tới nội dung tìm kiếm của một hoặc là một nhóm người sử dụng. Để định nghĩa được khái niệm này là thông qua mức độ quan tâm. Cho một truy vấn Q, mức độ quan trọng của P được định nghĩa là “độ tương quan văn bản ” giữa P và Q. Một cách hình thức hơn, để tính toán độ tương quan giữa các văn bản, đầu tiên chúng ta mô tả mỗi tài liệu (P hoặc Q) như là một véc tơ m chiều w1, w2........, wm, wi trong véc tơ này diễn tả từ thứ i trong bộ từ vựng. nếu wi không xuất hiện trong tài liệu thì wi bằng 0, còn nếu xuất hiện wi được thiết lập để diễn tả ý nghĩa của từ. Một cách phổ biến để tính mức độ quan trọng wi đó là nhân số lần của từ thứ i xuất hiện trong văn bản với nghịch đảo của lần suất tài liệu (inverse document frequence - IDF) của từ thứ i. IDF bằng 1 chia cho số lần từ đó xuất hiện trong toàn bộ Web. Sau đó chúng ta định nghĩa độ tương quan giữa P và Q là tích cosine giữa các véc tơ P và Q. Giả sử truy vấn Q diễn tả sự quan tâm của người sử dụng, thì ma trận này chỉ ra trang P liên quan tới nó như thế nào.Chúng ta sử dụng kí hiệu IS(P) để chỉ độ quan trọng ma trận này. Lưu ý rằng nếu chúng ta không sử dụng toán hạng IDF trong việc tónh độ tương quan thì độ quan trọng của một trang có thể được tính toán với thông tin cục bộ, ví dụ như là P và Q. Còn nếu sử dụng số hạng IDF thì chúng ta cần thông tin toàn cục. Trong suốt quá trình xử lý Crawling chúng ta không có toàn bộ tập tài liệu vì thế chúng ta phải ước lượng thừa số IDF từ các trang đã được Crawling, hoặc từ vài số hạng được tính toán từ trước. Chúng ta sử dụng IS (P) chỉ độ quan trọng của trang P được tính theo cách trên để phân biệt với độ quan trọng thông thường IS(P) (được tính toán sau khi toàn bộ trang Web đã được tải). 2. Mức độ phổ biến: Một cách để định nghĩa mức độ phổ biến là sử dụng tổng số Backlink của một trang ( thuật ngữ backlink ở đây được định nghĩa số các liên kết trỏ tới trang đã cho). Vì thế các Backlink của trang P là tập hợp tất cả các liên kết trên các trang trỏ tới P. Khi sử dụng các giá trị backlink như một ma trận đánh giá mức độ phổ biến thì giá trị đánh giá mức độ quan trọng của trang P là số các liên kết tới P xuất hiện trên toàn bộ Web. Chúng ta sử dụng ký hiệu IB(P) để phân biệt cách tính này với cách tính độ quan trọng khác. Bằng trực giác ta thấy rằng một trang Web P được nhiều trang Web khác liên kết tới thì sẽ quan trọng hơn các trang Web khác liên kết tới thì sẽ quan trọng hơn các trang Web ít được các trang Web khác đề cập tới. Trên Web IB(P) thường được sử dụng để sắp xếp kết quả tìm kiếm tới người sử dụng cuối sao cho các trang đầu tiên giống với nội dung đang được quan tâm nhất. Lưu ý rằng đánh giá IB(P) đòi hỏi phải tính tổng của các backlink trên toàn bộ Web. Một Crawler có thể ước lượng giá trị này với IB’(P) - số lượng các liên kết đã được xem xét đến trang P. 3. Theo vị trí của trang : Cách xác định vị trí quan trọng của trang P là một hàm tính theo vị trí của nó IL(P), chứ không phải là nội dung của nó. Nếu URL u dẫn tới trang P, thì IL (P) là một hàm của u. Cho ví dụ URL kết thúc với “.com” có thể được cho rằng phổ biến hơn các URL kết thúc ở dạng khác, hoặc URL chứa đựng xâu “home” có thể được quan tâm URL khác. Ma trận vị trí thỉnh thoảng cũng cho rằng các URL với ít đường gạch chéo sẽ thường dùng hơn các URL có nhiều đường gạch chéo. Các ma trận vị trí có thể được xem xét như là một trường hợp đặc biệt của ma trận độ quan tâm, xong chúng ta có thể liệt kê ra đây một cách riêng biệt bởi chúng rất dễ dàng để đánh giá. Cụ thể là tất cả các ma trận vị trí đề xuất ở đây mang tính cục bộ, bởi ta có thể ước lượng một cách đơn giản trên giá trị URL u. Ma trận đánh giá mức độ của chúng ta có thể được kết hợp trong nhiều cách khác nhau. Dựa vào vị trí độ quan trọng của trang Web không chỉ phụ thuộc vào nội dung trang Web mà còn thể hiện ở địa chỉ URL của chúng. Ví dụ chúng ta có thể định nghĩa ma trận: IC(P) =k1 . IS (P) + k2 .IB(P) + k3 .IP (P) với k1,k2,k3 là các hằng số. * Các mô hình thu hồi Vấn đề đặt ra ở đây là thiết kế một Crawler để có thể thăm các trang quan trọng dựa trên một ma trận đánh giá mức độ quan trọng nào đó. Dựa trên những ước lượng mà Crawler sẽ phải gợi ý các trang quan trọng để tìm và nạp tiếp theo. Dưới đây là hai mô hình phổ biến nhất của một bộ Crawler: + Thu hồi và dừng: Ở mô hình này, Crawler C bắt đầu tại trang P0 và dừng sau khi đã thăm K trang ( trong đó K là một số không đổi xác định số lượng các trang Crawler sẽ tải trong một quá trình thu hồi). Theo định nghĩa này một Crawler hoàn hảo sẽ thăm các trang R1, R2,......., Rk trong đó R1 có giá trị quan trọng cao nhất, R2 có giá trị quan trọng cao thứ 2.... Chúng ta có thể gọi các trang R1, Rk là các trang nóng . Còn đối với K trang được thăm bởi Crawler thực sự sẽ chỉ chứa đựng MK trang với sự sắp xếp cao hơn hoặc bàng Rk , lưu ý rằng chúng ta cần biết sự sắp xếp chính xác của tất cả các trang để thu được giá trị M, rõ ràng sự ước lượng này là không thể cho tới khi chúng ta tải toàn bộ các trang xuống và có một bức tranh toàn cảnh về Web. Ta định nghĩa hiệu suất thực hiện của Crawler C là PCS(C) = (M.100)/K. Khả năng thực hiện của các Crawler lí tưởng là 100%. Crawler quản lý việc thăm toàn bộ các trang một cách ngẫu nhiên và có thể thăm lại chúng, sẽ có hiệu suất là (K . 100 )/T, trong đó T là tổng số lượng các trang trên Internet, sác xuất thăm trang nóng là K/T).Vì vậy số lượng mong đợi của các trang mong muốn khi Crawler dừng là K2/ T. + Thu hồi và dừng với ngưỡng: Giả sử rằng Crawler thăm K trang. Bây giờ chúng ta đưa ra một giá trị mục tiêu G về độ quan trọng và bát kỳ trang nào có mức độ quan trọng cao hơn G được xem là nống. Giả sử rằng tổng số các trang nóng là H. Hiệu suất Crawler, PST(C), là phần trăm của các trang nóng đã được thăm sau khi Crawler dừng. Nếu K<H thì một Crawler lý tưởng sẽ có hiệu suất 100%. Một Crawler ngẫu nhiên hoàn hảo khi thăm lại các trang sẽ mong đợi thăm(H/T).K trang nóng khi nó dừng. Vì thế hiệu suất của nó là(K.100)/T. Chỉ khi Crawler ngẫu nhiên thăm tất cả T trang thì hiệu suất mong đợi là 100%. * Ma trận thứ tự Một Crawler lưu trữ một hàng các giá trị URL mà nó đã tìm thấy trong suốt quá trình crawl, mà phải lừa chọn từ hàng này một giá trị URL được thăm tiếp theo. Ma trận thứ tự sẽ được Crawler sử dụng cho sự lựa chọn này, ví dụ nó chọn URL u sao cho giá trị thứ tự của nó là cao nhất trong số tất cả các URL trong hàng. Ma trận thứ tự có thể chỉ sử dụng các thông tin được tìm thấy bởi Crawler. Ma trận thứ tự nó có cùng nghĩa với ma trận đánh giá mức độ quan trọng. Chẳng hạn chúng ta đang tìm kiếm các trang có IB(P) cao, thì cũng tương tự như ta chọn chúng theo thứ tự của giá trị IB’(P) (ma trận PageRank). Ma trận vị trí có thể được sử dụng một cách trực tiếp để lựa chọn thứ tự, do URL của trang P cho ta ngay giá trị IL(P). Tuy nhiên, với các ma trận tương quan, nó khó hơn nhiều để đưa ra một ma trận thứ tự, khi chúng ta vẫn chưa tìm thấy P. 2.2 Lưu trữ Từ hình 3 cho chúng ta thấy kho lưu trữ các trang là một hệ thống lưu trữ mở rộng để quản lý tập hợp các trang Web. Kho lưu trữ sẽ thực hiện hai chức năng cơ bản. Thứ nhất nó cung cấp một giao diện để Crawler lưu trữ các trang. Thứ hai, nó phải cung cấp cách truy cập hiệu quả để các mô đun chỉ mục và mô đun phân tích tập hợp sử dụng cho việc tìm kiếm các trang. Một kho lưu trữ và quản lý một tập rất lớn các đối tượng dữ liệu, ở đây chính là các trang Web. Tuy nhiên một kho lưu trữ Web không phải cung cấp nhiều chức năng như các hệ thống File và các hệ thông cơ sở dữ liệu, nhưng thay vào đó như khả năng mở rộng vì nó phải phân tán kho lưu trữ trên một nhóm các máy tính và các đĩa để đối phó với kích thước của Web. Bên cạnh đó là việc tồn tại mô hình truy nhập kép, khi đó kho lưu trữ phải được hỗ trợ hai mô hình khác nhau có hiệu quả truy cập ngang nhau. Truy cập ngẫu nhiên sử dụng để thu hồi một trang Web cụ thể cho bởi một giá trị nhận dạng duy nhất của trang. Tuy cập theo luồng được sử dụng để thu hồi toàn bộ tập hợp, hoặc là một vài tập con quan trọng như một luồng các trang. Truy cập ngẫu nhiên được sử dụng bởi công cụ truy vấn để đưa ra các bản sao từ bộ đệm tới người sử dụng cuối. Truy cập theo luồng được sử dụng bởi các mô đun lập chỉ mục và mô đun phân tích tập hợp để xử lí và phân tích một số lượng lớn các trang. Do Web trao đổi rất nhanh nên kho lưu trữ cần được điều khiển với khả năng biến đổi cao. Khi nhận các phiên bản từ các trang Web từ Crawler, phần không gian bị chiếm gữi bởi phiên bản được phục hồi thông qua việc nén và tổ chức lại. Hơn nữa, phải tránh sự xung đột giữa việc xử lý cập nhật và các ứng dụng truy cập trang. Ngoài ra các trang quá hạn thì kho lưu trữ không được thông báo, vì thế kho lưu trữ phải có một kĩ sảo để dò xét các và rời các trang đã quá hạn. Để thiết kế kho lưu trữ Web phân tán sẽ có ba vấn đề chính tác động tới đặc thù và khả năng thực hiện của kho lưu trữ. 2.2.1.Sự phân tán trang theo các nút: Các trang có thể được phân bố tới các nút sử dụng một số chiến lược khác nhau. Ví dụ, với chiến lược phân tán đồng bộ, tất cả các nút được đối xử tương tự nhau. Một trang đã cho có thể được phân bố tới bất kỳ nút nào trong hệ thống không phụ thuộc vào giá trị nhận dạng của nó. Các nút sẽ lưu trữ các phần của tập hợp tương ứng với khả năng lưu trữ của nó. Ngược lại, với chiến lược phân bố băm, sự phân bố các trang tới các nút sẽ phụ thuộc vào giá trị nhận dạng của trang. Trong trường hợp này, giá trị nhận dạng trang sẽ được băm cho ta một giá trị nhận dạng nút và trang đó sẽ được phân bố tới nút tương ứng. 2.2.2.Các phương pháp tổ chức trang vật lý : Trong một nút đơn có 3 hoạt động có thể xảy ra là, thêm/chèn một trang, truy cập luồng trang tốc độ cao, truy cập trang ngẫu nhiên. Tổ chức trang vật lí tại mỗi nút là xác minh xem một nút hỗ trợ các hoạt động này tốt như thế nào. Có một vài sự lựa chọn cho việc tổ chức trang. Cho ví dụ tổ chức dựa trên việc băm sẽ coi mỗi đĩa như là một tập các bucket băm, mà mỗi phần tử đủ nhỏ để lấy đầy trong bộ nhớ. Các trang được phân bố trên các butkets băm phụ thuộc vào giá trị nhận dạng của nó. Do các trang thường xuyên được thêm vào nên tổ chức theo cấu trúc bản ghi sẽ thuận lợi. Trong trường hợp này toàn bộ đĩa được coi như là các bản ghi liên tiếp nhau và các trang thêm vào sẽ được nối vào cuối. Truy cập ngẫu nhiên được hỗ trợ bởi việc sử dụng bảng chỉ mục B- Tree để giá trị các ánh xạ nhận dạng các trang tới các vị trí vật lý trên đĩa, chúng ta cũng có thể đưa ra một cách tổ chức là sự kết hợp của băm và bản ghi, trong đó việc lưu trữ được chia thành các phần liên tiếp, các trang được băm thành các phần và mỗi phần được tổ chức giống như một File có cấu trúc bản ghi. Do đó mà mô hình bản ghi làm việc rất tốt ngoại trừ trường hợp đòi hỏi nhiều truy cập ngẫu nhiên. 2.2.3. Các chiến thuật cập nhật Việc thiết kế chiến thuật cập nhật cho một kho lưu trữ trang sẽ phụ thuộc vào các đặc thù của Crawler và Crawler có thể được xây dựng theo ít nhất là hai cách: a. Chế độ khối hoặc chế độ đồng đều : Crawler với chế độ khối được thực hiện một cách chu kỳ và cho phép thu hồi với lượng thời gian nào đó sau đó sẽ dừng lại. Khi đó các kho lưu trữ sẽ nhận sự cập nhật cho một số lượng nhất định cho một số ngày trong tháng. Ngược lại, một Crawler đồng đều (Steady) luôn luôn chạy và không dừng, liên tục cập nhật và cung cấp các trang mới tới kho lưu trữ. b. Thu hồi cục bộ hay toàn phần: Một Crawler chế độ khối có thể được định cấu hình để thực hiện một chiến lược thu hồi toàn phần tại mọi thời gian nó chạy hoặc chỉ thu hồi một số lượng cố định các trang hoặc các Site. Trong trường hợp đầu các trang từ đợt thu hồi mới thay thế hoàn toàn tập các trang cũ đang tồn tại trong kho. Trong trường hợp thứ hai, tập hợp mới được tạo ra bởi việc áp dụng sự cập nhật của Crawler cục bộ tập hợp đang tồn tại. Phụ thuộc vào kho lưu trữ này chúng ta có thể chọn lựa kiểu thực hiện hoặc là cập nhật tại chỗ hoặc là cập nhật có màn che (shadowing). Với kiểu cập nhật tại chỗ, thì các trang nhận được từ Crawler có thể được tích hợp một cách trực tiếp vào tập dữ liệu đang tồn tại, cũng có thể là thay đổi phiên bản cũ. với kiểu Shadowing thì các trang nhận được từ quá trình Crawler sẽ được lưu trữ một cách riêng biệt với tập đang tồn tại và được cập nhật cũng được thực hiện một bước riêng rẽ. như được chỉ ra trong hình 10, các nút đọc chứa đựng tập đang tồn tại và sử dụng để phục vụ tất cả các yêu cầu truy nhập theo luồng hay ngẫu nhiên. Các nút cập nhật lưu trữ các trang nhận được trong suốt quá trình crawl sau cùng. Đặc thù hấp dẫn của shadowing đó là sự tách biệt hoàn toàn giữa cập nhật và truy cập đọc. Một nút lưu trữ đơn không bao giờ phải đồng thời điều khiển việc thêm và tìm kiếm một trang. Điều này tránh được sự xung đột, nâng cao hiệu suất và thực hiện đơn giản hơn. Tuy nhiên, sẽ có một thời gian trễ từ khi có Crawler tìm thấy một trang và trang đó có hiệu lực cho việc truy cập, shadowing có thể làm giảm độ tươi của tập hợp. Kho lưu trữ Standford Webbase: Để minh họa tất cả các phần tử trong kho được kết hợp với nhau như thế nào, chúng ta sẽ được làm. Kho lưu trữ WebBase là một hệ thống lưu trữ file phân tán kết hợp với Stanford WebCawler. Kho lưu trữ hoạt động thông qua một nhóm các nút lưu trữ nối kết bởi một mạng truyền thông tốc độ cao. Kho lưu trữ sử dụng một máy quản lý nút để giám sát các nút lưu trữ cá nhân và tập hợp các thông tin trạng thái (ví dụ hư không gian trống, việc tải, việc phân đoạn, một số yêu cầu truy cập còn tồn tại). Quản lý nút sẽ sử dụng các thông tin này để điều khiển các hoạt động của kho lưu trữ và lập biểu việc cập nhật cùng với các yêu cầu truy cập trên mỗi nút. Nót ®äc Crawler nút quản lý LAN Indexer Analyst Nót cËp nhËt H×nh 10: KiÕn tróc kho l­u tr÷ Mỗi trang trong kho được phân bố một giá trị định danh duy nhất, nhận được từ một việc tính toán một Signature của URL kết hợp với trang đó. Tuy nhiên một giá trị URL có thể được diễn tả dưới nhiều dạng xâu văn bản khác nhau. Ví dụ http:// WWW.STANFORD.EDU:80/ và http:// www.stanford.edu:80/ diễn tả cùng một trang Web nhưng sẽ cho ta các giá trị Signature khác nhau. Để tránh vấn đề này, URL phải được chuẩn hóa và các giá trị định danh được tính toán như một signature của URL chuẩn này.Do Stanford Web Crawler là một crawler chế độ khối nên kho lưu trữ WebBase sử dụng kỹ thuật Shadowing. Nó có thể sử dụng các phương pháp khác để tổ chức trang và các chiến lược phân tán khác trên các nút đọc và các nút cập nhật. vì thế, các nút cập nhật có thể nâng cao hiệu suất thêm các trang còn các nút đọc nâng cao khả năng đọc. Như vậy: Kho lưu trữ trang là một nội dung quan trọng trong kiến trúc tìm kiếm Web. Nó phải hỗ trợ một cách hiệu quả các phép truy cập khác nhau đối với các mẫu của bộ công cụ truy vấn (truy cập ngẫu nhiên) và các mô đun lập chỉ mục (truy cập theo luồng). Nó cũng phải sử dụng một chiến thuật cập nhật phù hợp với các đặc thù của Crawler. Lập chỉ mục Các mô đun lập chỉ mục và mô đun phân tích tập hợp đã xây dựng lên đủ loại bảng lập chỉ mục trên tập hợp các trang. mô đun lập chỉ mục xây dựng hai bảng chỉ mục cơ bản: Đó là bảng chỉ mục văn bản(cho nội dung) và bảng chỉ mục cấu trúc (cho liên kết). Môđun phân tích tập hợp sử dụng hai bản chỉ mục cơ bản này cùng với các trang trong kho lưu trữ để xây dựng lên các bảng chỉ mục tiện ích khác. Sau đây, em trình bày một cách ngắn gọn từng loại bảng chỉ mục, chủ yếu là tập chung vào cấu trúc và phương pháp sử dụng chúng. * Lập chỉ mục văn bản: Mặc dù các kỹ thuật dựa trên các liên kết đã nâng cao chất lượng và độ chính xác của kết quả tìm kiếm, nhưng tìm kiếm dựa trên văn bản (chẳng hạn tìm kiếm các trang chứa đựng từ khóa) vẫn tiếp tục phương pháp chính để xác định các trang liên quan tới vấn đề đang được truy vấn. Bảng chỉ mục văn bản hỗ trợ cho việc tìm kiếm có thể được thực hiện sử dụng bất kỳ phương pháp truy cập truyền thống nào để tìm kiếm trên toàn tập tài liệu như các file Signature, các file Inverted hoặc các bảng chỉ mục Inverted. Bảng Inverted là cấu trúc truyền thống được lựa chọn cho Web. *Bảng chỉ mục tiện ích: số lượng kiểu bảng chỉ mục tiện ích được xây dựng bởi mô đun phân tích tập hợp phụ thuộc vào nét đặc trưng của công cụ truy vấn và các loại thông tin cần hỗ trợ cho quá trình sắp xếp. Cho ví dụ, một công cụ truy vấn cho phép tìm kiếm bị giới hạn trong một site hoặc là một miền cụ thể (chẳng hạn WWW.stanford.edu) sẽ có lợi nhuận từ một bảng chỉ mục site ánh xạ mỗi tên miền tới một danh sách các trang của miền đó. Tương tự, chúng ta có thể sử dụng các thông tin hàng xóm từ bảng chỉ mục liên kết để hỗ trợ cho thuật toán lặp trong việc tính toán và lưu trữ PageRank kết hợp với mỗi trang một cách dễ dàng. * Bảng chỉ mục liên kết: Muốn xây dựng một bảng chỉ mục liên kết thì các phần được thu hồi trên Web được mô hình hóa như một đồ thị với các cạnh và các nút. Mỗi nút trong đồ thị tương ứng với một trang Web, mỗi cạnh có hướng từ A đến B diễn tả liên kết siêu văn bản trong trang A trỏ tới trang B. Một bảng chỉ mục cho cấu trúc liên kết phải là một diễn tả mở rộng và hiệu quả của đồ thị này. Các thông tin cấu trúc phổ biến nhất được sử dụng trong tìm kiếm đó là các thông tin về hàng xóm. Chẳng hạn cho trang P, hãy tìm kiếm một tập các trang được P trỏ tới (liên kết đi ra) hoặc một tập các trang trỏ tới P(liên kết đi vào). Cấu trúc danh sách liền kề của đồ thị Web đầu tiên và của đồ thị Web đã được đảo có thể cung cấp phép truy cập tới các thông tin hàng xóm một cách có hiệu quả. Các thuộc tính cấu trúc khác của đồ thị Web có thể được đưa ra một cách dễ dàng từ những thông tin cơ bản lưu trữ trong danh sách liền kề. Cho ví dụ, khái niệm về các trang anh em thường được sử dụng làm cơ sở cho việc tìm kiếm các trang liên quan với trang đã cho. Thông tin anh em có thể được đưa ra một cách dễ dàng từ một cặp danh sách liền kề. Còn các đồ thị với hàng trăm hoặc hàng nghìn nút có thể được diễn tả một cách hiệu quả dưới bất kỳ dữ liệu được biết nào. Tuy nhiên làm công việc đó đối với đồ thị có vài triệu nút là một thách thức về công nghệ. Cấu trúc của bảng chỉ mục ngược Bảng chỉ mục ngược (Inverted) cho một tập các trang Web bao gồm một tập các danh sách Inverted được sắp xếp theo vị trí từ trong văn bản. Trong trường hợp đơn giản nhất, vị trí sẽ bao gồm giá trị nhận dạng trang và vị trí của từ trong trang. Tuy nhiên thuật toán tìm kiếm thường phải sử dụng những thông tin được thêm vào về từ trong trang Web. Chẳng hạn, từ xuất hiện dưới dạng chữ in đậm (gắn thẻ ), hoặc nằm trong phần đầu (gắn cờ hoặc ), hoặc các từ có thể được đánh trọng số hỗ trợ cho việc sắp xếp này. Để thực hiện được điều đó phải có một trường trọng tải được thêm vào tới các phần tử vị trí.Trường trọng tải mã hóa bất kỳ thông tin cần thiết nào cho mỗi từ. Với một từ chỉ mục w và vị trí tương ứng l lúc này ta có một cặp (w,l) và được gọi là posting cho từ w.Cộng với danh sách inverted, hầu hết các bảng chỉ mục cho văn bản đều duy trì một cuốn từ điển. Cuốn từ điển này liệt kê tất cả các từ xảy ra trong bảng chỉ mục cùng với sự thống kê của từ đó. 2.3.2 Một số thách thức: Khi xây dựng một bảng chỉ mục ngược bao gồm việc xử lý từng trang để trích ra các posting, sắp xếp các posting đầu tiên theo từ rồi sau đó theo vị trí và cuối cùng đưa ra các posting đã được sắp xếp như một tập hợp của các danh sách inverted trên đĩa. Đối với các tập hợp tĩnh và ít quan hệ như trong môi trường tìm kiếm thông tin truyền thống, thì thời gian xây dựng bảng chỉ mục là không quan trọng. Tuy nhiên, đối với tập dữ liệu Web rộng lớn, thì mô hình xây dựng bảng chỉ mục trở thành không thể quản lý và đòi hỏi nguồn tài nguyên quá lớn, thông thường mất nhiều ngày để hoàn thành. Thêm vào nữa, nội dung của trang Web thay đổi liên tục do đó việc thu hồi một cách tuần hoàn và xây dựng lại bảo chỉ mục là cần thiết để duy trì độ tươi. Việc xây dựng lại bảng chỉ mục là cần thiết bởi vì những kỹ thuật cập nhật tiên tiến nhất cũng trở nên nghèo nàn khi ta áp dụng nó với tập dữ liệu cực lớn và thay đổi liên tục như Web. Cuối cùng khuôn dạng lưu trữ của bảng chỉ mục Inverted phải được thiết kế một cách cẩn thận. Một bảng chỉ mục nén cải tiến khả năng truy vấn bằng việc cho phép từng phần của bảng chỉ mục có thể trở thành bộ đệm trong bộ nhớ. Do đó, phải có sự thỏa hiệp giữa hiệu suất này và tổng chi phí giải nén tại thời gian truy vấn. Để thu được sự cân bằng đã trử thành một thách thức lớn. Chia bảng chỉ mục Để xây dựng bảng chỉ mục ngược cho Web đòi hỏi một kiến trúc bảng chỉ mục phân tán và rộng lớn. Có hai chiến thuật cơ bản chỉ mục ngược dựa trên tập hợp các nút. Tổ chức dạng tập tin đảo (Inverted file ) cục bộ (IFL), mỗi nút tương ứng với một tập con các trang phân biệt trong tập hợp. Công việc tìm kiếm sẽ được quảng bá tới tất cả các nút, mỗi nút sẽ trả lại danh sách chứa đựng giá trị nhận dạng của các trang chứa đựng từ đang được tìm kiếm. Tổ chức dạng Inverted File toàn cục (IFG) sẽ chia theo các từ được lập chỉ mục, vì thế mỗi dịch vụ truy vấn sẽ chỉ lưu trữ các danh sách Inverted cho một tập các từ trong tập hợp. Ví dụ, trong một hệ thống có hai dịch vụ truy vấn A và B có thể lưu trữ các danh sách Inverted cho những từ bắt đầu với ký tự nằm trong phạm vi [a- q], còn B có thể lưu trữ các danh sách Inverted cho những từ còn lại. Vì thế, một yêu cầu truy vấn từ “process” sẽ chỉ đòi hỏi hệ phục vụ A. Trang Web Bé ph©n phèi Bé lËp chØ môc C¸c dÞch vô truy vÊn Bé Thèng kª B¶ng chØ môc Tr¹ng th¸i 2 Tr¹ng th¸i 1 D·y s¾p xÕp trung gian H×nh 11: M« h×nh lËp chØ môc Web Đặc thù quan trọng của chiến thuật IFL, như là khả năng phục hồi lỗi và giảm việc tải trên mạng, làm cho nó trở thành lý tưởng trong môi trường tìm kiếm Web. Các đánh giá về hiệu suất trong cũng chỉ ra rằng tổ chức IFL đã sử dụng nguồn tài nguyên một cách hiệu quả và cung cấp một truy vấn tốt trong hầu hết các trường hợp. Sắp xếp và phân tích liên kết Như được chỉ trong hình 3, công cụ truy vấn tập hợp các từ tìm kiếm từ người sử dụng và thu hồi các trang có nội dung liên quan. Có hai lý do chính giải thích tại sao các kỹ thuật thu hồi thông tin truyền thông không đủ hiệu quả cho việc sắp xếp các kết quả truy vấn. Đầu tiên là do Web quá lớn, với sự giao động về số lượng, chất lượng và kiểu loại thông tin được diễn tả trong mối trang Web. Vì vậy mà có rất nhiều trang chứa đựng các từ tìm kiếm nhưng chúng lại ít liên quan tâm thậm chí là không liên quan tới nội dung đang được tìm kiếm. Thứ hai, có rất nhiều trang Web không đủ để tự diễn tả nó muốn nói về vấn đề gì, do vậy nếu ta áp dụng kỹ thuật IR để kiểm tra nội dung của một trang thì sẽ không cho một câu trả lời tốt một ví dụ thông thường để minh họa cho vấn đề này là khi ta đánh từ tìm kiếm “search engines” các trang chủ của hầu hết bộ công cụ tìm kiếm chính đều không chứa đựng văn bản “search engines”. Hơn nữa các trang Web thường xuyên thêm vào các từ lừa dối vì thế chúng sẽ được sắp xếp cao hơn bởi bộ công cụ tìm kiếm (spaming). Do đó các kỹ thuật chỉ dựa trên nội dung của một trang Web sẽ đưa ra những quyết định lệch lạc. Cấu trúc của Web sẽ cho thấy các thông tin rất quan trọng, và nó có thể hỗ trợ trong việc lọc và sắp xếp các trang Web. Cụ thể là một liên kết từ trang A tới trang B cho ta biết trang B sinh ra từ trang A. Một vài thuật toán đã được đề xuất để khai thác cấu trúc liên kết này, không chỉ cho việc tìm kiếm từ khóa mà còn cho cả những công việc khác như vậy việc xây dựng kiến trúc Yahoo một cách tự động, hoặc nhận dạng nhóm truyền thống trên Web. Hiệu quả của thuật toán này cao hơn các thuật toán IR bởi chúng sử dụng nhiều thông tin hơn. Để đưa ra những thông tin lựa chọn cho một trang Web, sau đây em xin mô tả hai kỹ thuật dựa trên các cấu trúc liên kết – PageRanK và HITS. 2.4.1 Phương pháp PageRank Page và Brin đưa ra một mô hình sắp xếp tổng cục, được gọi là PageRank, để làm nổi bật khái niệm “quan trọng” của một trang. Chẳng hạn như trang chủ Yahoo có cảm giác là quan trọng hơn trang chủ của nhóm cơ sở dữ liệu Stanford. Sự khác biệt này được phản ánh trong số lượng các trang trỏ tới hai trang này, có nghĩa là có nhiều trang trỏ tới trang chủ Yahoo hơn trang chủ của nhóm cơ sở dữ liệu Stanford. Vì thế sự sắp xếp của trang A có thể định nghĩa như số lượng trang Web trỏ tới A, và có thể được sử dụng để sắp xếp các kết quả của truy vấn. PageRank mở rộng ý tưởng trên bởi việc đưa thêm vào khái niệm một trang được Yahoo trỏ tới sẽ quan trọng hơn một trang không biết nào đó trỏ tới. Do đó ta có định nghĩa của PageRank là đệ quy - độ quan trọng của một trang vừa phụ thuộc vừa ảnh hưởng tới độ quan trọng của trang khác. 1/ Tính PageRank đơn giản Định nghĩa về một PageRank đơn giản, và tham khảo các lĩnh vực tính toán của nó trước khi đưa ra một phép biến đổi thực tế. Định nghĩa các trang Web là 1,2,3,...,m. N(i) là số lượng liên kết đi ra từ trang i và B(i) là số lượng trang trỏ tới trang i. Chúng ta giả sử rằng các trang Web hình thành lên một đồ thị liên kết mạnh (mọi trang có thể đi tới từ bất kỳ một trang nào khác). Giá trị PageRank đơn giản của trang i được định nghĩa là r(i): Việc chia cho N(j) muốn nói rằng các trang trỏ tới trang i được phân bố giá trị sắp xếp của chúng một cách đồng đều tới tất cả các trang chúng trỏ tới. Theo ngôn ngữ đại số tuyến tính, ta có r = ATr, trong đó r là vector m´1 và các phần tử aij của ma trận A được cho bởi ai,j = 1/N(i) nếu trang i trỏ tới trang j và aij = 0 nếu ngược lại. Vì thế vector PageRank r là eigenvector của ma trận AT tương ứng với eigenvector 1. Vì đồ thị là liên kết mạnh nên có thể chỉ ra rằng 1 là eigenvector của AT và eigenvector r là duy nhất.(khi thực hiện chuẩn hóa là vector là không âm). * Mô hình lướt ngẫu nhiên Từ định nghĩa của PageRank đơn giản dẫn tới một sự diễn giải dựa trên các cuộc dạo chơi ngẫu nhiên thì được gọi là mô hình lướt ngẫu nhiên. Chúng ta hình dung ra một người đang lướt các trang Web bằng việc kích ngẫu nhiên vào các liên kết trên các trang được thăm. Việc lướt ngẫu nhiên này cũng tương tự như việc đi bộ trên một đồ thị liên kết cơ bản. Bài toán đi bộ trên đồ thị là một bài toán tổ hợp đã được nghiên cứu. Nó có thể được chỉ ra rằng vector PageRank r là tương đương với phân bố xác suất thống kê của việc đi bộ ngẫu nhiên. Vì thế, PageRanK của một trang tương ứng với tần số mà một người lướt ngẫu nhiên để thăm nó. * Các tính toán của PageRank Như đã trình bày ở mục trên, việc tính toán PageRank tương đương với việc tính toán eigenvector chính của ma trậ AT. một trong những phương pháp đơn giản nhất để tính toán eigenvector chính của ma trận đó là sử dụng các bước lặp lũy thừa. Trong một bước lặp lũy thừa, một vector ban đầu có giá trị tùy ý được nhân nhiều lần với một ma trận đã cho tới khi nó hội tụ về eigenvector chính. Bước lặp lũy thừa cho việc tính toán PageRank được cho như sau: s <- vector ngẫu nhiên bất kỳ r <- AT ´ s Nếu || r – s || < e thì kết thúc . r là vector PageRank 2 4 5 R2 = 0.142 3 R2 = 0.101 R2 = 0.154 1 R2 = 0.313 R2 = 0.290 Hình 12(b) PageRank với d = 0.8 4 . s < - r, goto 2 2 4 5 R2 = 0.286 3 R2 = 0.143 R2 = 0.286 1 R2 = 0.143 R2 = 0.143 Hình 12 (a ) PageRank đơn giản Hình 2.4.1(a) đã minh họa các giá trị PageRanK cho một đồ thị đơn giản. Nó thật dễ dàng để nhận ra rằng sự phân phối sắp xếp này thỏa mãn định nghĩa của PageRank. Chẳng hạn, nút 2 có giá trị sắp xếp là 0.286 và có hai liên kết đi ra. Một nửa giá trị sắp xếp (0.143) đi tới nút 1 và một nửa tới nút 3. Do nút 3 không có thêm một “liên kết tới” nào khác nữa nên giá trị sắp xếp của nó được nhận từ chính nút 2 và bằng 0.143. Nút 1 nhận 0.143 từ 2 và 0.143/2 từ 3 cộng với 0.143/2 từ nút 5 cho ta tổng là 0.286. để ý rằng nút 1 có thứ tự sắp xếp cao hơn bởi vì bất kỳ một người nào thăm nút 1 cũng sẽ phải thăm nút 2. Lưu ý rằng tổng giá trị sắp xếp của tất cả các nút bằng 1. 2/ Tính PageRank thực tế PageRank đơn giản chỉ được tính cho đồ thị liên kết mạnh. trong khi đó, môi trường Web không phải là một liên kết mạnh. Cụ thể là rank sinks và rank leaks. Bất kỳ nhóm các liên kết mạnh nằm trong đồ thị Web mà không có một liên kết nào đi ra từ chúng hình thành nên rank sink. Một trang đơn lẻ không có bất kỳ một liên kết đi ra nào hình thành nên rank leak. Mặc dù rank leak là trường hợp đặc biệt của rank sink nhưng rank leak sẽ gây ra một loại vấn đề khác. Trong trường hợp rank sink các nút không nằm trong sink nhận giá trị sắp xếp 0, nghĩa là chúng ta không thể phân biệt mức độ quan trọng của những nút như vậy. Ví dụ, giả sử trong hình 2.4.1(a) chúng ta rời liên kết 5-> 1, khi đó các nút 4 và 5 hình thành nên một sink. Một người lướt Web ngẫu nhiên khi thăm đồ thị này cuối cùng sẽ bị mắc kẹt trong các nút 4 và 5 vì thế các nút 1,2,3 sẽ có giá trị sắp xếp là 0 và các nút 4,5 có giá trị sắp xếp là 0.5. Còn một trong các trường hợp khác, bất kỳ một sắp xếp nào đi tới rank leak sẽ bị mất mãi mãi. Cho ví dụ, trong hình 2.4.1(a), nếu chúng ta rời nút 5(và tất cả các liên kết kết hợp với nó), nút 4 sẽ trở thành leak. leak này sẽ gây cho tất cả các giá trị cuối cùng đều bằng 0. Có nghĩa là một người lướt Web ngẫu nhiên cuối cùng sẽ đi tới nút 4 và không bao giờ trở lại nữa. Page và Brin đã gợi ý hai cách giải quyết vấn đề này. Thứ nhất là họ rời tất cả các nút leak có bậc ra bằng 0. Thứ hai để giải quyết vấn đề sink, họ đưa ra một hệ số phân rã d ( 0 < d <1)trong công thức PageRank. Ở định nghĩa đã được biến đổi này, chỉ có hệ số d của giá trị sắp xếp của một trang được phân bố giữa các nút nó trỏ tới. Giá trị sắp xếp còn lại được phân bố đồng đều cho tất cả các trang trên Web. Vì thế công thức PageRank có dạng Trong đó m là tổng số lượng các nút trong đồ thị. Chú ý rằng công thức PageRank đơn giản là trường hợp đặc biệt khi d =1. Trong mô hình lướt ngẫu nhiên, sự thay đổi có thể làm cho người lướt Web thỉnh thoảng sẽ gặp những điều tẻ nhạt và có thể nhảy đến một trang ngẫu nhiên trên Web (thay cho việc đi tới một liên kết ngẫu nhiên từ trang Web hiện thời). Hệ số phân rã d chỉ cho biết mức độ thường xuyên gặp điều phiền phức của người lướt Web như thế nào. Hình 12(b) chỉ ra mô hình PageRank đã được biến đổi ( với d = 0.8) cho đồ thị của hình 12(a) khi ta rời liên kết 5-> 1. Nút 4 và 5 có giá trị sắp xếp cao hơn các nút khác cho biết rằng những người lướt Web sẽ tập chung vào các nút 4 và 5. Tuy nhiên các nút khác có giá trị sắp xếp khác 0. 3/ Sử dụng PageRank cho tìm kiếm theo từ khóa Page và Brin diễn tả một bộ công cụ tìm kiếm được phát triển tại Stanford gọi là Google (Cái mà sau đó trở thành công cụ tìm kiếm Gooogle.com). Google sử dụng cả các kỹ thuật IR và PageRank để trả lời các truy vấn từ khóa. Cho một truy vấn, Google tính toán tỷ lệ IR cho tất cả các trang chứa đựng từ tìm kiếm. Tỷ lệ IR được kết hợp với PageRank của các trang này để xác định bảng sắp xếp cuối cùng cho truy vấn. 4/ Các vấn đề trong tính toán Để cho bước lặp lũy thừa được thực hiện, nó không cần chỉ hội tụ tới PageRank, mà còn phải thực hiện rất ít bước lặp. một cách lý thuyết, lặp sự hội tụ của bước lặp lũy thừa cho một ma trận phụ thuộc vào eigenvalue gap (được định nghĩa như sự khác biệt giữa mô đun của hai giá trị lớn nhất của hai ma trận đã cho). Page và Brin cho rằng điều này là đúng và bước lặp lũy thừa hội tụ một cách nhanh chóng (trong khoảng 100 bước lặp). Bên cạnh đó cần chú ý rằng, chúng ta đang quan tâm tới thứ tự liên quan của các trang dựa vào PageRank (thứ tự này được sử dụng để sắp xếp các trang) hơn là giá trị thực của PageRank, vì thế chúng ta có thể kết thúc bước lặp khi thứ tự các trang trở nên cố định. Thực nghiệm chỉ ra rằng thời gian đưa ra thứ tự các trang dựa vào độ hội tụ của PageRank nhanh hơn khi ta đi tính giá trị thực của PageRank. 2.4.2 Phương pháp HITS (Hypertext Induced Topic Search) Thuật toán này được đề suất đầu tiên bởi Kleinberg. Ngược lại với đặc trưng phân phối giá trị sắp xếp trên toàn cục tới mọi trang trong kỹ thuật PageRank, thuật toán HITS là một truy vấn phụ thuộc vào kỹ thuật sắp xếp. Hơn nữa, thay cho việc chỉ đưa ra một tỷ lệ sắp xếp, thuật toán HITS đưa ra hai tỷ lệ: Tỷ lệ Hub và tỷ lệ Authority, các trang Hub và Authority liên quan đến nhau như thế nào? Các trang Hub thì trỏ tới nhiều trang Authority. Ngược lại, một trang được gọi là Authority tốt khi đó được trỏ tới bởi nhiều trang Hub. Vì thế có một mối tăng cường lẫn nhau giữa Hub và Authority: Trang Authority là trang được trỏ tới bởi nhiều trang Hub và các trang Hub là các trang trỏ tới nhiều Authority. Từ các định nghĩa này dẫn đến thuật toán HITS. Thuật toán HITS: Ý tưởng cơ bản của thuật toán HITS là xác định một đồ thị con của Web và áp dụng sự phân tích liên kết trên đồ thị con này để xác định các Authority và các Hub đối với truy vấn đã cho. Đồ thị con này phụ thuộc vào truy vấn của người sử dụng. Sự chọn lựa đồ thị con (cụ thể là vài nghìn trang ) không chỉ tập chung vào việc phân tích liên kết trên hầu hết các phần liên quan trong Web, mà đồng thời cũng giảm số lượng công việc cho pha tiếp theo (do việc chọn lựa đồ thị con và phân tích nó đều được thực hiện trong thời gian truy vấn nên nó rất quan trọng để hoàn thành chúng trong một thời gian ngắn). * Xác định đồ thị con tập trung : Đồ thị con tập chung được sinh ra từ tập gốc R. Một tập ngẫu nhiên các trang chứa đựng xâu truy vấn đã cho và mở rộng tập gốc tới các trang là hàng xóm của R. Bảng chỉ mục văn bản có thể được sử dụng để tìm kiếm tập gốc. Thuật toán tính toán đồ thị tập trung được như sau: 1. R<- tập t trang chứa đựng từ truy vấn (sử dụng bảng chỉ mục văn bản) 2. S<- R 3. for mỗi trang p Î R (a) Gộp tất cả các trang mà p trỏ tới vào trang S (b)gộp (cho tới giá trị lớn nhất d trang) tất cả các trang trỏ tới p vào trong S 4. Đồ thị đem lại từ S là đồ thị con tập chung Thuật toán có đầu vào là trang truy vấn và hai tham số t và d. Tham số t giới hạn kích thước tập gốc, tham số d giới hạn số lượng các trang được thêm vào đồ thị con tập chung. (các điều khiển này giới hạn sự ảnh hưởng của một trang vô cùng phổ biến như WWW.yahoo.com khi nó xuất hiện trong tập gốc). Một tập mở rộng S sẽ chứa nhiều Authority vì rằng một Authority được trỏ bởi ít nhất một vài trang trong tập gốc. Tương tự như vậy, cũng có nhiều Hub tốt nằm trong S. * Phân tích liên kết: Thuật toán HITS lợi dụng thuộc tính tăng cường lẫn nhau để xác định các Hub và các Authority từ tập mở rộng S (pha này không cần biết nội dung được truy vấn ). Tập các trang trong đồ thị con tập trung S được định nghĩa là 1,2,...n. B(i) là tập các trang trỏ tới trang i, F(i) là tập các trang mà trang i trỏ tới. Thuật toán phân tích liên kết đưa ra tỷ lệ Authority và hub hi và tỷ lệ Hub hi cho mỗi trang trong tập S. Để bắt đầu, các tỷ lệ của Authority và Hub được khởi tạo với các giá trị tùy ý. Thuật toán có tính chất lặp và nó thực hiện hai loại hoạt động trong mỗi bước lặp, gọi là I và O. trong hoạt động I, tỷ lệ Authority của mỗi trang cập nhật tổng các tỷ lệ Hub của các trang trỏ tới nó. Trong hoạt động O, tỷ lệ Hub của mỗi trang cập nhật tổng các tỷ lệ Authority của các trang nó trỏ tới. Có nghĩ là: Bước I: Bước O: Các bước I và O chỉ ra rằng một Authority tốt sẽ được trỏ tới nhiều Hub tốt và nhiều hub tốt sẽ trỏ tới nhiều Authority tốt. Cũng chú ý rằng một trang có thể là (và cũng thường là) một trang hub đồng thời là trang authority. Thuật toán Hub chỉ tính toán hai tỷ lệ cho mỗi trang, tỷ lệ Hub và tỷ lệ Authority. Thuật toán lặp đi lặp lại các bước I và O, với một sự chuẩn hóa, cho đến khi các tỷ lệ hub và authority hội tụ: 1. Khëi t¹o víi c¸c gi¸ trÞ tuú ý 2. LÆp cho tíi khi héi tô (a) ¸p dông ho¹t ®éng I (b) ¸p dông ho¹t ®éng O (c) chuÈn ho¸ vµ 3.KÕt thóc Một ví dụ của việc tính toán Hub và Authority được chỉ ra trong hình 13. Tỷ lệ Authority của nút 5 có thể thu được bằng việc thêm vào các tỷ lệ Hub của các nút trỏ tới nút 5( ví dụ 0.408 +0.816 + 0.408) và chuẩn hóa giá trị này bởi các tỷ lệ Hub kết hợp ( ví dụ (0.408)2 + (0.816)2 +(0.408)2). h= 0 a= 0.408 4 h= 0 a= 0.816 5 1 h= 0.408 a= 0 2 h= 0.816 a= 0 3 h= 0.408 a= 0 h= 0 a= 0.408 6 Hình 13: Thuật toán HITS Các giá trị Hub và Authority có những thuộc tính toán học thú vị giống như trong trường hợp của PageRank. Với Am x m là ma trận liền kề của đồ thị con tập chung. Phần tử thứ (ij) của A bằng 1 nếu trang i trỏ tới trang j và bằng 0 nếu ngược lại. Với A là các vector fias trị Authority [a1,a2,........an] và h là vector các giá trị [h1,h2,.........,hn ]. Các hoạt đọng I và O có thể biểu diễn a = Ah và h = AT a, sự biến đổi đơn giản đó chỉ ra rằng các tỷ lệ hội tụ cuối cùng của Hub và Authority thõa mãn a = c1A ATa và h = c2 AT Ah ( hằng số thêm vào giải thích cho bước chuẩn hóa ). Vì thế vector tỷ lệ authority và vector tỷ lệ Hub tương ứng là các eigenvector của các ma trận AAT và ATA. Thuật toán phân tích liên kết diễn tả ở trên là một bước lặp lũy thừa đơn giản nhân vector a và h là các eigenvector chính của AAT và ATA. Chỉ trong trường hợp của PageRank tỷ lệ hội tụ của các giá trị Hub và Authority mới phụ thuộc vào eigenvalue gap. Thứ tự của các trang Hub và Authority đưa ra bởi độ hội tụ của tỷ lệ hub và tỷ lệ Authority nhanh hơn việc tính chính xác các giá trị thực của chúng (khoảng 10 bước lặp). * Tìm kiếm các trang liên quan: Một vấn đề được đặt ra trong tìm kiếm từ khóa là khi một người đưa vào một số từ khóa, nhưng nó rất khó khăn cho họ khi chọn một số từ khóa diễn tả đúng nội dung đang quan tâm. Do đó các bộ công cụ đang tìm kiếm có thể hỗ trợ một kiểu truy vấn khác được gọi là tìm kiếm các trang liên quan, hoặc tìm kiếm bởi ví dụ. Trong kiểu truy vấn này, người tìm kiếm đưa vào một ví dụ mà cụ thể là một trang Web diễn tả phần nào đó thông tin mà anh ta đang tìm kiếm. Công cụ tìm kiếm sẽ thu hồi các trang Web tương đương với trang Web đã cho. Một truy vấn tìm kiếm liên quan có thể được đáp ứng với các kỹ thuật IR dựa trên độ tương quan văn bản. Tuy nhiên trên môi trường Web chúng ta có thể khai thác cấu trúc liên kết của chúng. Nếu một trang A trỏ đến hai trang B và C thì nó cho biết rằng B và C có liên quan. Lưu ý rằng thuật toán HITS hoàn toàn sử dụng thông tin Cocitation. Kleinberg đã gợi ý rằng một sự biến đổi đơn giản của thuật toán HITS có thể được sử dụng để hỗ trợ các truy vấn tìm kiếm liên quan. Dean và Henzing đưa ra hai thuật toán tìm kiếm liên quan, được đặt tên là thuật toán Companion là sự mở rộng ý tưởng của Kleinberg, và thuật toán Cocitation sử dụng việc đếm cocitation để xác minh các trang liên quan. Họ nhận thấy rằng cả hai thuật toán này thực hiện tốt hơn dịch vụ Nescape và thuật toán Conpanion là tốt nhất. * Phân lớp và biên soạn nguồn tài nguyên: Rất nhiều các công cụ tìm kiếm giống như Altavista và Yahoo có sự phân lớp kiến trúc của các trang Web. Người sử dụng có thể duyệt kiến trúc đó để xác định thông tin họ quan tâm. Các kiến trúc này được dịch bằng tay, các vấn đề về phân lớp tài liệu tự động dựa trên một vài ví dụ phân lớp đã được nghiên cứu IR. Chakrabarti, Dom và Indyk đã mở rộng các kỹ thuật IR để đưa thông tin ra siêu văn bản. Ý tưởng cơ bản là không chỉ sử dụng các từ trong tài liệu mà còn cả các phạm trù của các trang lân cận để phân loại. Họ đã chỉ ra một cách thực nghiệm rằng kỹ thuật của họ nâng cao độ chính xác của sự phân lớp. Một bài toán liên quan đã được nghiên cứu đó là quá trình biên dịch tài nguyên một cách tự động. Sự quan trọng trong trường hợp này đó là xác định các trang có chất lượng cao cho một phạm trù hay một chủ đề cụ thể nào đó. Thuật toán được gợi ý đó là sự biến đổi của thuật toán HITS sử dụng thông tin từ nội dung cộng với các mối liên kết. Tóm lại Cấu trúc liên kết của các trang Web chứa đựng rất nhiều thông tin hữu ích có thể được khai thác để hỗ trợ việc tìm kiếm theo từ khóa hay các công việc thu hồi thông tin khác trên Web. Chúng ta đã tham khảo hai kỹ thuật phân tích liên kết thú vị trong mục này. PageRank là một mô hình sắp xếp toàn cục được sử dụng để sắp xếp các kết quả tìm kiếm. Còn thuật toán HITS thì xác định một tập các trang Hub và các trang Authority đối với một truy vấn đã cho. Có rất nhiều hướng thú vị được đưa ra. Một trong những chiều hướng có triển vọng đó là nghiên cứu các nguồn thông tin khác như thế nào, ví dụ như các truy vấn bản ghi. Những chiều hướng nghiên cứu quan trọng khác đó là nghiên cứu các kỹ thuật phân tích văn bản xã hội và nâng cao nó cho tập dữ liệu siêu văn bản. Vậy, Để tìm kiếm thành công trên WWW là một trong những công việc cơ bản trong môi trường công nghệ thông tin ngày nay. Vì thế các bộ công cụ tìm kiếm ngày càng nâng cao khả năng trích dẫn các nguồn thông tin liên quan từ một số lượng tài liệu rất lớn. Và các bộ công cụ thực hiện điều này với một lượng dữ liệu đầu vào rất nhỏ thường chỉ là một hoặc hai từ khóa truy vấn. Trong hình 3 chúng ta đã được tham khảo các công cụ được đặt cùng nhau như thế nào. Các khối chức năng chính hình thành nên một kiến trúc cụ thể: Crawler lướt trên mạng để thu hồi các trang. Các trang này được lưu trữ một cách cục bộ, ít nhất cho đến khi chúng lập chỉ mục và phân tích. Công cụ truy vấn thu hồi các giá trị URL mà nhường như là liên quan tới truy vấn của người sử dụng. Một môđun Ranking cố gắng sắp xếp các giá trị URL sao cho những kết quả triển vọng nhất được đặt ở đầu. Nhóm các kỹ thuật này vẫn đòi hỏi một sự cố gắng trong thiết kế. Phần lớn sự phức tạp trong thiết kế và thực hiện bắt nguồn từ phạm vi rộng của Web. CHƯƠNG III THIẾT KẾ CÁC CÔNG CỤ HỖ TRỢ TÌM KIẾM THÔNG TIN TRÊN MẠNG Môđul lập chỉ mục là bước tiền xử lí trong bộ công cụ tìm kiếm thông tin, nó có thể lập chỉ mục cho hai dạng nguồn dữ liệu. thứ nhất, đó là file-system với đầu vào cho môđul là các file hoặc các thư mục chứa các file với đuôi mở rộng là: .html, .xml, .txt. Thứ hai, đó là một cơ sở dữ liệu WebBase với đầu vào cho môđul là một giá trị địa chỉ URL. Sau khi lập chỉ mục ta thu được một cơ sở dữ liệu bao gồm các bảng chỉ mục (Inverted File) chứa đựng từ đó và nhiều thông tin khác hỗ trợ cho quá trình tìm kiếm. Môđul tìm kiếm phân tích cú pháp truy vấn của người sử dụng và thực hiện tìm kiếm trên các bảng chỉ mục (là đầu ra của môđul trên) để đưa ra các tài liệu có liên quan tới truy vấn. Trong chương trình này em có đưa ra các giải pháp cũng như cấu trúc giữ liệu để giải quyết các dạng truy vấn: truy vấn một cụm từ, truy vấn Boolean, truy vấn meta, truy vấn với kí tự đại diện ( Wildcat ).Do truy vấn thường là rất ngắn nên số lượng tài liệu liên quan là rất lớn, do đó phải có một môđul thực hiện việc sắp xếp kết quả, sao cho tập kết quả đầu ra có độ liên quan giảm dần đối với truy vấn. Môđul sắp xếp này sử dụng các giá trị thống kê của các từ nằm trong bảng chỉ mục để tính toán độ liên quan của tài liệu. Trong chương này em cũng đưa ra các giải pháp và sự chọn lựa thuật toán cũng như cấu trúc dữ liệu để có được thời gian lập chỉ mục và tìm kiếm nhanh nhất, tài liệu đưa ra có mức độ liên quan tới truy vấn cao nhất đồng thời đáp ứng đựơc nhiều dạng của truy vấn. 3.1 MÔ ĐUN LẬP CHỈ MỤC 3.1.1 Khái niệm chỉ mục Đầu tiên, chúng ta tập trung tìm kiếm các truy vấn và thông báo các tài liệu chứa các từ trong truy vấn, số lần xuất hiện truy vấn trong mỗi tài liệu và thậm chí các vị trí chính xác trong mỗi văn bản. Cách tìm kiếm một truy vấn đơn giản nhất là quét liên tiếp văn bản. Việc tìm kiếm liên tiếp hoặc online là tìm sự xuất hiện của một mẫu trong văn bản khi văn bản không được tiền xử lý. Tìm kiếm online chỉ phù hợp với các văn bản nhỏ. Cách lựa chọn tìm kiếm thứ hai là xây dựng các cấu trúc dữ liệu cho văn bản ( gọi là bảng chỉ mục - index ) để tăng tốc độ tìm kiếm, phù hợp với việc xây dựng và duy trì các chỉ số khi tập văn bản là lớn và nửa tĩnh (semi- static).Trong phần này, em sẽ đưa ra hai kỹ thuật đánh chỉ số chính: Inverted File và Signature Files - đó là các kỹ thuật tìm kiếm dựa vào từ khác trong đó nhấn mạnh kỹ thuật Inverted Files - là sự lựa chọn hợp lý và có nhiều ứng dụng nhất hiện nay. 3.1.2. Các cấu trúc lưu chỉ mục 1/ Signature files Signature files sử dụng phương pháp mã hóa chồng nhau để tạo ra nhãn (signature) cho nhập tài liệu sẽ được chia thành khối logic, mỗi khối chứa đựng D từ phân biệt (đây là các từ không nằm trong StopList ). Mỗi từ cho ta một nhãn từ - kích thước F bít với m bít được thiết lập là 1 còn những bít còn lại là 0. Các nhãn từ được “OR” cùng nhau hình thành nền nhãn khối. Các nhãn khối nối với nhau tạo ra nhãn tài liệu. Vị trí của m bít được thiết lập là “1’’ được quyết định bởi các hàm băm. Ta có một ví dụ tạo nhãn: Từ Nhãn ------------------------------------------------------------ Free 001 000 110 010 Text 000 010 101 001 ------------------------------------------------------------ Free text 001 010 111 011 Hình 14: Một ví dụ tạo nhãn với mỗi khối logic có D= 2 từ, kích thước nhãn F = 12 bit, m= 4 bit Giả sử nhãn của một khối là B. để kiểm tra một từ có nằm trong tài liệu không, ta tiến hành xác định nhãn của từ đó, giả sử là W, sau đó thực hiện phép toán logic (W & B)đối với các khối trong tài liệu, nếu(W&B = W) thì từ có thể nằm trong khối đó. Một khái niệm quan trọng trong Signature Files là xác xuất “false drop’’ Fd , đó là xác suất mà phương pháp Signature cho ta những báo động có lỗi có nghĩa là từ không nằm trong văn bản. do đó xác suất False drop Fd là xác suất mà một khối được phương pháp Signature báo là chứa đựng từ tìm kiếm chia cho khối đó hiện thực không chứa tìm tìm kiếm. Signture Files là một ma trận nhị phân F x N, theo Stiassny, theo 1960 thì để xác suất False drop là nhỏ nhất thì mỗi hàng trong ma trận này sẽ chứa đụng khoảng 50% bít 1, và khi đó Fd = 2-m Trong hầu hết các trường hợp ma trận Signature được lưu một cách tuần tự theo các hàng, và được gọi là cấu trúc SSF (Sequential Sinature File) File v¨n b¶n Con trá File 0 1 ….. 0 1 1 …………….. 1 Nh·n F bit N Khèi Logic Hình 15: Cấu trúc file dang SSF Ta nhận thấy rằng thời gian xử lí đối với phương pháp này là tuyến tính với số lượng khoản tin N nằm trong cơ sở dữ liệu do đó nó sẽ trở nên chậm chạp đối với cơ sở dữ liệu lớn. vì thế phương pháp Signature chỉ sử dụng tốt trong một số môi trường như: - Trên PC nhưng với kích thước dữ liệu trung bình - Trên WORM (Write-Read-Only) - Các máy song song Sau đây em xin đưa ra một phương pháp khác để tổ chức bảng chỉ mục, đó là phương pháp Inverted File. 2/ Tập tin đảo (Inverted Files) Signature file cho phép thu hẹp không gian tìm kiếm nhưng để khẳng định chính xác văn bản nào có chứa truy vấn thì ta vẫn phải thực hiện giải thuật tìm kiếm trực tiếp. Nếu đặt hệ tìm kiếm vào tình huống phải xử lý trên khối lượng dữ liệu lớn, đồng thời nằm trong một hệ khôi phục thông tin thì thời gian truy tìm trên cấu trúc dữ liệu Signature file sẽ quá lớn, không phù hợp với hoàn cảnh thực tế. Inverted File là giải pháp trọn vẹn hơn, những kết quả của Moffat cho thấy: trong hầu hết các ứng dụng, Inverted file đạt hiệu quả hơn Signature file cả kích thức kho chỉ mục lẫn tốc độ tìm kiếm. Cấu trúc Inverted files (Inverted index ) là một cơ chế đánh chỉ số cho một tập văn bản theo thứ tự để tăng tốc độ tìm kiếm. Cấu trúc Inverted files (IF) gồm 2 thành phần :Từ vựng và tham số kèm theo : - Từ vựng là tập hợp toàn bộ các từ khác nhau trong văn bản. Mỗi từ lưu trữ một danh sách tất cả các vị trí văn bản mà từ đó xuất hiện cùng nhưng thông tin khác. - Tập hợp tất cả các danh sách đó gọi là sự xuất hiện (occurrences). Cấu trúc của Inverted files (IF) khá đơn giản, gồm các inverled list (IL) đặt liên tiếp nhau. Trong một IF mỗi phần tử của một danh sách chỉ tới một tài liệu hoặc một tên file. Không gian cần thiết cho bảng từ vựng là khá nhỏ. Theo luật Heap, từ vựng tăng với tộc độ O(nβ ), với β là một hằng số nhận giá trị giữa 0 và 1 phụ thuộc vào văn bản, trong thực tế từ 0.4 đến 0.6. Chẳng hạn, cho 1 Gb tập hợp dữ liệu TREC-2 thì bẳng từ vựng có kích thước chỉ 5Mb. Việc giảm kích thước này có thể thực hiện được bằng cách lược từ (stemming) hoặc một số kỹ thuật chuẩn hoá khác. Các vị trí xuất hiện yêu cầu không gian lớn hơn. Vì mỗi từ xuất hiện trong văn bản đòi hỏi một cấu trúc như vậy, không gian cần bổ sung là O(n). Ngay cả khi bỏ qua các từ kết thúc (trong thực tế là ngầm định khi đánh chỉ số các từ), trong thực tế toàn bộ không gian của các vị trí xuất hiện của các từ này chiếm khoảng 30% đến 40%kích thước văn bản. để giảm không gian yêu cầu, người ta đưa ra kỹ thuật đánh địa chỉ khối (block addressing): chia văn bản thành các block và các occurrence chỉ đến các block- nơi mà từ xuất hiện ( gồm các vị trí chính xác ). Các lớp index chỉ đến các vị trí xuất hiện chính xác gọi là “full invenrted index’’. Kỹ thuật này không chỉ giảm khối lượng con trỏ ( số các block ít hơn các vị trí ) mà tất cả occurrence của một từ trong một block riêng lẻ được giảm tương ứng đến 1. Với kỹ thuật này, indices chỉ chiếm 5% toàn bộ kích thước văn bản. Các block có thể được cố định về kích thước hoặc có thể xác định bằng cách chia văn bản thành files,các tài liệu, các trang Web… việc chia văn bản thành các block làm tăng hiệu quả về thời gian và chất lượng tìm kiếm.Trong phần thiết kế chương trình do được thực hiện trên nguồn dữ liệu là các file HTML, XML, TXT nên em đã chia tập tài liệu thành các block lớn là các File ( hoặc trang Web ), và trong mỗi block lớn được chia thành các Block nhỏ hơn dựa theo cấu trúc của đoạn văn bản nằm trong File (ví dụ Meta, Comment, Header, Title,…) 3/ Cấu trúc dữ liệu trong Inverted File Có ba câú trúc dữ liệu có thể được tổ chức một cách hiệu quả cho Inverted File: bảng băm, mảng sắp xếp, và cây B-tree. Một trong cấu trúc dữ liệu được sử dụng phổ biến trong hầu hết các bộ công cụ tìm kiếm trên bảng băm rất dễ dàng với độ phức tạp chỉ là hằng số. Sau đây em xin trình bày một cách tổng quan về cấu trúc dữ liệu này. Cấu trúc bảng băm Hàm băm h(x) ánh xạ khoá x sang một số nguyên trong pham vi đã cho (ví dụ từ 0 tới m-1). Và trong ứng dụng hàm băm được dùng để ánh xạ một từ khoá tới một vị trí trong bảng băm. Tuy nhiên hàm băm có thể cho ta cùng một vị trí trong bảng băm cho hai khoá khác nhau, khi đó ta có một xung đột. trong chương trình giới thiệu bộ công cụ em đã trình bày cách giải quyết xung đột này. Với hai phương pháp giải quyết xung đột ta thấy phương pháp Open Addressing chỉ có thể làm việc với một số lượng khoá nhất định và hiển nhiên rằng số lượng khoá không thể lớn hơn số phần tử của bảng băm. Trong khi đó bộ đệm gói có số lượng từ lưu trữ là không biết trước, ngoài ra cấu trúc từ điển cho phép người sử dụng thêm các từ mới nên phương pháp này không phù hợp. Phương pháp Chaining khắc phục được những điểm trên. Cấu trúc bảng băm có thể cho ta độ phức tạp trong việc xoá, chèn và tìm kiếm một khoá là tối ưu, tuy nhiên cấu trúc này không thể giải quyết cá truy vấn với kí tự đại diện ( ví dụ như Search Libra *) với truy vấn dạng này ta phải có một cấu trúc dữ liệu cho phép tìm kiếm theo phạm vi, cấu trúc đơn giản nhất có thể là một mảng sắp xếp. Mảng sắp xếp . . . Doc.# Link TËp tµi liÖu Doc.#1 1 2 Comput Tõ kho¸ Thuéc tÝnh File chØ môc Doc.#2 Posting File Với cấu trúc này Inverted File sẽ lưu một danh sách từ khoá trong mảng sắp xếp cùng với thông tin vị trí mà từ khoá nằm trong. Giải thuật tìm kiếm trên cơ sở dữ liệu này là phương pháp tìm kiếm nhị phân truyền thống. Hình 16: Inverted File sử dụng mảng sắp xếp Ta nhận thấy rằng mô hình cấu trúc này dễ hiểu, và nó sẽ thực hiện tốt trên bộ nhớ thứ cấp, tuy nhiên bất lợi chính của cấu trúc này đó là khả năng cập nhập bảng chỉ mục (ví dụ như ta thêm một từ khóa mới ) hơn nữa với độ phức tạp tìm kiếm log (N) trong đó N là số lượng từ khóa chỉ mục thì chưa phải là tối ưu. Sau đây em xin đưa ra một cấu trúc vẫn đáp ứng được khả năng tìm kiếm theo phạm vi mà thời gian tìm kiếm của nó nhỏ hơn nhiều so với cấu trúc mảng sắp xếp. Cấu trúc cây B-Tree Với cấu trúc của cây B- Tree đã được trình bày trong chương trình giới thiệu ta có thể nhận thấy rằng đây là một cấu trúc tốt đủ để đáp ứng mọi dạng truy vấn, các thuộc tính mong muốn dễ nhận thấy ở cây B-Tree đó là: - Khả năng tìm kiếm nhanh - Có khả năng tìm kiếm với các từ khóa kí tự đại diện ( ví dụ : comput* ) - Khả năng lập chỉ mục nhanh - Thực hiện chèn xóa rất dễ dàng - Thuật toán đơn giản Với những đánh giá trên em xin lựa chọn cài đặt cấu trúc dữ liệu từ điển trong chương trình: Sử dụng mảng băm để lưu từ điển nằm trong bộ đệm, còn từ điển nằm trong bộ nhớ thứ cấp được lưu dưới hai dạng: bảng băm và cây B - Tree 3.1.3 Các bước xây dựng chỉ mục theo phương pháp Inverted files Quá trình lập chỉ mục đòi hỏi một số lượng các thao tác vào ra đĩa cứng trên nguyên tắc thời gian thực hiện những thao tác này sẽ chiếm tỷ lệ quan trọng trong tổng thể thời gian thực hiện chung. Trên cơ sở hạn chế tối đa chi phí truy cập bộ nhớ ngoài, việc thiết kế cấu trúc Inverted File nhằm tới hai mục tiêu: thứ nhất là giảm thiểu các thao tác truy xuất, thứ hai cố gắng sắp xếp dữ liệu sao cho việc truy xuất được thực hiện tuần tự hơn là truy cập ngẫu nhiên. C¸c Inverted File nhá Tµi liÖu nguån Bé hîp nhÊt Inverted File lín Bé ph©n tÝch Với sự mô tả các bước thực hiện ở trên ta có thể thấy được phần nào thứ tự thực hiện quá trình lập chỉ mục. Tuy nhiên để có cái nhìn trực quan hơn về các bước tiến hành, em xin trình bày khái quát mô hình lập chỉ mục theo sơ đồ sau : Hình 17 Khái quát mô hình lập chỉ mục 1/ Bộ phân tích Quá trình phân tích bắt đầu bằng việc phân tích từng văn bản để nhận dạng các từ sau đó chuẩn hóa chúng và lưu vào bộ đệm trong bộ nhớ chính, sau khi toàn bộ tài liệu đã được lập chỉ mục và lưu vào trong bộ đệm ta đi bộ trên bộ đệm đó để loại