TRƯỜNG ĐẠI HỌC MỞ THÀNH PHỐ HỒ CHÍ MINH
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO ĐỒ ÁN MÔN HỌC
Đề tài: Tìm hiểu Search Engine và xây dựng ứng dụng minh hoạ.
GVDH:
Thầy Ninh Xuân Hương.
Sinh viên: Lê Nguyễn Đoàn Trí
- 0851010294.
Võ Nguyễn Minh Tuân - 0851010308.
TP.HCM tháng 2 năm 2012.
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
LỜI CẢM ƠN
Trước khi trình bày nội dung tìm hiểu của đồ án môn học, chúng em xin
dành những dòng đầu tiên để gởi lời cám ơn chân thành đến:
Thầy Ninh Xuân Hương, người đã tận tình hướng dẫn và tạo mọi điều
kiện tốt nhất cho chúng em trong suốt thời gian thực hiện đồ án môn học.
Chúng em xin gởi lời cám ơn đến quý thầy cô trong khoa công nghệ thông
tin trường Đại học Mở TP.HCM đã tận tình giảng dạy, truyền đạt kiến thức,
kinh nghiệm quý báu chuẩn bị cho em những kiến thức cần thiết làm căn bản để
tìm hiểu một vấn đề còn mới đối với chúng em giúp chúng em tự tin khi đối mặt
với những vấn đề mới sẽ có khi chúng em rời khỏi ghế nhà trường.
Chúng con xin gởi lời cảm ơn sâu sắc đến ba mẹ và gia đình đã luôn chăm
sóc, giáo dục, động viên và tạo mọi điều kiện tốt nhất trong suốt quá trình học
tập, tìm hiểu để chúng con đạt được kết quả hôn nay.
Chúng tôi xin cảm ơn bạn bè đã và đang động viên, chia sẻ, giúp đỡ
chúng tôi trong suốt thời gian học tập và tim hiểu và thực hiện đồ án môn học.
TP.HCM, tháng 2 năm 2012.
Nhóm thực hiện
Lê Nguyễn Đoàn Trí.
Võ Nguyễn Minh Tuân.
Lê Nguyễn Đoàn Trí – 0851010294
1/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
MỤC LỤC
LỜI NÓI ĐẦU ......................................................................... 7
PHẦN A: TÌM HIỂU LÝ THUYẾT VỀ TỔ CHỨC VÀ
HOẠT ĐỘNG CỦA SEARCH ENGINE. ............................... 8
CHƯƠNG 1: TỔNG QUAN VỀ TÌM KIẾM THÔNG TIN .............8
I. Giới thiệu về tìm kiếm thông tin. ............................................................. 8
1. Khái niệm về công cụ tìm kiếm: ........................................................... 8
2. Một số vấn đề trong việc tìm kiếm thông tin: ....................................... 8
3. Hệ tìm kiếm thông tin-Information Retrieval Search. .......................... 9
II. Tổng quan về của một hệ thống tìm kiếm thông tin ................................. 9
1. Bộ phận thu thập thông tin (Spyder/Robot/Web Crawler…): ............ 10
2. Bộ phân lập chỉ mục (Indexing): ......................................................... 10
3. Bộ phận giao tiếp, so khớp và sắp xếp các tài liệu trả về.................... 10
III. Nguyên lý hoạt động............................................................................... 11
CHƯƠNG 2: NHỮNG VẤN ĐỀ CỦA BỘ THU THẬP THÔNG
TIN ...................................................................................................13
I. Tóm tắt lược sử của WebCrawler:.......................................................... 13
1. Chu kỳ thu thập dữ liệu của một web crawler: ................................... 13
2. Web Crawler đầu tiên: ......................................................................... 13
II. Các ứng dụng của WebCrawler: ............................................................. 14
1. General Web Search (Tạo chỉ mục bao gồm các chủ đề rộng): .......... 14
2. Vertical Web Search (Tạo chỉ mục cho các chủ đề cụ thể): ............... 14
3. Thu thập đặc tính của Web (Web Characterization): .......................... 14
Lê Nguyễn Đoàn Trí – 0851010294
2/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
4. Ánh xạ trang web (Mirroring-Giữ lại bản sao hoặc tái tạo trang web):
15
5. Web archival (Lưu trữ nội dung): ....................................................... 15
6. Web Site Anaylysis (Phân tích trang web): ........................................ 15
III. Kiến trúc của Web Crawler: ................................................................... 16
IV. Những thắc mắc liên quan đến hoạt động của WebCrawler: ................. 16
1. Trong môi trường mạng, robot lấy thông tin từ các site. Vậy robot sẽ
bắt đầu từ site nào ? ................................................................................... 17
2. Ai sẽ cung cấp địa chỉ của các site này cho robot ? ............................ 17
3. Chọn dữ liệu nào trong tài liệu để lập chỉ mục ?................................. 17
V. Các thuật toán thu thâp dự liệu: .............................................................. 17
1. Tìm kiếm theo chiều sâu: .................................................................... 18
2. Tìm kiếm theo chiều rộng: .................................................................. 19
3. Tìm kiếm theo ngẩu nhiên: .................................................................. 19
VI. Những vấn đề cần lưu ý về web crawler: ............................................... 20
CHƯƠNG 3: NHỮNG VẤN ĐỀ CỦA BỘ PHẬN LẬP CHỈ MỤC
..........................................................................................................21
I. Khái quát về hệ thống lập chỉ mục ......................................................... 21
II. Vấn đề tách từ tự động để lập chỉ mục: .................................................. 21
1. Tách từ trong tiếng Anh ...................................................................... 21
2. Tách từ trong tiếng việt ....................................................................... 21
3. Tách từ tự động tiếng việt: .................................................................. 22
III. Vấn đề xác định từ chỉ mục .................................................................... 24
1. Vấn đề lập chỉ mục tự động trong tiếng anh ....................................... 26
2. Vấn đề lập chỉ mục tự động trong tiếng việt: ...................................... 27
Lê Nguyễn Đoàn Trí – 0851010294
3/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
IV. Vấn đề tính trọng số cho từ chỉ mục....................................................... 27
1. Cách tính trong số cho vector chỉ mục: ............................................... 27
2. Độ nhiễu tín hiệu (Signal Noise): ........................................................ 28
3. Giá trị phân biệt từ ............................................................................... 29
4. Tập tin nghịch đảo tài liệu ................................................................... 29
5. Tại sao phải sử dụng tập tin nghịch đảo? ............................................ 30
CHƯƠNG 4: NHỮNG VẤN ĐỀ CỦA BỘ PHẬN GIAO TIẾP, SO
KHỚP VÀ SẮP XẾP KẾT QUẢ TRẢ VỀ ......................................31
I. Vấn đề giao tiếp với người dùng ............................................................ 31
II. Vấn đề so khớp câu truy vấn và tài liệu. ................................................ 31
1. Thuật toán không gian vector: ............................................................. 31
2. Tìm kiếm Boolean ............................................................................... 32
3. Thuật toán Boolean mở rộng ............................................................... 33
4. Thuật toán xác suất .............................................................................. 34
5. Thuật toán PageRank của Google: ...................................................... 35
III. Sắp xếp các tài liệu trả về ....................................................................... 40
CHƯƠNG 5: GIỚI THIỆU MỘT SỐ SEARCH ENGINE THÔNG
DỤNG HIỆN NAY ..........................................................................41
I. Giới thiệu chung: .................................................................................... 41
II. Google..................................................................................................... 42
III. LYCOS ................................................................................................... 44
IV. Bùng nổ cỗ máy tìm kiếm tiếng Việt...................................................... 45
V. Một số trang web “cây nhà lá vườn” nổi bật. ......................................... 48
1. http://socbay.vn/ .................................................................................. 48
2. http://xalo.vn/....................................................................................... 48
3. http://baamboo.com/ ............................................................................ 49
Lê Nguyễn Đoàn Trí – 0851010294
4/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
PHẦN B: CHƯƠNG TRÌNH DEMO SEARCH ENGINE ... 51
I. Giới thiệu chương trình: ......................................................................... 51
II. Mô hình chương trình: ............................................................................ 52
1. Ý NGHĨA: ........................................................................................... 52
2. Lớp FILE: ............................................................................................ 52
3. Lớp WORD: ........................................................................................ 52
4. Lớp CATALOG: ................................................................................. 53
5. Tập tin Crawler.aspx: .......................................................................... 53
6. Tập tin Home.aspx: ............................................................................. 53
III. Chi tiết chương trình:.............................................................................. 53
1. Lớp FILE: ............................................................................................ 53
2. Lớp WORD: ........................................................................................ 54
3. Lớp CATALOG: ................................................................................. 56
4. Crawler.aspx: ....................................................................................... 59
4. Xây dựng phương thức Search ............................................................ 64
5. Home.aspx ........................................................................................... 65
IV. Kết luận:.................................................................................................. 69
1. Khuyết điểm của chương trình: ........................................................... 69
2. Ưu điểm của chương trình:.................................................................. 69
PHẦN C: CÁC TÀI LIỆU THAM KHẢO............................ 70
Lê Nguyễn Đoàn Trí – 0851010294
5/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN
.......................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
Ngày…..tháng…..năm 2012
Ký tên
Lê Nguyễn Đoàn Trí – 0851010294
6/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
LỜI NÓI ĐẦU
Trong thời đại bùng nổ thông tin như hiện nay, thông tin được lưu trữ trên
máy tình ngày càng nhiều, con người không thể biết được hoặc đọc hết tất cả nội
dung của các trang web để tìm nội dung mình cần. Do đó, việc tìm kiếm thông
tin chính xác là nhu cầu thiết yếu đối với mọi người trong mọi lĩnh vực. Internet
hiện nay đã trở thành một kho tư liệu khổng lồ mà việc tìm kiếm thông tin trên
kho tư liệu này cần phải được hỗ trợ bởi các công cụ tìm kiếm tốt. Các hệ thống
tìm kiếm thông tin thông dụng như Google search, Yahoo search đã đáp ứng
được hầu hết nhu cầu của mọi người một cách rất linh động.
Ngày nay, hầu như tất cả người dùng internet đầu biết đến ít nhất là một
hoặc nhiều những công cụ tìm kiếm trên internet. Tuy nhiên không phải ai cũng
biết được tổ chức cũng như cách thức hoạt động của một Search Engine là như
thế nào. Do đó, Mục tiêu của đồ án là tìm hiểu cách thức tổ chức, hoạt động và
cách cài đặt một search engine là như thế nào. Qua đó giúp chúng tôi và các bạn
hiểu cách thức tổ chức thông tin, thực thi một câu truy vấn và đặc trưng của
ngôn ngữ mà search engine tiếp cận thì ta có thể tối ưu hoá cơ hội nhận được các
thông tin hữu ích và các bạn có thể phát triện một Search Engine của mình. Đây
chính là mục tiêu chính của đồ án.
Trong quá trình thực hiền đồ án, chúng em đã nỗ lực rất nhiều để tìm
kiếm nhưng thông tin hữu ích để phục vụ cho đồ án. Nhưng việc chúng em
không thể tránh khỏi những sai sót, mong nhận được sự thông cảm và góp ý từ
quý thầy cô và các bạn.
Lê Nguyễn Đoàn Trí – 0851010294
7/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
PHẦN A: TÌM HIỂU LÝ THUYẾT VỀ TỔ
CHỨC VÀ HOẠT ĐỘNG CỦA SEARCH
ENGINE.
CHƯƠNG 1: TỔNG QUAN VỀ TÌM KIẾM
THÔNG TIN
I. Giới thiệu về tìm kiếm thông tin.
1. Khái niệm về công cụ tìm kiếm:
_ Công cụ tìm kiếm(Search Engine) là một hệ thống thu thập thông
tin được thiết kế để giúp cho việc tìm kiếm thông tin lưu trữ trên
một hệ thống máy tính. Công cụ tìm kiếm tối thiểu hóa thời gian
cần thiết để tìm kiếm thông tin bằng việc lưu trữ và xử lý thông tin
theo nhiều cách.
_ Dạng phổ biến nhất của công cụ tìm kiếm đó là công cụ tìm kiếm
Web (Web Search Engine) .
_ vd: Google Search, Yahoo Search, …
_ Công cụ tìm kiếm cung cấp một giao diện giúp cho người dùng có
thể chọn thông tin cần tìm và có cơ chế xử lý và tìm được thông tin
tương ứng. Thông tin cần tìm sẽ tương ứng với một câu truy vấn.
2. Một số vấn đề trong việc tìm kiếm thông tin:
_ Kể từ những năm 40, các vấn đề trong việc lưu trữ thông tin và tìm
kiếm thông tin đã thu hút được sự chú ý rất lớn. Với một lương
thông tin khổng lồ thì việc tìm kiếm chính xác và nhanh chóng càng
trở nên cần thiết và khó khăn hơn. Với sự ra đời của máy tính, rất
nhiều ý tưởng lớn được đưa ra nhằm cung cấp một hệ thống tìm
kiếm thông tin thông minh và chính xác. Tuy nhiên vấn đề tìm
kiếm sao cho hiệu quả vẫn chưa được giải quyết.
_ Về nguyên tắc, việc lưu trữ thông tin thì đơn giản. Giả sử có một
kho chức các tài liệu và một ngươì muốn tìm các tài liệu liên quan
đến yêu cầu của mình. Người đó có thể đọc tất cả các tài liệu trong
kho, giữ lại các tài liệu có liên quan và bỏ đi các tài liệu không liên
quan. Rõ ràng giải pháp này không thực tế bởi vì tốn rất nhiều thời
gian.
Lê Nguyễn Đoàn Trí – 0851010294
8/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
_ Với sự ra đời của máy vi tình tốc độ cao, máy tính có thể đọc thay
cho con người để trích ra tài liệu có liên quan trong toàn bộ tập dữ
liệu. Tuy nhiên vấn đề lúc này là làm sao để xác định được tài liệu
nào liên qua đế câu hỏi. Mục đích của một hệ thống tìm kiếm thông
tin tự động là truy lục được tất cả các tài liệu có liên quan đến yêu
cầu.
3. Hệ tìm kiếm thông tin-Information Retrieval Search.
Sau đây là định nghĩa về hệ thống tìm kiếm thông tin của một số tác
giả:
_ Salton(1989): “Hệ thống tìm kiếm thông tin xữ lý các tập tin lưu trữ
và những yêu cầu về thông tin, xác định và tìm từ các tập tin những
thông tin phù hợp với những yêu cầu về thông tin. Việc truy tìm
những thông tin đặc thù phụ thuộc vào sự tương tác các giá trị của
các thuộc tính đối với thông tin được lưu trữ và các yêu cầu về
thông tin.”
_ Kowalski (1997): “Hệ thống truy tìm thông tin là một hệ thống có
khả năng lưu trữ, truy tìm và duy trì thông tin. Thông tin trong
những trường hợp này có thể bao gồm văn bản, âm thanh, video và
những đối tượng đa phương tiện khác.”
_ Hiểu đơn giản hệ thống tìm kiếm thông tin là một hệ thống hỗ trợ
cho con người sử dụng tìm kiếm thông tin một cách nhanh chóng
và dễ dàng. Người sử dụng có thê đưa vào những câu hỏi, những
yêu cầu (dạng ngôn ngữ tự nhiên) và hệ thống sẽ tìm kiếm trong tập
các tài liệu (dạng ngôn ngữ tự nhiên) đã được lưu trữ để tìm ra
những tài liệu có liên quan, sau đó sẽ sắp xấp các tài liệu theo mức
độ liên quan giảm dần và trả về cho người dùng.
II. Tổng quan về của một hệ thống tìm kiếm thông tin
Gồm các tập tài liệu (DOCS) đã được lưu trữ trong kho dữ liệu, tập
các yêu cầu (REQS) của người dùng và một số phương pháp tính độ
tương quan (SIMILAR) để xác định các tài liệu đáp ứng cho yêu cầu.
Theo lý thuyết thì mối liên hệ giữa các câu hỏi và các tài liệu có thể so
sánh một cách trực tiếp. Nhưng trên thực tế thì điều này không thể được
vì các câu hỏi và các tập tài liệu đều ở dạng văn bản, chỉ có con người đọc
thì thấy ngay được mối liên hệ giữa chúng, nhưng ở đây là máy móc,
không thể suy luận như con người được. Chính vì thế để xác định được
mối liên hệ giữa câu hỏi và các tập tài liệu phải qua một bước trung gian.
Lê Nguyễn Đoàn Trí – 0851010294
9/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
REQS
GVHD: Thầy Ninh Xuân Hương
SIMILAR
DOCS
Hình 1: Tổng quan về chức năng của một hệ tìm kiếm thông tin
Trước hết phải chuyển đổi các câu hỏi thành các từ riêng biệt đủ để
biểu hiện cho nội dung câu hỏi gọi là ngôn ngữ chỉ mục (Indexing
Language-LANG). Tách từ trong các tập tài liệu và lập chỉ mục cho tài
liệu. và từ đó ta sẽ dễ dàng hơn để xác định độ tương quan giữa câu hỏi và
tập tài liệu.
Dựa vào chức năng ta chia thành 3 bộ phận:
1. Bộ phận thu thập thông tin (Spyder/Robot/Web Crawler…):
Robot là một chương trình tự động duyệt qua các cấu trúc siêu
liên kết để thu thập tài liệu và tự động nhận về tất cả các siêu liên kết
có trong tài liệu để tiếp tục duyệt.
Robot được biết đến dưới nhiều tên gọi khác nhau : Web
crawler, Spider, Web wanderer hoặc Web worm,… Những tên gọi này
đôi khi gây nhầm lẫn, như từ “Spider”, “Wanderer” làm người ta nghĩ
rằng robot tự nó di chuyển và từ “Worm” làm người ta liên tưởng đến
virus. Về bản chất robot chỉ là một chương trình duyệt và thu thập
thông tin từ các Website theo đúng giao thức web. Những trình duyệt
thông thường không được xem là robot do thiếu tính chủ động, chúng
chỉ duyệt web khi có sự tác động của con người.
2. Bộ phân lập chỉ mục (Indexing):
Hệ thống lập chỉ mục hay còn gọi là hệ thống phân tích và xử lý
dữ liệu, thực hiện việc phân tích, trích chọn những thông tin cần thiết
(thường là các từ đơn , từ ghép , cụm từ quan trọng) từ những dữ liệu
mà robot thu thập được và tổ chức thành cơ sở dữ liệu riêng để có thể
tìm kiếm trên đó một cách nhanh chóng, hiệu quả. Hệ thống chỉ mục là
danh sách các từ khoá, chỉ rõ các từ khoá nào xuất hiện ở trang nào,
địa chỉ nào.
3. Bộ phận giao tiếp, so khớp và sắp xếp các tài liệu trả về
Search engine tương tác với user thông qua giao diện web, có
nhiệm vụ tiếp nhận, phân tích các câu truy vấn sau đó so sánh để tìm
tài liệu liên quan và trả về những tài liệu thoả yêu cầu của user.
Các từ được trích từ câu truy vấn và các từ chỉ mục của văn bản
sẽ được so khớp với nhau để tìm ra các tài liệu liên quan đến câu truy
vấn. Mỗi tài liệu có một độ tương qua với câu hỏi. Các tài liệu này sẽ
được sắp xếp theo độ tương quan giảm dần và trả về cho người dùng.
Lê Nguyễn Đoàn Trí – 0851010294
10/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
Nói nôm na, công việc là tìm kiếm các trang mà những từ trong
câu truy vấn (query) xuất hiện nhiều nhất, ngoại trừ stopword (các từ
quá thông dụng như mạo từ a, an, the,…). Một từ càng xuất hiện nhiều
trong một trang thì trang đó càng được chọn để trả về cho người dùng.
Và một trang chứa tất cả các từ trong câu truy vấn thì tốt hơn là một
trang không chứa một hoặc một số từ. Ngày nay, hầu hết các search
engine đều hỗ trợ chức năng tìm cơ bản và nâng cao, tìm từ đơn, từ
ghép, cụm từ, danh từ riêng, hay giới hạn phạm vi tìm kiếm như trên
đề mục, tiêu đề, đoạn văn bản giới thiệu về trang web,…..
Ngoài chiến lược tìm chính xác theo từ khoá, các search engine
còn cố gắng “hiểu” ý nghĩa thực sự của câu hỏi thông qua những câu
chữ do người dùng cung cấp. Điều này được thể hiện qua chức năng
sửa lỗi chính tả, tìm cả những hình thức biến đổi khác nhau của một từ.
Ví dụ : search engine sẽ tìm những từ như speaker, speaking, spoke khi
người dùng nhập vào từ speak.
III. Nguyên lý hoạt động
Search engine điều khiển robot đi thu thập thông tin trên mạng
thông qua các siêu liên kết ( hyperlink ). Khi robot phát hiện ra một site
mới, nó gởi tài liệu (web page) về cho server chính để tạo cơ sở dữ liệu
chỉ mục phục vụ cho nhu cầu tìm kiếm thông tin.
Bởi vì thông tin trên mạng luôn thay đổi nên robot phải liên tục cập
nhật các site cũ. Mật độ cập nhật phụ thuộc vào từng hệ thống search
engine. Khi search engine nhận câu truy vấn từ user, nó sẽ tiến hành phân
tích, tìm trong cơ sở dữ liệu chỉ mục & trả về những tài liệu thoả yêu cầu.
Lê Nguyễn Đoàn Trí – 0851010294
11/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
Hình 2: Nguyên lý hoạt động của search engine.
Lê Nguyễn Đoàn Trí – 0851010294
12/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
CHƯƠNG 2: NHỮNG VẤN ĐỀ CỦA BỘ THU
THẬP THÔNG TIN
I. Tóm tắt lược sử của WebCrawler:
Web crawler là một phần mềm để tải về nội dung các trang web.
Còn được biết đến với những tên gọi khác là Web Spider, Web Robot
hoặc đơn giản là Bot.
1. Chu kỳ thu thập dữ liệu của một web crawler:
_ The crawler bắt đầu tải nội dung của các trang hạt giống, từ những
trang hạt giống này The Crawler sẽ phân tích và quét để tìm ra các
liên kết mới.
_ Các liên kết chưa được ghé thăm sẽ được thêm vào một hàng đợi và
được tải về sau.
_ Tiếp theo đó, the Crawler sẽ chọn một trang mới để tải về và quá
trình được lặp đi lặp lại cho đến khi gặp một điều kiện chặn để
dừng quá trình.
2. Web Crawler đầu tiên:
Web Crawler đầu tiên được một sinh viên đang theo học tại
MIT-Matthew Gray tạo ra vào năm 1993. Vào tháng 6 năm đó, Gray
đã gửi mội tin nhắn đến www-talkmailing: “Tôi đã viết một perl script
dùng để lướt qua WWW collectingURLs sau đó theo dõi máy chủ mà
nó đã đi qua và tìm ra máy chủ mới. Cuối cùng, hack mã để trả về
những thông tin có ích hơn.(Hiện tại nó chỉ trả về URL), tôi sẽ sản
xuất một chỉ mục có thể tìm kiếm được về điều này”. Dự án thu thập
thông tin được gọi là WWWW( World Wide Web Wanderer), và được
sử dụng chủ yếu để nghiên cứu các đặc tính của web.
Vào tháng 6 năm 1994, Brian Pinkerton-một sinh viên học tiến
sĩ tại đại học Washinton, đăng một thông điệp trên tờ tin tức
comp.infosystems.announce như sau: “Bây giờ, chỉ mục của The
WebCrawler đã sẵn sàng để tìm kiếm! Chỉ số này rộng khắp: Nó chứa
thông tin từ nhiều máy chủ khác nhau theo khả năng mà nó có thể. Nó
là một công cụ tuyệt vời để định vị những máy chủ khác nhau từ một
máy chủ ban đầu ( vị trí máy chủ ban đầu được xác định thủ công). Chỉ
số hiện hành có được dựa trên nội dung của các tài liệu nằm trên 4000
máy chủ khác nhau trên toàn thế giới.” TheWebCrawler trở thành một
công cụ thương mại thành công. Các công cụ tìm kiếm dựa trên sự thu
thập thông tin TheWebCrawler bắt đầu xuất hiện: Lycos(1994),
Excite(1995), Altavista(1995) và Hotbot(1996). Lúc bấy giờ các cỗ
máy tìm kiếm đều thuê Crawler.
Lê Nguyễn Đoàn Trí – 0851010294
13/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
II. Các ứng dụng của WebCrawler:
Web Crawler có thể được sử dụng theo từng mục đích sau:
1. General Web Search (Tạo chỉ mục bao gồm các chủ đề rộng):
_ Được thực hiện bởi các công cụ tìm kiếm lớn, thu thập thông tin
cho một General Web Search phải đảm bảo giữ độ bao phủ (Nó
phải quét tất cả các trang có thể được sử dụng để trả lời cho các
truy vấn khác nhau) và chất lượng (Các trang phải có giá trị).
2. Vertical Web Search (Tạo chỉ mục cho các chủ đề cụ thể):
_ Tức là thiết lập các trang web mục tiêu trong giới hạn của một chủ
đề, một quốc gia hay một ngôn ngữ cụ thể. Trong đó Vertical
Crawler sẽ tập trung vào một tập hợp các trang web, tập hợp này có
thể được xác định theo địa lý, ngôn ngữ, mạng cục bộ.v..v. Ví dụ:
• Shopbot: được thiết kế để tải thông tin từ các danh mục mua
sắm trực tuyến và cung cấp giao diện so sánh giá theo cách tập
trung.
• News crawler: tập hợp các mục tin tức từ một nguồn đã được
xác định trước.
• Spambot: việc thu thập nhằm vào các địa chỉ email để được
chèn vào trang web.
_ Vertical Search còn bao gồm phân loại định dạng dữ liệu. Trong
trường hợp này The Crawler được điều chỉnh để thu thập tập hợp
các đối tượng thuộc loại được chỉ định cụ thể như: hình ảnh, âm
thanh, video...Ví dụ: Feed crawler: kiểm tra việc cập nhật thông tin
trong RSS/RDF files trong trang web.
_ Thu thập theo đề tài: trình thu thập tập trung vào một chủ đề cụ thể
cung cấp các chiến lược thu thập để tránh tải về các trang web
nhiều hơn mức cần thiết. Một Crawler dạng này nhận được một mô
tả đầu vào của một chủ đề, thường được mô tả bằng một câu truy
vấn chỉ hướng( a driving query) hay một tập các tài liệu mẫu. Có
hai chế độ hoạt động của Crawler dạng này là: Chế độ hàng loạt
(Batch mode-Thu thập các trang theo một chủ đề một cách định kỳ)
và chế độ theo yêu cầu (On Demand-Thu thập các trang theo định
hướng câu truy vấn của người dùng.
3. Thu thập đặc tính của Web (Web Characterization):
_ Thu thập đặc tính web bao gồm các nỗ lực để lấy được các thống kê
thuộc tính của các trang web. Những vấn đề khó khăn là xác định
đặc tính web. Điều gì tạo nên mẫu đại diện cho một trang web? Hay
những gì tạo nên một trang web của một quốc gia? Chiều sâu của
Lê Nguyễn Đoàn Trí – 0851010294
14/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
việc thu thập thông tin ảnh hưởng đến kết quả trả về. Những URL
hạt giống phải được chọn một cách cẩn thận.
4. Ánh xạ trang web (Mirroring-Giữ lại bản sao hoặc tái tạo trang web):
_ Mirroring là hành động giữ lại một phần hay toàn bộ nội dung
giống như bản sao của trang web. Một Crawler dùng để ánh xạ
thường khá đơn giản. Chính sách ánh xạ bao gồm: thời gian làm
mới (cập nhật lại bản sao) điển hình là hàng ngày hay hàng tuần và
thời gian trong ngày để thực hiện Mirroring.
5. Web archival (Lưu trữ nội dung):
_ Web archiving là một mirroring nhưng không cần loại bỏ những
bản sao đã lội thời, tức là toàn bộ lược sử của một trang được ghi
nhận. Dự án lưu trữ trang web lớn nhất là internet. URL
http://www.archive.org. Nó tập trung vào việc bảo vệ trạng thái của
các trang web trong từng năm. Tập hợp các trang của tháng 3/2006
gồm 55 tỷ trang.
6. Web Site Anaylysis (Phân tích trang web):
_ Web crawler có thể được dùng để phân tích một trang web và thậm
chí nó thể thay đổi nó theo một tiêu chuẩn định dạng sẵn. Ví dụ:
• Xác thực liên kết (Link Validation): Quét các trang web của một
website để xác định các liên kết hỏng.
• Xác thực mã (Code Validation): đảm bảo rằng tất cả các trang
của một website đúng dạng (well-formed).
• Phân thích cây của web (Web directories analysis): tìm những
trang không còn sẵn sàng (available) nữa.
_ Một công cụ phân tích website còn được dùng để tìm ra các lỗ hổng
của một website bao gồm việc tìm ra những phiên bản cũ hoặc chưa
được vá của những kịch bản thông dụng (popular script).
Lê Nguyễn Đoàn Trí – 0851010294
15/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
III. Kiến trúc của Web Crawler:
_ Trình thu thập thông tin gồm 3 module chính là : Downloader,
Storege, và Scheduler.
• Scheduler: Duy trì một hàng đợi các URL để lập lịch trình các
trang sẽ ghé thăm. Và có thể chi làm hai phần :
¾ Long-term Scheduling(kế hoạch dài hạn): Quyết định các
trang nào cần truy cập tiếp theo.
¾ Short-term Scheduling: Sắp xếp lại các trang để tráng tình
trạng quá tải cho máy chủ và thực hiện các nguyên tắc lịch sự
của web crawler. Việc này yêu cầu duy trì nhiều hàng đợi,
mỗi hàng đợi dành cho một website, và một danh sách các
trang để tải về trong mỗi hàng đợi.
• Downloader: Tải nội dung các trang.
• Storage: lập chỉ mục cho các trang và cung cấp lịch trình với các
siêu dữ liệu trên các trang đã truy hồi. Việc lưu trữ có thể chia
nhỏ làm 3 phần: Văn bản (rich text), siêu dữ liệu (metadata) và
liên kết (link).
IV. Những thắc mắc liên quan đến hoạt động của
WebCrawler:
Trong quá trình thu thập thông tin phục vụ cho bộ lập chỉ mục, ta
cần giải quyết những vấn đề sau :
Lê Nguyễn Đoàn Trí – 0851010294
16/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
1. Trong môi trường mạng, robot lấy thông tin từ các site. Vậy robot sẽ
bắt đầu từ site nào ?
Điều này hoàn toàn phụ thuộc vào robot. Mỗi robot khác nhau
sẽ có những chiến lược khác nhau. Thường thì robot sẽ viếng thăm các
site phổ biến hoặc những site có nhiều liên kết dẫn đến nó.
2. Ai sẽ cung cấp địa chỉ của các site này cho robot ?
_ Có 2 nguồn :
• Robot nhận các URL ban đầu từ user.
• Robot phân tích các trang web để lấy các URL mới, đến lượt các
URL này trở thành địa chỉ đầu vào cho robot. Quá trình này
được lặp lại liên tục.
3. Chọn dữ liệu nào trong tài liệu để lập chỉ mục ?
Quyết định chọn dữ liệu nào trong tài liệu cũng hoàn toàn phụ
thuộc vào robot, thường thì những từ được liệt kê như sau được xem là
quan trọng :
• Trong các đề mục
• Được in đậm (inktomi)
• Trong URL.
• Trong tiêu đề (quan trọng)
• Trong phần miêu tả trang web (description) .
• Trong các thẻ dành cho hình ảnh (ALT graphisc).
• Trong các thẻ chứa từ khóa.
• Trong các text liên kết.
Một số robot lập chỉ mục trên tiêu đề, hoặc một số đoạn văn
bản đầu tiên hoặc toàn bộ tài liệu (full text). Một số khác lại lập chỉ
mục trên các thẻ META(META tags) hoặc các thẻ ẩn, nhờ vậy tác giả
của trang web được quyền ấn định từ khoá cho tài liệu của mình. Tuy
nhiên chức năng này bị lạm dụng quá nhiều do đó các thẻ META
không còn giữ được giá trị ban đầu của chúng nữa.
V. Các thuật toán thu thâp dự liệu:
Trước khi các trang web được đánh chỉ mục, tất cả các trang web
phải được lấy về máy của robot. Để lấy được tất cả các trang web, robot
phải có chiến thuật. Từ một số trang web có sẵn, robot lọc ra danh sách
các liên kết, rồi từ đó dò tìm các trang khác.
Lê Nguyễn Đoàn Trí – 0851010294
17/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
Có 3 chiến thuật tìm kiếm Heuristic sau : tìm kiếm theo chiều sâu,
tìm kiếm theo chiều rộng và tìm kiếm ngẫu nhiên.
1. Tìm kiếm theo chiều sâu:
Lấy trang đầu tiên trong
danh sách.
Danh sách địa
chỉ các trang
đầu tiên.
Nếu có
Trang này đã xét tới chưa?
Nếu chưa
Nếu có, thêm vào
đầu danh sách.
Nếu không
Nếu rồi
Đánh dấu đã tới và xác
định xem có liên kết nào
trong trang đó không?
Nếu không
Kết thúc
Lê Nguyễn Đoàn Trí – 0851010294
18/70
Võ Nguyễn Minh Tuân - 0851010308
Tìm hiểu về Seach Engine
GVHD: Thầy Ninh Xuân Hương
2. Tìm kiếm theo chiều rộng:
Lấy trang đầu tiên trong
danh sách.
Danh sách địa
chỉ các trang
đầu tiên.
Nếu có
Nếu rồi
Nếu chưa
Nếu có, thêm vào
cuối danh sách.
Nếu
Trang này đã xét tới chưa?
Đánh dấu đã tới và xác
định xem có liên kết nào
trong trang đó không?
Nếu không
Kết thúc
3. Tìm kiếm theo ngẩu nhiên:
Danh sách địa
chỉ các trang
đầu tiên.
Lấy trang ngẫu nhiên
trong danh sách.
Nếu có
Nếu chưa
Nếu có, thêm vào
cuối danh sách.
Nếu
Trang này đã xét tới
Đánh dấu đã tới và xác
định xem có liên kết nào
trong trang đó không?
Nếu
Kết thúc
Lê Nguyễn Đoàn Trí – 0851010294
19/70
Võ Nguyễn Minh Tuân - 0851010308
- Xem thêm -
.PDF 
71 
623 
56 
