Luận văn tốt nghiệp: Tổng quan về khai phá dữ liệu Web và máy tìm kiếm, xử lý song song, giới thiệu về máy tìm kiếm ASPseek và đề xuất giải pháp song song hóa. - Tailieu123.org

Mục lục......................................................................................................................................................1

Chương 1. Tổng quan về khai phá dữ liệu Web và máy tìm kiếm............................4

1.1. Khai phá dữ liệu Web...............................................................................................................4

1.1.1. Tổng quan về khai phá dữ liệu Web............................................................................4

1.1.2 Các bài toán được đặt ra trong khai phá Web.......................................................5

1.1.3 Các lĩnh vực của khai phá dữ liệu Web.......................................................................6

1.1.3.1 Khai phá nội dung Web (Web content mining):...................................................6

1.1.3.2. Khai phá cấu trúc web (web structure mining):...................................................6

1.1.3.3 Khai phá sử dụng web (web usage mining)...........................................................7

1.1.4. Khó khăn..............................................................................................................................7

1.1.4.1 Web dường như quá lớn để tổ chức thành kho dữ liệu phục vụ Dataming....7

1.1.4.2. Độ phức tạp của trang Web lớn hơn rất nhiều so với những tài liệu văn bản

truyền thống khác......................................................................................................................8

1.1.4.3. Web là một nguồn tài nguyên thông tin có độ thay đổi cao..............................8

1.1.4.4. Web phục vụ một cộng đồng người dùng rộng lớn và đa dạng.......................8

1.1.4.5. Chỉ một phần rất nhỏ của thông tin trên Web là thực sự hữu ích....................9

1.1.5. Thuận lợi..............................................................................................................................9

1.2 Tổng quan về máy tìm kiếm....................................................................................................9

1.2.1 Nhu cầu:................................................................................................................................9

1.2.2 Cơ chế hoạt động của máy tìm kiếm..........................................................................10

1.2.3 Cấu trúc điển hình của một máy tìm kiếm................................................................11

Chương 3. Tổng quan về xử lý song song.........................................................................34

3.1 Máy tính song song..................................................................................................................34

3.1.2 Phân loại máy tính song song.......................................................................................35

3.1.2.1 Phân loại dựa trên cơ chế điều khiển chung........................................................35

3.1.2.2 Cách phân loại dựa trên sự tương tác giữa các BXL.........................................37

3.2 Mô hình lập trình song song..................................................................................................38

3.2.1 Mô hình nhiệm vụ - kênh liên lạc...............................................................................38

3.2.1.1 Đặc điểm mô hình nhiệm vụ-kênh liên lạc..........................................................38

3.2.1.2 Đặc điểm của mô hình nhiệm vụ - kênh liên lạc................................................39

3.2.2 Mô hình chia sẻ bộ nhớ chung.....................................................................................40

3.3. Hiệu năng của xử lý song song............................................................................................40

3.3.1 Khả năng tăng tốc độ tính toán:...................................................................................40

3.3.3 Cân bằng tải.......................................................................................................................43

3.3.4 Sự bế tắc..............................................................................................................................44

3.4 Môi trường lập trình song song............................................................................................45

3.4.1 Mô hình MPI (Message Passing Interface)..............................................................46

3.4.2 PVM (Parallel Virtual Machine)......................................................................................46

3.4.3 So sánh giữa MPI và PVM............................................................................................46

3.5 Giao thức truyền thông điệp MPI.........................................................................................47

Chương 2: Giới thiệu về module Crawler trong các máy tìm kiếm.......................13

2.1 Tổng quan:..................................................................................................................................13

2.2 Cấu trúc cơ bản của một crawler..........................................................................................15

2.2.1 Frontier................................................................................................................................16

2.2.2 History và kho chứa trang web....................................................................................17

2.2.3 Tải các trang web (fetching).........................................................................................18

2.2.4 Duyệt nội dung (parsing)...............................................................................................19

2.2.4.1. Quá trình lấy ra và chuẩn hóa các URL..............................................................20

2.2.4.2 Loại bỏ các từ dừng và chuyển các dạng thức của từ sang dạng gốc............21

2.2.4.3 Xây dựng cây các thẻ HTML.................................................................................21

2.3 Các crawler đa luồng (Multi-threaded crawlers).............................................................22

2.4. Các thuật toán crawling.........................................................................................................24

2.4.1 Thuật toán Naïve tốt nhất đầu tiên..............................................................................24

2.4.2 Thuật toán SharkSearch.................................................................................................25

2.4.3 Crawler có trọng tâm (focused crawler)...................................................................26

2.3.4 Các crawler tập trung theo ngữ cảnh (context focused crawler).......................27

2.4. Các tiêu chuẩn đánh giá các crawler..................................................................................29

2.4.1 Độ quan trọng của trang web.............................................................................................29

2.4.2 Các phân tích tổng hợp........................................................................................................31

Chương 4. Giới thiệu về máy tìm kiếm ASPseek và đề xuất giải pháp song

song hóa................................................................................................................................................50

4.1 Giới thiệu chung về máy tìm kiếm ASPseek....................................................................50

4.1.1 Một số tính năng của ASPseek....................................................................................50

4.1.2 Các thành phần của ASPseek.......................................................................................51

a. Module đánh chỉ số (indexing)........................................................................................51

b. Module tìm kiếm (searchd)..............................................................................................52

c. Module tìm kiếm s.cgi.......................................................................................................52

4.2 Cấu trúc cơ sở dữ liệu trong máy tìm kiếm ASPseek....................................................52

