CHƯƠNG 1. LÝ THUYẾT CHUNG VỀ SEARCH ENGINE 1. TỔNG QUAN VỀ MẠNG INTERNET VÀ SEARCH ENGINE Không có định nghĩa chính xác nào về thông tin. Khái niệm thông tin gắn liền với sự ra đời của máy tính và ngành công nghệ thông tin.
Có thể hiểu thông tin là “tin tức hay sự thật về một cái gì đó”. Thông tin mang đến cho con người sự cảm nhận về thế giới bên ngoài. Tùy theo kiểu mẫu, nội dung, chất lượng, cách thức lưu trữ, cách truyền đạt…của thông tin mà ta có thể chia ra nhiều loại thông tin khác nhau. Sự ra đời của mạng Internet (mạng của các mạng máy tính) đã kéo theo một loại thông tin đó là thông tin mạng.
Thông tin trên mạng bao gồm rất nhiều kiểu, được lưu trữ ở khắp nơi trên thế giới. Dạng chính của thông tin trên mạng chính là các trang tài liệu được viết bằng ngôn ngữ đánh dấu siêu văn bản HTML(Hyper-Text Markup Language) mà ta quen gọi là trang Web (Web page). Tập hợp các trang Web tạo thành Web. Số lượng trang Web hiện tại là cực kỳ lớn.
Có thể đến hàng triệu tỷ pages, và do dó tổng dung lượng của tất cả các trang Web có thể đến hàng nghìn terabytes. Nội dung các trang Web có thể nhiều hoặc ít tùy theo trang, số người biên tập, số người sử dụng, quản trị …. Vì thế việc kiểm soát chúng là không đơn giản. Giữa một khối lượng thông tin khổng lồ như vậy, việc người dùng biết và chọn ra cho mình những thông tin cần thiết không hề dễ chút nào.
Người dùng sẽ phải bắt đầu khai thác nguồn thông tin khổng lồ này như thế nào? Thông thường người dùng sẽ sử dụng một công cụ cho phép truy cập các nguồn tài nguyên đó, gọi là trình duyệt Internet (Internet browser). Trình duyệt sẽ giao tiếp với các chương trình cung cấp thông tin dưới dạng trang Web gọi là Web server được chạy trên các máy tính lớn (server) của các nhà cung cấp thông tin. Trình duyệt và Web server giao tiếp với nhau bằng giao thức HTTP (Hyper-Text Transfer Protocol) là một giao thức truyền văn bản theo định dạng siêu văn bản. Trong tình huống này người dùng phải biết chính xác Web server nào có chứa thông tin mình cần đến, hay nói cách khác là địa chỉ của trang Web mà người dùng muốn truy cập.
Mỗi địa chỉ trang Web được gọi là một URL (Uniform Rescourse Locator). URL có cấu trúc: http://tên_máy_chủ.tên_miền/đường_dẫn_cục_bộ_đến_trang_Web. Một tập hợp các trang Web có chung tên miền được gọi là một Website (ví dụ như Website của trường đại học Quốc gia Hà nội có tên miền là vnu. Người dùng viếng thăm nhiều trang Web sẽ không thể nhớ hết các địa chỉ (thường là dài và khó nhớ).
Hơn nữa, sự ra đời của các trang Web mới là đáng kể, trong khi đó người dùng không biết LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 đến chúng nếu như không được chỉ dẫn. Trong trường hợp người dùng không biết địa chỉ của trang Web có chứa thông tin mà họ cần, họ sẽ phải bắt đầu như thế nào? Hai câu trả lời là danh bạ Web (Web directory) và mô tơ tìm kiếm thông tin trên mạng (Search engine). Danh bạ Web là một Web site chứa các liên kết đến rất nhiều trang Web khác nhau trên thế giới, được sắp xếp theo các chủ đề. Người dùng truy cập danh bạ Web và lần theo các chủ đề, rồi các chủ đề con, … họ sẽ có được một danh sách các trang Web về lĩnh vực mà họ quan tâm.
Một trong số các Website cung cấp danh bạ Web tốt nhất hiện nay là Yahoo (http://www. Chẳng hạn ta có thể tìm thấy địa chỉ trang Web của hầu hết các trường đại học trên thế giới trong mục Education của Yahoo. Search Engine không cung cấp danh sách các trang Web như Web directory. Mỗi khi người dùng cần thông tin mà không biết địa chỉ trang Web, họ sẽ truy cập Search Engine ưa thích của họ bằng trình duyệt (bản thân Search Engine cũng là một Web site), nói cho Search Engine biết họ cần thông tin gì bằng cách nhập vào các từ khóa cho thông tin cần tìm.
Từ khóa ở đây là từ ngữ thông thường có liên quan đến thông tin cần tìm. Chẳng hạn muốn tìm thông tin về Search Engine có thể sử dụng từ khóa “Search”, “Search engine”, … Search Engine sẽ tiến hành phân tích yêu cầu tìm kiếm đó, thực hiện tìm theo sự hiểu biết của nó (tìm trên cơ sở dữ liệu về Web mà nó có được) và trả lại cho người dùng danh sách các URL dẫn đến các trang Web mà nó tìm được (đã có sự sắp xếp) và một phần nội dung được trích rút ra (extractor) từ trang Web có chứa từ khóa cần tìm. Đứng trên khía cạnh này thì Search Engine chính là một Search Engine trả lời câu hỏi QAM (Question Answer Machine). Ngày nay, khái niệm Search Engine đã trở nên khá phổ biến và Search Engine là một trong số những công cụ (dịch vụ) được người dùng sử dụng nhiều nhất trên mạng Internet.
Google (http://www.com) là một trong số các Search Engine cho các kết quả tìm kiếm chính xác nhất hiện nay. CÁC MÔ HÌNH KIẾN TRÚC CỦA SEARCH ENGINE 1. Mô hình kiến trúc chung Hình sau đây đưa ra kiến trúc mức cao của một Search Engine, trong đó các thành phần của kiến trúc này đảm nhiệm các chức năng khá cụ thể: LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Mô hình kiến trúc chung của Search engine[14] Crawler là chương trình có nhiệm vụ khám phá và tải về các trang Web từ mạng Internet.
Chúng dõi theo các trang Web giống như người dùng duyệt Web. Crawler xuất phát với tập các URLs khởi đầu, sau khi tải các trang Web về, Crawler tách các URLs trong trang Web đó ra, chuyển cho Crawl Control (Bộ điều khiển crawl). Bộ điều khiển sẽ quyết định liên kết nào sẽ được khám phá tiếp theo và trả lại cho crawler. Crawler cũng đồng thời chuyển các trang Web đã khám phá được vào kho dữ liệu Web (pages repository) và tiếp tục khám phá Web cho tới khi nào không còn gì để khám phá hoặc bị cạn tài nguyên hay được lệnh dừng, … Giải thuật cơ bản này có thể được sửa chữa nhằm đạt được hiệu quả tốt nhất theo một nghĩa nào đó.
Ví dụ crawler của một Search Engine nào đó được thiết kế để khám phá càng nhiều Web site càng tốt, bỏ lại các trang Web bị “vùi sâu” trong một site (đường đến các trang Web này dài và phức tạp) trong khi crawler của một Search Engine khác lại được giao nhiệm vụ khám phá một vùng (domain) nào đó. Bộ điều khiển crawler nắm giữ vai trò điều khiển, hướng hoạt động cho các crawlers. Khi Search Engine ít nhất một lần hoàn thành một vòng crawl, bộ điều khiển có thể nhận được thông báo bởi vài chỉ mục (indexes) được tạo ra trong quá trình khám phá trước đó. Bộ điều khiển căn cứ vào chỉ mục để quyết định xem những liên kết nào nên viếng thăm, những liên kết nào nên bỏ qua.
Bộ điều khiển đôi khi sử dụng thông LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 tin phản hồi từ phía Query Engine để điều khiển crawler (được thể hiện qu mũi tên nối Query Engine và Crawl control trong mô hình kiến trúc). Việc viếng thăm lại một trang Web nào đó để kiểm tra xem trang Web đó có cập nhật thông tin gì mới đòi hỏi tài nguyên khá lớn. Nó sẽ bao gồm những công việc kết nối đến Website, tải dữ liệu về và so sánh với dữ liệu cũ đã có để chống trùng. Sau khi kiểm tra việc dữ liệu có bị lặp giữa một trang với nhau và các nguồn khác nhau, chương trình mới quyết định có cập nhật hay không.
Như vậy, việc này đòi hỏi tiêu tốn cả CPU bên crawler, đường truyền mạng và cả thời gian trả lời của host chứa thông tin, thời gian để kiểm tra xem dữ liệu có trùng không. Trong lĩnh vực các trang Web dạng báo chí (news) hiện tượng trùng lặp thông tin do các báo dẫn lại thông tin của nhau hiện nay là rất nhiều. Trong lĩnh vực hàng hóa hoặc rao vặt, việc request kiểm tra cập nhật cho các trang con dễ làm Server bên phục vụ quá tải. Bởi vì những trang Web này có rất nhiều trang con vì mỗi sản phẩm được rao bán đòi hỏi phải có một trang con riêng biệt, và có rất nhiều sản phẩm được rao bán và do đó, mỗi khi Crawler gửi yêu cầu (request) đến, các Website loại này đều phải tạo những trang con có nội dung để trả lời.
Nếu bên Crawler sử dụng quá nhiều server và gửi quá nhiều request thì nó cũng chẳng khác DDOS bao nhiêu. Tất nhiên, tốc độ cập nhật của các trang Web khác nhau cũng rất khác nhau. Với những trang báo như Vnexpress.net thì thời gian cập nhật sẽ nhanh hơn rất nhiều so với những trang Web của các trường đại học như coltech. Do đó, việc cập nhật các trang Web với khoảng thời gian bao lâu, việc thỏa thuận giữa phía crawler với bên server chứa thông tin cũng cần phải được tính toán và cân nhắc.
Indexer module (mô-đun đánh chỉ mục) tách các từ cần thiết có trong mỗi trang Web, ghi lại URL của trang Web có chứa chúng. Kết quả là hình thành nên một bảng tra cứu mà từ các URLs có thể biết được các từ có trong văn bản của URL đó. Index có thể coi là một cách tái tổ chức lại văn bản theo một cách riêng để phục vụ cho việc tìm kiếm. Với một cách tổ chức dữ liệu khác nhau, ta có thể có cách tìm kiếm khác nhau Collection analysis module (mô-đun phân tích tập) Một module phân tích tập các Index nhằm rút ra các thông tin quan trọng có thể tính off_line với mục đích cho việc tìm kiếm dễ dàng và nhanh chóng hơn.
Utility index trong hình vẽ được tạo ra bởi collection analysis module. Ví dụ như utility index cho biết các trang Web có có chiều dài, mức độ quan trọng hay thậm chí là số lượng ảnh có trong nó cho trước. Collection analysis module sử dụng text index và structure index để tạo ra utility index. Trong quá trình khám phá Web và đánh chỉ mục, Search Engine có thể sẽ lưu trữ lại các trang Web mà nó tải về từ mạng.
Kho dữ liệu trang Web (Page repository) trong hình vẽ dùng để lưu trữ tập các trang Web này một cách tạm thời. Đôi khi, LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 Search Engine bảo lưu cả nội dung của trang Web mà nó viếng thăm (cache) ngoài việc đánh chỉ mục các trang Web. Cache sẽ giúp ích trong việc đưa ra các kết quả nhanh chóng và mang lại một số thuận lợi trong việc tìm kiếm.