Giải pháp tính hạng trang khai thác cấu trúc Block của web và áp dụng vào máy tìm kiếm

Luận văn tốt nghiệp

Giải pháp tính hạng trang khai thác cấu trúc

Block của web và áp dụng vào máy tìm kiếm

1

Mở đầu

Ngày nay, với những tác động to lớn và mạnh mẽ của mạng Internet tới đời

sống kinh tế, chính trị và văn hóa của con người, lĩnh vực khai phá dữ liệu Web đã và

đang trở thành lĩnh vực nghiên cứu thời sự, thu hút được sự quan tâm của rất nhiều nhà

nghiên cứu. Khai phá dữ liệu Web là điểm hội tụ của rất nhiều lĩnh vực nghiên cứu

như: cơ sở dữ liệu, truy xuất thông tin (information retrival), trí tuệ nhân tạo, nó còn là

một lĩnh vực nhỏ trong học máy (machine learning) và xử lý ngôn ngữ tự nhiên.

Một trong những lĩnh vực nghiên cứu đang rất được quan tâm hiện nay trong

khai phá Web là việc xây dựng các công cụ tìm kiếm trên Web. Bởi trong bối cảnh xã

hội thông tin ngày nay, nhu cầu nhận được các thông tin một cách nhanh chóng, chính

xác đang ngày càng trở nên cấp thiết. Để tìm ra được các thông tin có ích đối với mỗi

người dùng, đặc biệt là với những người dùng thiếu kinh nghiệm hoàn toàn không phải

là việc đơn giản. Với một công cụ tìm kiếm, khả năng người dùng có thể duyệt Web

và định vị được các trang Web mình quan tâm đã trở nên dễ dàng hơn nhiều.

Tuy nhiên hiện nay, do sự phát triển và thay đổi với tốc độ quá nhanh của

Internet, các công cụ tìm kiếm đang phải đối mặt với những bài toán nan giải về tốc

độ. Trong đó có bài toán về tốc độ tính toán hạng cho các trang Web, thực thi nhiệm

vụ tính toán độ “quan trọng” cho các trang thông tin kết quả tìm được so với yêu cầu

tìm kiếm của người dùng. Vì kích thước của World Wide Web là vô cùng lớn, lên tới

hàng tỉ trang web, không những thế các trang Web này không ở trạng thái tĩnh mà luôn

luôn thay đổi. Do đó tính hiệu quả về thời gian càng trở nên quan trọng. Nếu phép tính

PageRank cho tập các trang web trong cơ sở dữ liệu không đủ nhanh, hệ thống tìm

kiếm sẽ không cung cấp được chất lượng tìm kiếm tốt cho người dùng.

Ý thức đây là một lĩnh vực nghiên cứu có nhiều triển vọng, chúng tôi đã chọn

hướng nghiên cứu “Giải pháp tính hạng trang khai thác cấu trúc Block của Web và

áp dụng vào máy tìm kiếm” cho đề tài khóa luận tốt nghiệp của mình. Khóa luận tập

trung nghiên cứu bài toán tính hạng trang web (PageRank) trong các máy tìm kiếm:

cấu trúc, thuật toán cũng như các tiêu chuẩn đánh giá quá trình này. Chúng tôi cũng đã

áp dụng các lý thuyết trên để đi sâu phân tích mã nguồn, tìm hiểu cơ chế thực thi quá

trình tính PageRank trong máy tìm kiếm Vinahoo, một máy tìm kiếm tiếng Việt mã

nguồn mở với nhiều tính năng ưu việt. Từ việc nghiên cứu này, chúng tôi đã đề xuất

một giải pháp áp dụng khái niệm thành phần liên thông trong ma trận liên kết Web

trong Vinahoo, đồng thời thực hiện việc cài đặt thử nghiệm trên mã nguồn của máy

tìm kiếm này.

Nội dung của khóa luận được tổ chức thành bốn chương với nội dung được

giới thiệu như dưới đây.

2

Chương 1 với tên gọi “Tổng quan về khai phá dữ liệu web và máy tìm kiếm”

trình bày về những nội dung nghiên cứu cơ bản của khai phá web, những thuận lợi và

khó khăn trong lĩnh vực này. Phần cuối của chương này trình bày các thành phần cơ

bản của một máy tìm kiếm.

“Một số thuật toán tính hạng trang điển hình” là tiêu đề của chương 2. Phần

đầu chương này giới thiệu tổng quan về bài toán xêp hạng trang Web trong máy tìm

kiếm và thuật toán tính PageRank cơ bản. Việc phân tích nhu cầu tăng tốc độ tính toán

PageRank trong máy tìm kiếm, một số thuật toán cải tiến từ phương pháp PageRank

cùng với đánh giá được trình bày trong phần cuối của chương.

Chương 3 với tên gọi “Thuật toán sử dụng cấu trúc Block theo thành phần

liên thông” tập trung nghiên cứu về giải pháp khai thác cấu trúc Web. Chương này

giới thiệu khái niệm, một số vấn đề về lý thuyết, chứng minh và đánh giá thuật toán

CCP sử dụng cấu trúc này.

Chương 4 với tiêu đề “Giải pháp tính hạng trang cải tiến cho máy tìm kiếm

Vinahoo” giới thiệu thành phần tính PageRank trong module đánh chỉ số của

Vinahoo, các cải tiến, cài đặt và đánh giá kết quả thực nghiệm.