4.2.1 Cấu trúc một số bảng chính trong cơ sở dữ liệu của ASPseek...........................53

4.2.2 Cấu trúc một số file nhị phân trong cơ sở dữ liệu của ASPseek........................56

4.2.2.1 Cấu trúc các file nhị phân trong thư mục xxw:..................................................56

4.3 Tìm hiểu về việc thực thi quá trình crawler trong module index của máy tìm

kiếm VietSeek...................................................................................................................................60

4.3.1Quá trình crawler trong ASPseek. ................................................................

4.3.2 Đề xuất giải pháp song song hóa .................................................................

4.3.2.1 Giải pháp song song hóa................................................................................. 63

4.3.2.2 Cơ chế phân công công việc giữa các bộ xử lý. ............................................. 65

4.3.2.3 Tổng hợp kết quả sau quá trình song song: .................................................... 65

4.3.2.4 Vấn đề tương tranh giữa các bộ xử lý: ........................................................... 66

4.3.2.5 Đánh giá giải pháp song song hóa.................................................................. 66

4.3.3.

Tài liệu tham khảo:...............................................................................................

Phụ lục: Một số hàm bổ sung trong Môđun indexing song song hóa

Chương 1. Tổng quan về khai phá dữ liệu Web và máy tìm

kiếm

1.1. Khai phá dữ liệu Web

1.1.1. Tổng quan về khai phá dữ liệu Web

Ngày nay, sự phát triển nhanh chóng của mạng Internet và Intranet đã sinh ra một

khối lượng khổng lồ các dữ liệu dạng siêu văn bản (dữ liệu Web). Trong những năm gần

đây Intrnet đã trở thành một trong những kênh về khoa học, thông tin kinh tế, thương

mại và quảng cáo. Một trong những lý do cho sự phát triển này là chi phí thấp để duy trì

một trang Web trên Internet. So sánh với những dịch vụ khác như đăng tin hay quảng

cáo trên một tờ báo hay tạp chí, thì một trang Web "đòi" rẻ hơn rất nhiều và cập nhật

nhanh chóng hơn tới hàng triệu người dùng khắp mọi nơi trên thế giới. Có thể nói

Internet như là cuốn từ điển Bách khoa toàn thư với nội dung và hình thức đa dạng. Nó

như một xã hội ảo, nó bao gồm các thông tin về mọi mặt của đời sống kinh tế, xã hội

được trình bày dưới dạng văn bản, hình ảnh, âm thanh ...

WWW

Knowledge

Hình 1.1: Khai phá web, công việc không dễ dàng

Tuy nhiên, Internet là một môi trường đa phương tiện động bao gồm sự kết hợp

của các cơ sở dữ liệu không đồng nhất, các chương trình và các giao tiếp người dùng.

Rõ ràng, khai phá dữ liệu text chỉ là một lĩnh vực nhỏ trong môi trường này. Khai phá

dữ liệu trên Internet, hay thường được gọi là khai phá web ngoài việc cần khai phá được

nội dung các trang văn bản, còn phải khai thác được các nguồn lực này cũng như mối

quan hệ giữa chúng. Khai phá Web, sự giao thoa giữa khai phá dữ liệu và Word-Wide-

Web, đang phát triển mạnh mẽ và bao gồm rất nhiều lĩnh vực nghiên

cứu như trí tuệ nhân tạo, truy xuất thông tin (information retrival) hay các lĩnh vực khác.

Các công nghệ Agent-base, truy xuất thông tin dựa trên khái niệm (concept-based), truy

xuất thông tin sử dụng case-base reasoning và tính hạng văn bản dựa trên các đặc trưng

(features) siêu liên kết... thường được xem là các lĩnh vực nhỏ trong khai phá web. Khai

phá Web vẫn chưa được định nghĩa một cách rõ ràng và các chủ đề trong đó vẫn tiếp tục

được mở rộng. Tuy vậy, chúng ta có thể hiểu khai phá web như việc trích ra các thành

phần được quan tâm hay được đánh giá là có ích cùng các thông tin tiềm năng từ các

tài nguyên hoặc các hoạt động liên quan tới World-Wide Web[]. Hình 1.2 thể hiện một

sự phân loại các lĩnh vực nghiên cứu quen thuộc trong khai phá Web. Người ta thường

phân khai phá web thành 3 lĩnh vực chính: khai phá nội dung web (web content mining),

khai phá cấu trúc web (web structure mining) và khai phá việc sử dụng web (web usage

mining).

WEB MINING

Web

Content

Structure

Usage

Web Page Search General Access Customized

Content Result Pattent

Usage

Hình 1.2: Các nội dung trong khai phá Web.

1.1.2 Các bài toán được đặt ra trong khai phá Web

- Tìm kiếm các thông tin cần thiết: Web quá lớn và quá đa dạng, vì vậy việc tìm

được thông tin cần thiết là không đơn giản. Công việc này được giải quyết bởi các máy

tìm kiếm.

- Tạo ra các tri thức mới từ các thông tin có sẵn trên Web: Vấn đề này có thể

được coi như một vấn đề con của bài toán trên. Ở đây ta mặc định đã có một tập các

dữ liệu Web, và ta cần lấy ra được các thông tin hữu ích từ những dữ liệu này.

LÝ THUYẾT TOÁN

Kinh doanh - tiếp thị

Quản trị, internet, marketing

Giáo dục đào tạo

Các tài liệu, đề thi liên quan đến các môn học của học sinh và bài giảng của giáo viên

Công nghệ thông tin

Tài liệu lĩnh vực công nghệ thông tin

Học tiếng Anh

Các tài liệu liên quan đến học tiếng Anh