Tìm hiểu search engine và xây dựng ứng dụng minh họa

  • Số trang: 71 |
  • Loại file: PDF |
  • Lượt xem: 91 |
  • Lượt tải: 0
sakura

Đã đăng 9677 tài liệu

Mô tả:

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 -