MỤC LỤC

[FONT="]LỜI MỞ ĐẦU 4

PHẦN I: MỞ ĐẦU 6

1. Tính cấp thiết của luận văn .6

2. Mục đích, nhiệm vụ của luận văn .7

Mục đích của luận văn 7

Nhiệm vụ của luận văn 7

3. Phạm vi nghiên cứu 7

4. Nội dung luận văn 8

PHẦN II: NỘI DUNG 9

[FONT="]CHƯƠNG I: GIỚI THIỆU BỘ CÔNG CỤ TÌM KIẾM THÔNG TIN .9

[FONT="]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

[FONT="]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 [FONT="]2.1 Thu hồi trang Web 33

2.1.1 Web Crawler .33

2.1.2 Chọn lựa các trang .34

2.2 Lưu trữ .38

2.2.1 Sự phân tán trang theo các nút . .39

2.2.2 Các phương pháp tổ chức trang vật lý .40

2.2.3 Các chiến thuật cập nhật 40

2.3 Lập chỉ mục 43

2.1.1 Cấu trúc của bảng chỉ mục .45

2.1.2 Một số thách thức. .46

2.3.3 Chia bảng chỉ mục. .46

2.4 Sắp xếp và phân tích liên kết 48

2.4.1 Phương pháp PageRank .49

2.4.2 Phương pháp HIST 54

CHƯƠNG III: THIẾT KẾ CÁC CÔNG CỤ TÌM KIẾM THÔNG TIN TRÊN MẠNG .61

3.1 Mô đun lập chỉ mục 62

3.1.1 Khái niệm chỉ mục 62

3.1.1 Các cấu trúc lưu chỉ mục 62

3.1.2 Các bước xây dựng chỉ mục theo phương pháp Inverted files. .68

3.1.4 Lập chỉ mục với nguồn dữ liệu đầu vào .76

3.2 Mô đun tìm kiếm 77

3.2.1 Các dạng truy vấn .80

3.2.2 Phân tích cú pháp truy vấn .81

3.2.3 Các phương pháp giải quyết vấn đề 83

3.3 Mô đun sắp xếp 82

Các mô hình sắp xếp và đánh giá . .82

1. Mô hình Boolean .83

2. Mô hình không gian vector .84

[FONT="]PHẦN III: KẾT LUẬN .90

1. Kết quả đạt được trong luận văn .90

2. Hướng phát triển trong tương lai 91

TÀI LIỆU THAM KHẢO 94

PHỤ LỤC .98

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