Luận văn Nghiên cứu máy tìm kiếm và xây dựng thử nghiệm mô phỏng máy tìm kiếm

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN Tel. (84-511) 3736 949, Fax. (84-511) 842 771 Website: itf.ud.edu.vn, E-mail: cntt@ud.edu.vn LUẬN VĂN TỐT NGHIỆP NGÀNH CÔNG NGHỆ THÔNG TIN MÃ NGÀNH : 05115 ĐỀ TÀI: NGHIÊN CỨU MÁY TÌM KIẾM VÀ XÂY DỰNG THỬ NGHIỆM MÔ PHỎNG MÁY TÌM KIẾMTìm hiểu và xây dựng máy tìm kiếm SINH VIÊN : PHAN TẤN LUẬN LỚP : 04T1 CBHD : TS.NGUYỄN THANH BÌNH ĐÀ NẴNG, 06/2009 LỜI CẢM ƠN Để hoàn thành được đồ án này, em đã nhận được sự chỉ bảo tận tình của các Thầy Cô giáo trong khoa Công nghệ Thông tin trường Đại học Bách Khoa, cùng sự giúp đỡ động viên của gia đình và bạn bè. Trước tiên em xin chân thành cảm ơn tất cả các thầy cô của trường Đại học Bách Khoa, Đại học Đà Nẵng đã dạy dỗ và truyền đạt kiến thức cho em trong thời gian học tại trường. Em xin chân thành cám ơn Tiến sĩ Nguyễn Thanh Bình, thầy đã tận tình hướng dẫn góp ý cho em trong quá trình thực hiện đồ án này. Nhờ đó mà em có thể hoàn thành theo đúng yêu cầu về nội dung của một đồ án tốt nghiệp. Em cũng xin được cám ơn những người bạn cùng ngành đã động viên giúp đỡ em trong suốt thời gian làm đồ án. Cuối cùng, con xin cảm ơn gia đình đã tạo mọi điều kiện tốt nhất để bản thân có thể hoàn thành được đồ án đúng hạn. Mặc dù đã cố gắng hết sức, nhưng vì khả năng và thời gian có hạn, đề tài nghiên cứu chắc chắn còn nhiều khiếm khuyết. Rất mong các Thầy Cô giáo chỉ bảo giúp đỡ. Rất mong sự góp ý của bạn bè, đồng nghiệp. Đà Nẵng, 06/2009 Sinh viên Phan Tấn Luận LỜI CAM ĐOAN Em xin cam đoan: Những nội dung trong báo cáo này là do em thực hiện dưới sự hướng dẫn của thầy TS.Nguyễn Thanh Bình. Mọi tham khảo dùng trong báo cáo này đều được trích dẫn rõ ràng tên tác giả, tên công trình, thời gian, địa điểm công bố. Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá,tôi xin chịu hoàn toàn trách nhiệm. Sinh viên, Phan Tấn Luận NHẬN XÉT CỦA CÁN BỘ HƯỚNG DẪN NHẬN XÉT CỦA CÁN BỘ DUYỆT MỤC LỤC MỤC LỤC HÌNH ẢNH Hình 1 Giao diện của google search engine 2 Hình 2 Giao diện của xalo.vn search engine 3 Hình 3 Sơ đồ Use Case ban đầu của hệ thống 6 Hình 4 Tổng quan hệ thống tìm kiếm 8 Hình 5 Biểu đồ trạng thái của một liên kết 13 Hình 6 Quá trình đánh chỉ mục 16 Hình 7 Các bước phân tích tài liệu 16 Hình 8 Vòng đời của một Thread 28 Hình 9 Bảng trong Html 33 Hình 10 Sơ đồ thành phần tổng quan của hệ thống 37 Hình 11 Cấu trúc của Crawler 39 Hình 12 Sơ đồ use-case của gói crawler 39 Hình 13 Sơ đồ Usecase của việc quản lý các liên kết gốc 40 Hình 14 Sơ đồ trạng thái thêm mới các liên kết gốc 41 Hình 15 Sơ đồ trạng thái của tác vụ chỉnh sửa một liên kết gốc 42 Hình 16 Sơ đồ trạng thái xóa liên kết gốc 43 Hình 17 Sơ đồ usecase cho tác vụ quản lý các liên kết đã tải về máy 44 Hình 18 Sơ đồ usecase quản lý danh sách các thư mục chứa tài liệu 46 Hình 19 Sơ đồ tổng thể các thành phần của gói reader 48 Hình 20 Sơ đồ hoạt động của gói indexer 49 Hình 21 Sơ đồ hoạt động của gói Searcher và ứng dụng web 50 Hình 22 Sơ đô tuần tự của hệ thống 51 Hình 23 Sơ đồ mô tả hoạt động Crawler 53 Hình 24 Trạng thái hoạt động của gói reader 54 Hình 25 Sơ đồ tuần tự của gói indexer 55 Hình 26 Sơ đồ hoạt động của chức năng đọc file robot.txt 56 Hình 27 Sơ đồ hoạt động của chức năng tải tài liệu về máy 57 Hình 28 Sơ đồ hoạt động của chức năng tạo công việc mới 59 Hình 29 Sơ đồ hoạt động truy xuất các liên kết 61 Hình 30 Màn hình crawler đang hoạt động tải các dữ liệu về máy 68 Hình 31 Màn hình khi hệ thống thực hiện các công việc cũ 70 Hình 32 Danh sách các dữ liệu do crawler tải về 71 Hình 33 Kết quả trả về với câu truy vấn “Java Tutorial” 72 Hình 34 Trang web nguồn của kết quả đầu tiên 73 MỤC LỤC CÁC BẢNG Bảng 1 Bảng xếp hạng search engine năm 2009 2 Bảng 2 Các gói chính trong thư viện mã nguồn mở Lucene 21 Bảng 3 Các giao thức thường gặp 24 Bảng 4 Các thành phần của một URL 25 Bảng 5 Danh mục các bảng trong cơ sở dữ liệu 62 Bảng 6 Bảng chứa thông tin địa chỉ gốc 63 Bảng 7 Bảng lưu thông tin các địa chỉ được tải về 64 Bảng 8 Bảng lưu trữ thông tin của các thư mục chứa tài liệu tải về 65 Bảng 9 Bảng mô tả các lớp chính của chương trình 66 Chương 1 TỔNG QUAN ĐỀ TÀI GIỚI THIỆU CHUNG VỀ VẤN ĐỀ NGHIÊN CỨUMáy tìm kiếm Hiện nay Internet là nguồn tài nguyên vô tận của nhân loại chỉ cần vài lần nhấp chuột ta có thể tiếp cận được những nguồn tài liệu mong muốn. Để tiếp cận được tài liệu thích hợp ta nhờ vào các máy tìm kiếm (search engine) vì vậy máy tìm kiếm chiếm lĩnh một vị trí vô cùng quan trọng trong thời đại thông tin. Các máy tìm kiếm thông dụng ngày nay đầu tiên phải nói đến Google, Yahoo, MSN-Live. Để xây dựng được một hệ thống như vậy vô cùng phức tạp và nó là đề tài luôn được nghiên cứu để tìm giải pháp tối ưu nhất. Lịch sử phát triển Năm 1990 công cụ tìm kiếm đầu tiên được ra đời là Archie-phát triển bởi Alan Emtage sinh viên đại học McGill, Montreal. Archie cũng bao gồm các thành phần như các máy tìm kiếm ngày nay, đó là dò tìm tài liệu, thiết lập chỉ mục, xây dựng giao diện tìm kiếm. Archie chỉ đánh chỉ mục với tên file bằng cách download về tất cả các thư mục liệt kê danh sách các file nằm trên FTP site. Năm 1991 máy tìm kiếm Gopher được đưa ra bởi Mark McCahill tại đại học Minnesota. Máy tìm kiếm Gopher có thể đánh chỉ mục tên toàn văn bản text đơn giản. Năm 1993 World Wide Web Wanderer xuất hiện, được biết đến như là robot đầu tiên. Nhiệm vụ của nó là đếm để ước lượng số lượng các web Năm 1994 WebCrawler được giới thiệu. Đây là máy tìm kiếm full-text đầu tiên tức là tìm kiếm trên toàn bộ phần văn bản. Năm 1995 máy tìm kiếm Alta Vista ra đời, công cụ đầu tiên cho phép sử dụng các câu truy vấn là ngôn ngữ tự nhiên. Mặc dù thất bại sau này nhưng Alta vista vẫn thực sự ấn tượng có thể nói Alta vista là một Google thời bấy giờ Năm 1996 công ty Inktomi được khởi đầu tại UC Berkeley và vào tháng 6 năm 1999, công ty Inktomi giới thiệu một thư mục tìm kiếm dựa trên công nghệ "concept induction". Theo như giới thiệu của công ty này thì "concept induction" có khả năng tiến hành phân tích thói quen của người sử dụng để đưa ra các trang gợi ý. Năm 1997 Google ra mắt như một dự án nghiên cứu tại trường Đại học Stanford bởi hai nhà sáng lập Sergey Brin và Larry Page. Dường như Google là máy tìm kiếm thống lĩnh ngày nay. Năm 1998 MSN Search và Open Directory ra đời. Giới thiệu về các máy tìm kiếm thông dụng Bảng 1 Bảng xếp hạng search engine năm 2009 Thế giới google.com Hình 1 Giao diện của google search engine Google được xem như là máy tìm kiếm thống trị thế giới hiện nay. Việt Nam xalo.vn Hình 2 Giao diện của xalo.vn search engine Xalo.vn là một Máy tìm kiếm (search engine) được Tinhvân Media phát triển với tham vọng Xalo.vn sẽ trở thành công cụ tìm kiếm tiếng Việt hàng đầu của Việt Nam. Xalo.vn hiện tại đang cung cấp 7 dịch vụ tìm kiếm bao gồm: - Tìm kiếm Web: dịch vụ tìm kiếm thông tin tổng hợp trên dữ liệu gần 100 triệu trang văn bản tiếng Việt hiện có trên các Website của Việt Nam - Tìm kiếm Tin tức: dịch vụ tổng hợp tin tức và tìm kiếm thông tin trên dữ liệu dạng tin tức được tổng hợp từ gần 70 trang tin điện tử hàng đầu của Việt Nam - Tìm kiếm Diễn đàn: dịch vụ tìm kiếm cho phép người dùng tìm kiếm thông tin từ hơn 100 diễn đàn lớn nhất của Việt Nam hiện tại. - Tìm kiếm Ảnh: dịch vụ tìm kiếm hình ảnh trên số lượng hơn 20 triệu hình ảnh được người dùng Việt Nam đưa lên Internet. - Tìm kiếm Blog: dịch vụ tìm kiếm cho phép người dùng tìm kiếm thông tin trên hầu hết các mạng xã hội được cung cấp bởi Việt Nam cũng như trên thế giới mà người Việt Nam hay sử dụng - Tìm kiếm Nhạc: dịch vụ tìm kiếm dữ liệu Nhạc từ các Website nghe nhạc trực tuyến lớn nhất Việt Nam hiện tại. - Tìm kiếm Rao vặt: dịch vụ tổng hợp và tìm kiếm thông tin rao vặt từ hơn 20 Website mua bán rao vặt lớn nhất Việt Nam Với các dịch vụ cung cấp và tính năng khác biệt cho từng dịch vụ, Xa Lộ đang không ngừng được hoàn thiện để có thể phục vụ tốt nhất nhu cầu tìm kiếm của người dùng Internet Việt Nam và trở thành máy tìm kiếm tiếng Việt hàng đầu của Việt Nam. LÝ DO CHỌN ĐỀ TÀI Mục tiêu và ý nghĩa của đề tài Xử lý ngôn ngữ tự nhiên là một nhánh của lĩnh vực trí tuệ nhân tạo và có thể nói đây là phần khó nhất trong lĩnh vực trí tuệ nhân tạo vì nó liên quan đến việc phải hiểu ngôn ngữ-công cụ hoàn hảo của tư duy và giao tiếp. Các bài toán và ứng dụng của nhánh xử lý ngôn ngữ bao gồm: Nhận dạng chữ viết Nhận dạng tiếng nói Tổng hợp tiếng nói Dịch tự động Tìm kiếm thông tin Tóm tắt văn bản Khai phá dữ liệu Đây là các bài toán được rất nhiều chuyên gia quan tâm phát triển, vì tính ứng dụng của nó rất thiết thực trong đời sống xã hội. Ngay từ khi còn ngồi trên ghế nhà trường em mong một ngày nào đó sẽ được làm việc trong nhánh xử lý ngôn ngữ. Với mong ước đó trong thời gian qua em đã định hướng sẽ thực công việc có liên quan đến một phần nhỏ của lĩnh vực đó là nghiên cứu tìm hiểu phần tìm kiếm thông tin, tìm hiểu những công nghệ mới để có thể xây dựng được một máy tìm kiếm toàn văn. Trong thời đại công nghệ số như hiện nay, các nguồn tài liệu là vô cùng phong phú đa dạng. Mỗi giây sẽ có rất nhiều, rất nhiều thông tin được đưa lên làm giàu cho nguồn tài nguyên vô tận này. Nguồn tài nguyên càng nhiều thì dĩ nhiên là không thể thiếu công cụ tìm kiếm và công việc tìm kiếm càng khó hơn đòi hỏi các máy tìm kiếm phải phát triển không ngừng. Vì lý do đó mà có rất nhiều máy tìm kiếm ra đời, phục vụ cho nhu cầu thiết thực này. Làm thế nào mà chỉ trong tích tắc các máy tìm kiếm có thể đưa về hàng nghìn kết quả tương ứng với truy vấn của người dùng. Các máy tìm kiếm dùng các công nghệ nào, thuật toán nào mà có thể thực hiện được như vậy? Đó là câu hỏi mà em luôn tự hỏi và muốn nghiên cứu tìm hiểu. Quay về một phạm vi nhỏ hơn. Chẳng hạn như ta có một website chứa rất nhiều tài liệu và muốn hỗ trợ công cụ tìm kiếm cho người dùng. Thông thường thì ta sử dụng tìm kiếm toàn văn (full-text) mà các hệ quản trị cơ sở dữ liệu cung cấp. Sẽ có rất nhiều hạn chế như chỉ tìm được trên dữ liệu ở bên trong hệ quản trị cơ sở dữ liệu, hạn chế về câu truy vấn vì phụ thuộc vào cú pháp của mỗi cơ sở dữ liệu, không tìm được trên các dữ liệu phi cấu trúc, tốc độ xử lý trên một cơ sở dữ liệu lớn sẽ rất chậm v.v…Với các lý do đó ta cần xây dựng một hệ thống tìm kiếm cho website của mình tương tự như các máy tìm kiếm. Bởi vì mục đích và ý nghĩa như trên em chọn cho mình đề tài:”Nghiên cứu tìm hiểu máy tìm kiếm và xây dựng chương trình mô phỏng một máy tìm kiếm”sửa lại tên đề tài . Nhiệm vụ cần phải thực hiện Xây dựng chức năng Tự động thu thập tài liệu Từ một hay nhiều địa chỉ liên kết ban đầu, chương trình tự động theo tất cả các liên kết có trong liên kết ban đầu để truy xuất tài liệu. Một liên kết được tìm thấy sẽ đóng vai trò như một liên kết ban đầu mới. Công việc cứ diễn ra khi ta tìm hết tất cả các liên kết. Có hai tùy chọn: một chỉ tìm các liên kết cùng tên miền, hoặc cho phép theo những liên kết khác tên miền. Các tài liệu tìm thấy thường ở các dạng chính .html, .pdf, .doc sẽ được tải về lưu trữ trên máy. Xây dựng chức năng xử lý tài liệu thành các văn bản thuần túy (plaintext) Từ kho tài liệu đã tìm được, hệ thống sẽ xử lý đưa về định dạng đơn giản nhất là văn bản thuần túy. Để phục vụ cho các bước phân tích sau. Lập chỉ mục cho các tài liệu đã tìm được Từ các văn bản thuần túy đã truy xuất ra được ta sẽ thực hiện các bước như đưa tất cả về chữ thường, phân tích văn bản thành từng đơn vị từ vựng, loại bỏ các stopwords, thực hiện đưa văn bản về thành từ gốc (stemming, chỉ thực hiện phần này trong Tiếng Anh), tính trọng số của từ, loại bỏ những từ có trọng số thấp. Tiến hành lập các tập tin chỉ mục đảo cho các thông tin vừa tìm được Tìm kiếm tài liệu Từ các chỉ mục đảo ta có thể xây dựng ứng dụng tìm kiếm cho tài liệu ta thu thập được ở dạng tìm kiếm toàn văn. Hệ thống nhận truy vấn từ người dùng, truy vấn sẽ được phân tích qua các bước như: đưa về chữ thường loại bỏ, stopword. Sau đó tiến hành tìm kiếm, trả về kết quả được sắp xếp theo độ tương đồng với câu truy vấn giảm dần. Từ nhiệm vụ như trên ta có sơ đồ usecase tổng quát Hình 3 Sơ đồ usecase ban đầu của hệ thống Đây chỉ là sơ đồ hình dung ban đầu, vì thế có thể được thay đổi trong các bước phân tích sau. Xây dựng ứng dụng web Xây dựng giao diện giao tiếp giữa hệ thống và người sử dụng. Người sử dụng ở đây gồm người quản trị hệ thống, và người tìm kiếm. Người quản trị hệ thống sẽ có các chức năng vận hành hệ thống còn người dùng thì sẽ nhập câu truy vấn và nhận kết quả trả về. Hướng nghiên cứu của đề tài Về mặt lý thuyết Nắm được các lý thuyết liên quan đến lĩnh vực tìm kiếm thông tin. Công cụ xây dựng đề tài Về mặt cơ sở lý thuyết: các nguồn tài liệu tham khảo trên các trang web, sách ngôn ngữ lập trình, các giáo trình và kết thức trau dồi trong thời gian học tại trường… Công cụ thiết kế phần mềm: Eclipse version 3.3, Mysql, Poseidon for UML PE 6.0.2, ArgoUML Công cụ quản lý đề tài, mã nguồn: Maven2, Lucene, TortoiseSVN Công cụ Test: JUnit Dự kiến kết quả đạt được Xây dựng mô phỏng được một hệ thống máy tìm kiếm: Tải được nội dung các trang html. Từ một trang web gốc hệ thống sẽ tự tìm ra tất cả các siêu liên kết tới các trang web đó, download các loại định dạng (contentType) cơ bản như: text/html, application/pdf, application/doc… về máy. Các file sẽ được lưu trữ theo từng thư mục được đặt tên theo tên host của liên kết. Địa chỉ các trang web sẽ được mã hóa để có thể đặt tên cho nó ở trên đĩa. Xây dựng hệ thống đọc file dựa theo phần đuôi mở rộng. Tùy vào các định dạng file sẽ có các lớp đọc thích hợp. Chủ yếu đọc các file thông dụng như: html, htm, pdf, doc, rtf, xml, txt…còn các file dạng khác sẽ chỉ đánh chỉ mục theo tên của file và địa chỉ của nó. Phân tích các tài liệu đã thu thập được bóc tách phần văn bản thuần túy (plaintext). Sử dụng thư viện mã nguồn mở Lucene để đánh chỉ mục cho các tài liệu. Phân tích chuỗi tìm kiếm của người dùng. Tìm kiếm được trên các trang html và trong toàn nội dung tập tin. Trả về kết quả thích hợp Chương 2 CƠ SỞ LÝ THUYẾT LÝ THUYẾT LIÊN QUAN ĐẾN ĐỀ TÀI Tổng quan hệ thống máy tìm kiếm Hình 4 Tổng quan hệ thống tìm kiếm Giới thiệu Thuật ngữ search engine thường được dùng để mô tả cho cả crawler-based search engine và human-powered directory. Đây là hai loại máy tìm kiếm mà chúng thu thập chỉ mục theo các cách khác nhau. Crawler-based search engines Crawler-based search engines chẳng hạn như Google, tạo chỉ mục một cách tự động. Họ “crawl” và “spider” các trang web và sau đó chúng ta tìm trên hệ thống chỉ mục họ thu thập được. Khi ta thay đổi nội dung của trang web thì crawler-base search engine sẽ có thể tìm ra các thay đổi và điều đó sẽ ảnh hưởng đến trang web sẽ được xếp hạng như thế nào. Human-powered directory Human-powered directory chẳng hạn như Open Directory phụ thuộc vào nhân tố con người trong khi lập chỉ mục. Ta sẽ gửi một bản mô tả ngắn về trang web của ta đến human-powered directory, hoặc các nhà biên soạn cho các máy tìm kiếm này sẽ ghi lại một bản mô tả nội dung trang web mà họ đã xem qua. Kết quả phù hợp khi ta tìm kiếm sẽ phụ thuộc vào các bản mô tả này. Lập chỉ mục theo dạng này thì khi ta thay đổi nội dung của trang web thì sẽ chẳng ảnh hưởng gì đến chỉ mục đã được thực hiện. Ngoại trừ những trang web hay, trang web có nội dung bổ ích và phổ biến thì có khả năng được mô tả lại thường xuyên. Ngày nay các máy tìm kiếm không còn phân biệt rõ ràng là crawler-based search engine hay human-powerd directory. Bởi vì kết quả tìm kiếm trả về dựa trên cả hai dữ liệu. Chẳng hạn MSN Search trước kia là human-powered directory tuy nhiên ngày nay nó vẫn hiển thị các kết quả theo crawler-based search engine (được cung cấp bởi công ty Inktomi) cho các truy vấn phức tạp hơn. Crawler-based search engine thường bao hàm 3 thành phần chính. Đầu tiên là spider hay đôi khi còn gọi là crawler, wanderer…Crawler sẽ truy cập vào một trang web, đọc nội dung, và sau đó theo các liên kết có đi tới các trang khác bên trong site. Spider sẽ trở lại các website này theo một nguyên tắc đặt ra trước, có thể là mỗi tháng hay hai tháng để tìm kiếm các thay đổi. Những gì mà crawler thu thập được sẽ được đưa vào phần thứ hai của máy tìm kiếm để lập thành chỉ mục. Chỉ mục (index hay đôi khi còn được gọi là catalog, giống như là một quyển sách khổng lồ chứa tất cả những bản copy của mỗi trang web mà spider tìm thấy. Nếu một trang web thay đổi, thì quyển sách này sẽ được cập nhật các nội dung mới. Thường thì sẽ mất một khoảng thời gian các trang web mới, hay các thay đổi mà spider tìm thấy được thêm vào chỉ mục. Vì vậy, một trang web có thể đã được “spider” nhưng chưa được đánh chỉ mục. Khi chưa được đánh chỉ mục thì dĩ nhiên nó sẽ không tồn tại trên các kết quả tìm kiếm. Ứng dụng web là thành phần thứ ba trong máy tìm kiếm. Nó là chương trình mà sẽ duyệt qua hàng tỉ trang web được ghi lại trong bảng chỉ mục để tìm kiếm kết quả phù hợp cho một truy vấn và sắp xếp các kết quả theo một trật tự được cho là tương thích nhất. Search engine tìm kiếm trên hàng hàng tỉ trang web và trả về các kết quả phù hợp với người dùng mong muốn. Dĩ nhiên không phải lúc nào kết quả trả về cũng đúng đắn. Search engine không có khả năng hỏi vài câu hỏi để tập trung vào chủ đề tìm kiếm hay cũng chẳng thể nào dựa vào đánh giá cũng như kinh nghiệm cho các lần tìm kiếm trước như cách của con người. Search engine dựa tất cả vào thuật toán khi nó phải đối diện với hàng tỉ trang web cần phải sắp xếp. Hầu như các thuật toán cụ thể của các máy tìm kiếm làm việc như thế nào đều được giữ kín không tiếc lộ. Tuy nhiên các search engine đều tuân theo các các quy tắc chung. Các quy tắc này sẽ được trình bày ở phần sau. Bộ thu thập tài liệu-Crawler Đặc điểm hoạt động của Crawler Từ một hay nhiều các liên kết ban đầu, Crawler lên đường thực hiện công việc “lùng sục” Internet của mình. Crawler tải về nội dung các trang web từ các liên kết đã nhận ban đầu và truy xuất các liên kết mới nằm trong nội dung của các trang này. Các liên kết mới này sẽ được nạp vào một trình điều khiển (Crawler Manager). Crawler Manager sẽ quyết định các liên kết nào sẽ được viếng thăm kế tiếp, Crawler Manager sẽ nạp chúng vào hàng đợi để chờ xử lý. Các liên kết này sẽ được quản lý trong cơ sở dữ liệu để thuận tiện cho công việc cập nhật thông tin mới. Trong một lần thực hiện thì các liên kết phải chỉ được truy cập một lần để tăng khả năng hoạt động và tránh trùng lặp nội dung. Một crawler đi qua bốn bước cơ bản: Bắt đầu từ một hay nhiều liên kết Tải nội dung Phân tích nội dung, tìm liên kết, đi theo các liên kết Theo dõi liên kết, tránh trùng lặp Có nhiều chế độ làm việc cho crawler thực hiện nhiệm vụ truy tìm thông tin. Các chế độ được phân biệt theo nhiều cách. Các đặc điểm phân biệt có thể là: Batch Mode Incremental Mode Batch mode Crawler sẽ đánh chỉ mục liên tục các trang web và không tải nội dung về để lưu trữ. Cách này nội dung luôn được cập nhật nhưng chỉ phù hợp cho lượng trang web nhỏ có giới hạn. Chẳng hạn như mục tiêu của crawler được định ra là thực hiện trên một số website cụ thể nào đấy. Crawler chỉ có nhiệm vụ liên tục chạy qua các wesiste này để cập nhật các nội dung mới. Incremental Mode hoạt động ở chế độ này crawler sẽ không bao giờ xóa các nội dung lưu trữ. Khi gặp một tài liệu được cho là đã viếng thăm thì crawler sẽ tuân theo chiến lược cập nhật nội dung đã được cài đặt. Ở chế độ này thì crawler cần phải có kho lưu trữ tài liệu thật lớn. Breadth-first(Tìm kiếm theo chiều rộng) Depth-first(Tìm kiếm theo chiều sâu) Tìm kiếm theo chiều rộng Tìm tất cả các liên kết ở cùng cấp trước khi đi sâu hơn tìm tất cả các liên kết ở cấp tiếp theo. Cấu trúc dữ liệu cho thuật toán này là hàng đợi vào sau ra trước. Tìm kiếm theo chiều sâu Tìm tất cả các liên kết trong một nhánh trước khi tìm các liên kết ở nhánh tiếp theo. Randomized PageRank Randomized Tìm kiếm một cách ngẫu nhiên PageRank Tìm các trang quan trọng trước. Các trang quan trọng là các trang được dẫn tới từ nhiều trang khác. Tính năng bắt b