›
›

Luận văn Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt

pdf 150 trang phuongnguyen 1480
Download
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfluan_van_tim_hieu_ve_search_engine_va_xay_dung_ung_dung_minh.pdf

Nội dung text: Luận văn Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt

  1. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt
  2. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt LỜI CẢM ƠN Đầu tiên, chúng em xin gởi lời cảm ơn đến Thầy, Cô khoa Công nghệ Thông tin trường Đại học Khoa học Tự nhiên đã tận tình dạy dỗ, dìu dắt chúng em suốt bốn năm đại học. Chúng em cảm ơn Cô Nguyễn Thị Diễm Tiên, người tận tình hướng dẫn, giúp đỡ, động viên chúng em hoàn thành luận văn này. Chúng tôi cảm ơn các anh Trần Nguyễn Hoàng Phương, Bùi Ngọc Tuấn Anh, Đoàn Hữu Quang Vinh và các bạn Nguyễn Huy Hoàng, Phan Anh Đức đã giúp đỡ, đóng góp ý kiến cho chúng tôi trong quá trình cài đặt, thử nghiệm chư ơng trình. Cuối cùng, chúng con cảm ơn Ba, Mẹ và những người thân đã khích lệ, động viên chúng con trong thời gian học tập, nghiên cứu để có được thành quả như ngày nay. Tháng 7 năm 2004 Sinh viên Lê Thuý Ngọc – Đỗ Mỹ Nhung Lê Thuý Ngọc - 0012745 1 Đỗ Mỹ Nhung - 0012624
  3. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN Ngày tháng năm 2004 Ký tên Lê Thuý Ngọc - 0012745 2 Đỗ Mỹ Nhung - 0012624
  4. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN Ngày tháng năm 2004 Ký tên Lê Thuý Ngọc - 0012745 3 Đỗ Mỹ Nhung - 0012624
  5. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt MỤC LỤC Phần 1 : TÌM HIỂU VẤN ĐỀ 2 Chương 1: TỔNG QUAN VỀ HỆ THỐNG SEARCH ENGINE 2 1. Các bộ phận cấu thành hệ thống search engine 2 1.1 Bộ thu thập thông tin – Robot 2 1.2 Bộ lập chỉ mục – Index 2 1.3 Bộ tìm kiếm thông tin – Search Engine 3 2. Nguyên lý hoạt động 3 Chương 2: BỘ THU THẬP THÔNG TIN – ROBOT 5 1. Ứng dụng của Robot 5 1.1 Phân tích, thống kê – Statistical Analysis 5 1.2 Duy trì siêu liên kế - Maintenance 5 1.3 Ánh xạ địa chỉ web - Mirroring 5 1.4 Phát hiện tài nguyên – Resource Discovery 6 1.5 Kết hợp các công dụng trên- Combined uses 6 2. Robot chỉ mục – Robot Indexing 6 3. Các chiến thuật thu thập dữ liệu [II.1] 8 3.1 Chiến thuật tìm kiếm theo chiều sâu 8 3.2 Chiến thuật tìm kiếm theo chiều rộng 9 3.3 Chiến thuật tìm kiếm theo ngẫu nhiên 9 4. Những vấn đề cần lưu ý của web robot 10 4.1 Chi phí và hiểm hoạ 10 4.1.1 Qúa tải mạng và server – Network resource and server load 10 4.1.2 Sự cập nhật quá mức- Updating overhead 11 4.1.3 Những tình huống không mong đợi – Bad implementations 12 4.2 Tiêu chuẩn loại trừ robot 12 4.2.1 File robot.txt 13 4.2.2 Thẻ META dành cho robot – Robot META tag 14 4.2.3 Nhược điểm của file robot.txt 15 Chương 3: BỘ LẬP CHỈ MỤC – INDEX 18 1. Khái quát về hệ thống lập chỉ mục 18 2. Tổng quan về phương pháp lập chỉ mục ([I.1], [I.2], [II.1]) 21 2.1 Xác định mục từ quan trọng cần lập chỉ mục ([I.1]) 21 2.2 Một số hàm tính trọng số mục từ. ([I.1]) 23 2.2.1 Nghịch đảo trọng số tần số tài liệu ( The Inverse Document Frequency Weight) 24 Lê Thuý Ngọc - 0012745 4 Đỗ Mỹ Nhung - 0012624
  6. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt 2.2.2 Độ nhiễu tín hiệu (Signal Noise): 25 2.2.3 Giá trị độ phân biệt của mục từ : 25 2.2.4 Kết hợp tần số xuất hiện mục từ và nghịch đảo tần số tài liệu 26 2.3 Lập chỉ mục tự động cho tài liệu 28 3. Lập chỉ mục cho tài liệu tiếng Việt ([III.1], [II.1], [II.2], [II.3], [II.4], [IV.11], [IV.12]) 29 3.1 Khó khăn cho việc lập chỉ mục tiếng Việt 29 3.2 Đặc điểm về từ trong tiếng Việt và việc tách từ 31 3.2.1 . Đặc điểm về từ trong tiếng Việt: 31 3.2.2 Tách từ 32 3.3 Giải quyết các vấn đề hiển thị của tiếng Việt (vấn đề chính tả) 34 3.3.1 Vấn đề bảng mã 34 3.3.2 Vấn đề dấu thanh 35 3.3.3 Vấn đề dấu tổ hợp nguyên âm 36 3.4 Giải quyết các vấn đề về từ của tiếng Việt 37 3.4.1 Luật xác định các từ láy 37 3.4.2 Luật xác định các liên từ 37 3.5 Xây dựng từ điển tiếng Việt 37 Chương 4: BỘ TÌM KIẾM THÔNG TIN – SEARCH ENGINE 40 1. Vì sao ta cần một công cụ tìm kiếm (SE) ? 40 2. Các phương thức tìm kiếm 40 2.1 Tìm theo từ khoá – Keyword searching 40 2.2 Những khó khăn khi tìm theo từ khoá 41 2.3 Tìm theo ngữ nghĩa – Concept-based searching 41 3. Các chiến lược tìm kiếm 42 3.1 Tìm thông tin với các thư mục chủ đề 42 3.2 Tìm thông tin với các công cụ tìm kiếm 43 3.3 Tối ưu câu truy vấn 43 3.4 Truy vấn bằng ví dụ 44 Chương 5: MỘT SỐ SEARCH ENGINE THÔNG DỤNG TRÊN THẾ GIỚI VÀ VIỆT NAM 45 1.1 Thư mục của Yahoo, Google 54 1.2 Alltheweb 55 1.3 AltaVista 55 1.4 Lycos 55 1.5 HotBot 55 2. Một số search engine thông dụng ở Việt Nam 56 2.1 Netnam [IV.12] 56 2.1.1 Phương pháp Netnam SE lập chỉ mục dữ liệu 58 Lê Thuý Ngọc - 0012745 5 Đỗ Mỹ Nhung - 0012624
  7. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt 2.1.2 Cú pháp tìm kiếm 59 2.1.3 Sử dụng từ khoá để lọc các tìm kiếm 61 2.2 Vinaseek ([IV.11]) 65 Phần 2 : THIẾT KẾ VÀ CÀI ĐẶT 67 Chương 6: THIẾT KẾ DỮ LIỆU 67 1. Cơ sở dữ liệu trong SQL 67 2. Hệ thống tập tin 71 Chương 7: THU THẬP THÔNG TIN 72 1. Cấu trúc dữ liệu 72 1.1 Cấu trúc UrlInfo 73 1.2 Cấu trúc StartUrlInfo 74 1.3 Cấu trúc FileRetrieval 75 1.4 Cấu trúc ProjectInfo 75 2. Xử lý của web robot 78 3. Giải quyết các vấn đề của web robot 83 3.1 Tránh sự lặp lại 83 3.2 Tránh làm qúa tải server 83 3.3 Tránh truy xuất đến các dạng tài nguyên không thích hợp 83 3.4 Tránh các lỗ đen(black holes) 84 3.5 Tránh những nơi cấm robot 84 4. Các thuật toán phân tích cấu trúc file HTML 84 4.1 Thuật toán lấy liên kết 84 4.1.1 Thuật toán ứng dụng cũ đã cài đặt 85 4.1.2 Chọn lựa của ứng dụng mới 89 4.2 Thuật toán lấy tiêu đề 89 4.3 Thuật toán lấy nội dung 90 5. Duy trì thông tin cho CSDL 91 6. Resume project 91 6.1 Nguyên tắc resume của ứng dụng cũ 1 92 6.2 Cải tiến của ứng dụng mới 94 Chương 8: LẬP CHỈ MỤC 97 1. Tính trọng số của từ: 97 2. Tập tin nghịch đảo : 98 3. Từ điển chỉ mục 105 4. Quá trình stemming 110 Chương 9: TÌM KIẾM THÔNG TIN 113 Lê Thuý Ngọc - 0012745 6 Đỗ Mỹ Nhung - 0012624
  8. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt Chương 10: CÁC MODULE ,PACKAGE, LỚP CHÍNH CỦA CHƯƠNG TRÌNH 115 1. Các module, package của chương trình 115 2. Các lớp đối tượng chính trong từng module 116 2.1 Module DBController 116 2.2 Module ProcessDoc 117 2.3 Module Query 118 2.4 Module SE 119 2.5 Module Webcopy 119 2.6 Module WebcopyGUI 120 Phần 3 : KẾT QUẢ, ĐÁNH GIÁ VÀ HƯỚNG PHÁT TRIỂN 122 1. Kết quả thử nghiệm 122 2. Hoạt động của chương trình 124 2.1 Giao diện quản trị 124 2.1.1 Giao diện chính của quản trị 124 2.1.2 Tạo mới project 125 2.1.3 Tạo mới một StartUrl : 128 2.1.4 Xem từ điển chỉ mục 131 2.1.5 Quản lý mục từ 132 2.2 Giao diện tìm kiếm 134 3. Đánh giá 136 3.1 Ưu điểm 136 3.2 Khuyết điểm 137 4. Hướng phát triển 137 4.1 Đối với từng module : 137 4.2 Đối với toàn luận văn: 138 DANH SÁCH CÁC BẢNG 139 DANH SÁCH CÁC HÌNH VẼ 140 TÀI LIỆU THAM KHẢO 141 I. Sách, ebook: 141 II. Luận văn, luận án 141 III. Bài báo 142 IV. Website 142 Lê Thuý Ngọc - 0012745 7 Đỗ Mỹ Nhung - 0012624
  9. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt MỞ ĐẦU Trong thời đại ngày nay, thông tin là nhu cầu thiết yếu đối với mọi người trên mọi lĩnh vực. Mỗi phút trôi qua hàng triệu triệu trang web được đẩy lên nhằm làm giàu nguồn tài nguyên vô tận này. Tuy nhiên tồn tại một nghịch lý là dù được ví như thư viện toàn cầu, internet vẫn không thoả mãn nhu cầu thông tin của con người. Xung quanh vấn đề này có nhiều nguyên nhân nhưng quan trọng nhất là sự thông hiểu giữa con người và công cụ tìm kiếm trên mạng – search engine – chưa đạt đến mức có thể giao tiếp tốt với nhau. Hơn nữa, mỗi search engine sẽ mang đặc thù của ngôn ngữ mà nó hiển thị như search engine Tiếng Việt phải giải quyết những vấn đề đặc trưng của Tiếng Việt, cụ thể là vấn đề bảng mã, ngữ pháp trong Tiếng Việt. Nếu ta hiểu cách thức search engine 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 sẽ 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. Đây là mục tiêu chính của luận văn. Lê Thuý Ngọc - 0012745 1 Đỗ Mỹ Nhung - 0012624
  10. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt Phần 1 : TÌM HIỂU VẤN ĐỀ Chương 1: TỔNG QUAN VỀ HỆ THỐNG SEARCH ENGINE 1. Các bộ phận cấu thành hệ thống search engine 1.1 Bộ thu thập thông tin – Robot 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 & một cách đệ quy nó nhận về tất cả tài liệu có liên kết với tài liệu này. Robot được biết đến dưới nhiều tên gọi khác nhau : s pider, 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 site 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. 1.2 Bộ lập chỉ mục – Index 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. Lê Thuý Ngọc - 0012745 2 Đỗ Mỹ Nhung - 0012624
  11. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt 1.3 Bộ tìm kiếm thông tin – Search Engine Search engine là cụm từ dùng chỉ toàn bộ hệ thống bao gồm bộ thu thập thông tin, bộ lập chỉ mục & bộ tìm kiếm thông tin. Các bộ này hoạt động liên tục từ lúc khởi động hệ thống, chúng phụ thuộc lẫn nhau về mặt dữ liệu nhưng độc lập với nhau về mặt hoạt động. Search engine tương tác với user thông qua giao diện web, có nhiệm vụ tiếp nhận & trả về những tài liệu thoả yêu cầu của user. Nói nôm na, tìm kiếm từ 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. 2. 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 Lê Thuý Ngọc - 0012745 3 Đỗ Mỹ Nhung - 0012624
  12. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt 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ê Thuý Ngọc - 0012745 4 Đỗ Mỹ Nhung - 0012624
  13. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt Chương 2: BỘ THU THẬP THÔNG TIN – ROBOT 1. Ứng dụng của Robot Robot thường được sử dụng cho những mục đích sau : 1.1 Phân tích, thống kê – Statistical Analysis Robot đầu tiên được dùng để đếm số lượng web server, số tài liệu trung bình của một server, tỉ lệ các dạng file khác nhau, kích thước trung bình của một trang web, độ kết dính, 1.2 Duy trì siêu liên kế - Maintenance Một trong những khó khăn của việc duy trì một siêu liên kết là nó liên kết với những trang bị hỏng (dead links) khi những trang này bị thay đổi hoặc thậm chí bị xóa. Thật không may vẫn chưa có cơ chế nào cảnh báo các bộ duy trì về sự thay đổi này. Trên thực tế khi các tác giả nhận ra tài liệu của mình chứa những liên kết hỏng, họ sẽ thông báo cho nhau, hoặc thỉnh thoảng độc giả thông báo cho họ bằng email. Một số robot, chẳng hạn MOMspider có thể trợ giúp tác giả phát hiện các liên kết hỏng cũng như duy trì các cấu trúc siêu liên kết cùng nội dung của một trang web. Chức năng này lặp lại liên tục mỗi kh i một tài liệu được cập nhật, nhờ đó mọi vấn đề xảy ra sẽ được giải quyết nhanh chóng. 1.3 Ánh xạ địa chỉ web - Mirroring Mirroring là một kỹ thuật phổ biến trong việc duy trì các kho dữ liệu của FPT. Một ánh xạ (mirror) sẽ sao chép toàn bộ cấu trúc cây thư mục và thường xuyên cập Lê Thuý Ngọc - 0012745 5 Đỗ Mỹ Nhung - 0012624
  14. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt nhật những file bị thay đổi. Điều này cho phép nhiều người cùng truy xuất một nguồn dữ liệu, giảm số liên kết bị thất bại, nhanh hơn và ít chi phí hơn so với truy cập trực tiếp vào site thực sự chứa các dữ liệu này. 1.4 Phát hiện tài nguyên – Resource Discovery Có lẽ ứng dụng thú vị nhất của robot là dùng nó để phát hiện tài nguyên. Con người không thể kiểm soát nổi một khối lượng thông tin khổng lồ trong môi trường mạng. Robot sẽ giúp thu thập tài liệu, tạo và duy trì cơ sở dữ liệu, phá t hiện và xoá bỏ các liên kết hỏng nếu có, kết hợp với công cụ tìm kiếm cung cấp thông tin cần thiết cho con người. 1.5 Kết hợp các công dụng trên- Combined uses Một robot có thể đảm nhận nhiều chức năng. Ví dụ RBSE Spider [4] vừa thống kê số lượng tài liệu t hu được vừa tạo cơ sở dữ liệu. Tuy nhiên những ứng dụng như thế còn khá ít ỏi. 2. Robot chỉ mục – Robot Indexing 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 : Một là : 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ó. Hai là : Ai sẽ cung cấp địa chỉ của các site này cho robot ? Lê Thuý Ngọc - 0012745 6 Đỗ Mỹ Nhung - 0012624
  15. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt 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. Ba là : 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 :  Ở góc cao của tài liệu.  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 k hông còn giữ được giá trị ban đầu của chúng nữa. Lê Thuý Ngọc - 0012745 7 Đỗ Mỹ Nhung - 0012624
  16. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt 3. Các chiến thuật thu thập dữ liệu [II.1] 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. 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. 3.1 Chiến thuật tìm kiếm theo chiều sâu Từ một danh sách chứa các liên kết cần duyệt, thực hiện các bước sau : (1) Cho danh sách = {trang đầu tiên} (2) Lấy trang đầu tiên trong danh sách. Nếu có qua (3) Nếu không qua (5) (3) Trang này đã xét tới chưa ? Nếu rồi, quay lại (2) Nếu chưa, qua (4) (4) Đánh dấu đã tới rồi. Phân tích và tìm xem liên kết có trong trang đó không? (4a) Nếu có, thêm liên kết này vào đầu danh sách. Quay lại (4) (4b) Nếu không, quay lại (2). (5) Kết thúc. Lê Thuý Ngọc - 0012745 8 Đỗ Mỹ Nhung - 0012624
  17. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt 3.2 Chiến thuật tìm kiếm theo chiều rộng Từ một danh sách chứa các liên kết cần duyệt, thực hiện các bước sau : (1) Cho danh sách = {trang đầu tiên} (2) Lấy trang đầu tiên trong danh sách. Nếu có qua (3) Nếu không qua (5) (3) Trang này đã xét tới chưa ? Nếu rồi, quay lại (2) Nếu chưa, qua (4) (4) Đánh dấu đã tới rồi. Phân tích và tìm xem liên kết có trong trang đó không? (4a) Nếu có, thêm liên kết này vào cuối danh sách. Quay lại (4) (4b) Nếu không, quay lại (2). (5) Kết thúc. 3.3 Chiến thuật tìm kiếm theo ngẫu nhiên Từ một danh sách chứa các liên kết cần duyệt, thực hiện các bước sau : (1) Cho danh sách = {trang đầu tiên} (2) Lấy ngẫu nhiên một trang trong danh sách. Nếu có qua (3) Nếu không qua (5) (3) Trang này đã xét tới chưa ? Lê Thuý Ngọc - 0012745 9 Đỗ Mỹ Nhung - 0012624
  18. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt Nếu rồi, quay lại (2) Nếu chưa, qua (4) (4) Đánh dấu đã tới rồi. Phân tích và tìm xem liên kết có trong trang đó không? (4a) Nếu có, thêm liên kết này vào cuối danh sách. Quay lại (4) (4b) Nếu không, quay lại (2). (5) Kết thúc. 4. Những vấn đề cần lưu ý của web robot 4.1 Chi phí và hiểm hoạ Việc sử dụng các Robot tốn khá nhiều chi phí, đặc biệt là khi chúng được điều khiển từ xa trên internet. Phần n ày chúng ta sẽ cùng thảo luận về những hiểm hoạ do robot gây ra. 4.1.1 Qúa tải mạng và server – Network resource and server load Sau một khoảng thời gian dài, thường là một tháng, robot sẽ bắt đầu hoạt động một cách liên tục. Để tăng tốc nhiều robot được phóng r a đồng thời do đó cần có băng thông lớn. Tài nguyên mạng bị khai thác quá mức khi robot yêu cầu một lượng lớn thông tin trong khoảng thời gian quá ngắn (rapid fire). Kết quả là thiếu băng thông cho những ứng dụng khác. Server vừa phải phục vụ yêu cầu của robot vừa cung cấp dịch vụ cho user, do đó yêu cầu của robot tăng lên bao nhiêu thì dịch vụ sẽ giảm xuống bấy nhiêu. Tác giả của một con robot đã thử nghiệm bằng cách cho thi hành 20 lượt truy cập đồng thời vào server của anh ta. Những lúc robot thu thập thông tin, server bị chậm Lê Thuý Ngọc - 0012745 10 Đỗ Mỹ Nhung - 0012624
  19. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt lại. Trong vòng một tuần robot đã viếng thăm site này với một yêu cầu kinh khủng. Chỉ sau 170 lượt truy xuất liên tục, thử nghiệm thất bại do server bị quá tải. Rapid fire thực sự là thảm hoạ. Hiệu quả truyền tải thông tin dạng này bằng giao thức web hay HTTP sụt giảm thấy rõ. Những giao thức mới đang được xem xét nhằm cứu vãn tình thế. 4.1.2 Sự cập nhật quá mức- Updating overhead Người ta cho rằng các cơ sở dữ liệu do web robot tạo ra có thể được cập nhật tự động nhưng cho đến thời điể m này vẫn chưa có cơ chế kiểm soát sự thay đổi trên web một cách hiệu quả. Cập nhật thông tin rất quan trọng nhưng qúa thường xuyên là điều không cần thiết. Xuất phát từ thực tế đó HTTP đưa ra kỹ thuật ‘if – Modified – Since’ giúp các user – agent xác định được thời điểm tài liệu thay đổi. Robot phát hiện điều này chỉ khi nó lưu lại các thông tin cũ nhưng sẽ tốn nhiều bộ nhớ & cần dữ liệu phức tạp. Một trong những đặc tính phổ biến của robot là khả năng tiếp nhận các từ cần tìm trong khi vẫn thu thập dữ liệu. Tuy nhiên một số người cho rằng đặc tính này không đáng hoan nghênh bởi hai lý do :  Đầu tiên, các tác vụ tìm kiếm của người sử dụng cuối (end - user) góp phần đẩy server vào chỗ quá tải.  Thứ hai, không có cơ sở đảm bảo có mối quan hệ giữa các từ cần t ìm, đúng chính tả và tối ưu đối với cơ sở dữ liệu. Ví dụ, nếu bộ tìm kiếm không hỗ trợ các toán tử boolean, một user cần dữ liệu về xe máy muốn có được thông tin đúng thay vì nhập vào cụm từ ‘Ford and garage’ phải nhập vào từ ‘car’. Nhưng người đó không hề ý thức được điều này. Lê Thuý Ngọc - 0012745 11 Đỗ Mỹ Nhung - 0012624
  20. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt Một khía cạnh nguy hiểm nữa bắt nguồn từ sự định hướng sai lầm của end – user. Một số người sử dụng công cụ của mình rất tốt như dự đoán được lượng tài liệu lớn nhất có thể có, biết chính xác nơi cần tìm dữ liệu, giới hạn thời g ian sử dụng robot, trong khi đó một số khác lại lạm dụng khả năng của robot một cách vô tình hoặc cố ý. Vì vậy các tác giả viết robot đề nghị chỉ nên phân phát sản phẩm của mình cho những end-user ‘hiểu‘ được web robot và những khó khăn trong môi trường mạ ng. 4.1.3 Những tình huống không mong đợi – Bad implementations Thay vì kiểm tra trên máy cục bộ trước, một số tác giả lần đầu tiên viết robot cho thử ngay trên các server thực sự, điều này làm đau đầu không ít nhà quản trị web (web master). Truy xuất trùng lặp có thể xảy ra khi robot không lưu lại dấu vết những nơi nó đã đi qua hoặc nó không nhận diện được các URL mặc dù khác nhau về tên nhưng lại cùng dẫn đến một địa chỉ, ví dụ địa chỉ DSN & IP. Đôi khi, robot lãng phí thời gian và tài nguyên chỉ để thu về nh ững tài liệu mà sau đó phải vứt đi. Ví dụ hệ thống chỉ quan tâm đến file văn bản (text file) nhưng robot lại nhận cả những loại file khác như file hình ảnh, file thực thi, Trong môi trường mạng có những vùng gần như vô tận. Ví dụ, cứ mỗi lần phân tích một trang robot nhận về cùng một URL nhưng xa hơn một cấp, ‘/cgi -bin/pit/’, và tiếp tục ‘/cgi-bin/pit/a/’, ‘/cgi-bin/pit/a/a’, . . Sự lặp lại không có điểm dừng này được gọi là các lỗ đen (black holes) 4.2 Tiêu chuẩn loại trừ robot Trong quá trình xử lý robot không thể tự quyết định tài liệu nào được lập chỉ mục, tài liệu nào không do đó nó lấy tất cả những gì có thể. Thậm chí dù xác định được Lê Thuý Ngọc - 0012745 12 Đỗ Mỹ Nhung - 0012624
  21. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt tài liệu vô ích thì nó cũng đã bỏ ra một chi phí đáng kể cho hoạt động thu thập. Tiêu chuẩn loại trừ robot ra đời. Các chuẩn này chẳng những chỉ ra URL nào cần tránh mà còn cảnh báo robot về các lỗ đen. 4.2.1 File robot.txt Robot.txt là một file cấu trúc được đặt tại thư mục gốc của server, gồm 2 trường User-agent và Disallow.  User-agent : cho biết robot nào sẽ bị kiểm soát.  Disallow : cho biết robot có được phép kết nối vào URL này hay không.  Xét các ví dụ sau : Ví dụ Ý nghĩa # / robots.txt file for Ký tự # bắt đầu một chú thích User-agent: webcrawler Robot có tên là webcrawler có thể đi đến bất cứ trang nào ủa site Disallow: c User-agent: lycra Robot có tên là lycra bị cấm trên tất cả các trang của site Disallow: / Lê Thuý Ngọc - 0012745 13 Đỗ Mỹ Nhung - 0012624
  22. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt User-agent: * Mọi robot đều không được truy xuất vào 2 thư mục tmp và Disallow: /tmp logs Disallow: /logs Bảng 2.1 :Ví dụ về chuẩn loại trừ robot dùng file robot.txt 4.2.2 Thẻ META dành cho robot – Robot META tag META tag là sự mở rộng của chuẩn loại trừ robot, hỗ trợ cho tác giả của những trang web không có quyền admin. Vị trí Nằm trong phần HEAD của file HTML Cú pháp Tên trường Ý nghĩa Meta Thẻ báo hiệu bắt đầu Name Tên robot sẽ bị kiểm soát Content Cờ định hướng cho robot, các cờ này có thể kết hợp với nhau & được phân cách bằng dấu phẩy. Bảng 2.2 : Bảng thông tin về META tag trong chuẩn loại trừ robot Lê Thuý Ngọc - 0012745 14 Đỗ Mỹ Nhung - 0012624
  23. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt Các cờ của thuộc tính Content Ý nghĩa [NO]INDEX Robot không nên lập chỉ mục cho trang này. [NO]FOLLOW Robot không nên lấy các liên kết ở trang này ALL = INDEX, FOLLOW NONE= NOINDEX, NOFOLLOW Bảng 2.3 : Bảng giá trị các cờ của thuộc tính Content trong META tag 4.2.3 Nhược điểm của file robot.txt Người ta cho rằng việc liệt kê các trang hoặc các thư mục trong file robot.txt sẽ là nguyên nhân thu hút sự chú ý từ các ‘vị khách không mời‘. Thực ra chuẩn loại trừ robot chỉ là dấu hiệu cảnh báo, không là biện pháp cấm robot cho nên việc tuân theo hay không hoàn toàn là vấn đề tự nguyện. Tuy nhiên ta vẫn có cách khắc phục : Một là :  Tạo một thư mục chứa tất cả các file quan trọng.  Trường Disallow chỉ liệt kê tên thư mục vừa tạo.  Cấu hình server sao cho các trang không chứa đường dẫn đến thư mục này. Đáng buồn trên thực tế cách này không đạt được kết quả mong đợi do một trong các nguyên nhân sau : Lê Thuý Ngọc - 0012745 15 Đỗ Mỹ Nhung - 0012624
  24. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt  Các server có robot không bị cấm có thể dẫn đường các robot bị cấm khác đến những file này.  Các file quan trọng có thể nằm trong log file (file được tự do truy xuất)  Khi cấu hình lại server, admin có thể ‘quên‘ các thư mục này phải cấm robot! Hai là: chứng thực (athorization). Đây là biện pháp hữu hiệu, được sử dụng trong nhiều lĩnh vực, đặc biệt trong những môi trường mà sự an toàn dữ liệu trở nên rất cần thiết. Tóm tắt : Có thể nói web robot là con dao 2 lưỡi, sử dụng đúng sẽ giải quyết được nhiều vấn đề, sử dụng sai sẽ để lại những hậu quả khó đoán. Sau đây là tóm tắt cho những vấn đề cần lưu ý của web robot  Tránh lãng phí tài nguyên  Chỉ tải về những tài liệu cần thiết.  Nếu hệ thống chỉ quan tâm đến các file text (.html, .htm, .xml, ), web robot nên bỏ qua các liên kết dẫn đến những file thực thi (.exe, ), file ảnh (.gif, .bmp, ).  Bỏ qua các trường dữ liệu hệ thống không dùng đến.  Đừng lấy về các trang giống nhau nhiều hơn một lần.  Tránh cập nhật lại các site cũ quá thường xuyên bằng cách : Lê Thuý Ngọc - 0012745 16 Đỗ Mỹ Nhung - 0012624
  25. Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt  Ghi nhớ những địa chỉ web robot đã duyệt qua.  Dựa vào trường LastModified, trường head. Nếu các trường này khác với dữ liệu ta đã có thì đó là những thông tin cần ghi nhận.  Không nên duyệt hết một site, chỉ cần duyệt đến một độ sâu (deep link) cần thiết.  Tránh làm quá tải server  Duy trì một khoảng thời gian đợi giữa các lần truy xuất liên tiếp.  Kết nối với server vào những thời điểm thích hợp. Tham khảo ý kiến của admin để biết thông tin này.  Kiểm tra web robot trên máy cục bộ, sửa lỗi trươc khi chạy trên server thực sự.  Tuân theo các luật loại trừ robot. Lê Thuý Ngọc - 0012745 17 Đỗ Mỹ Nhung - 0012624
  26. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Chương 3: BỘ LẬP CHỈ MỤC – INDEX 1. Khái quát về hệ thống lập chỉ mục Các trang Web sau khi thu thập về sẽ đượ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) để lưu trữ trong cơ sở dữ liệu nhằm phục vụ cho nhu cầu tìm kiếm sau này. Mô hình xử lý tổng quát của một hệ thống được trình bày như sau : Lê Thuý Ngọc - 0012745 18 Đỗ Mỹ Nhung - 0012624
  27. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Danh sách Lọc các thông tin thừa, chuyển tài liệu về dạng văn bản các trang Web cần lập chỉ mục Tách văn bản thành các từ TỪ ĐIỂN Danh sách Loại bỏ stop-word các từ stop- word Tính trọng số và loại bỏ những từ có trọng số thấp ại bỏ hậu tố Lo Danh sách các hậu tố CSDL chỉ Lập chỉ mục mục thông tin Hình 3.1 Lưu đồ xử lý cho hệ thống lập chỉ mục Lê Thuý Ngọc - 0012745 19 Đỗ Mỹ Nhung - 0012624
  28. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Lập chỉ mục là quá trình phân tích và xác định các từ , cụm từ thích hợp cốt lõi có khả năng đại diện cho nội dung của tài liệu . Như vậy, vấn đề đặt ra là phải rút trích ra những thông tin chính, có khả năng đại diện cho nội dung của tài liệu. Thông tin này phải “vừa đủ”, nghĩa là không thiếu để trả ra kết quả đầy đủ so với nhu cầu tìm kiếm, nhưng cũng phải không dư để giảm chi phí lưu trữ và chi phí tìm kiếm và để loại bỏ kết quả dư thừa không phù hợp. Việc rút trích này chính là việc lập chỉ mục trên tài liệu. Trước đây , quá trình này thường được các chuyên viên đã qua đào tạo thực hiện một cách “thủ công “ nên có độ chính xác cao. Nhưng trong môi trường hiện đại ngày nay, với lượng thông tin khổng lồ thì việc lập chỉ mục bằng tay không còn phù hợp, phương pháp lập chỉ mục tự động mang lại hiệu quả cao h ơn. Một thủ tục lập chỉ mục tự động cơ bản cho các tài liệu tiếng Anh có thể được xử lý như sau: [III.1] 1. Step of tokenization: Tách văn bản ra thành các chuỗi nhờ vào khoảng trắng, mỗi chuỗi xem như là một từ. 2. Step of removal of stop words: bỏ những từ thường xuyên xuất hiện trong hầu hết các tài liệu nhưng lại không quan trọn g trong các tài liệu như tính từ, đại từ. 3. Step of stemming: loại bỏ các hậu tố (suffixes) để đưa về các từ gốc Các từ thu được sẽ được lập chỉ mục. Tuy nhiên hai bước đầu cũng cần cho quá trình lập chỉ mục cho các tài liệu tiếng Việt, bước thứ ba không cần vì tiếng Việt thuộc dòng ngôn ngữ đơn thể. Lê Thuý Ngọc - 0012745 20 Đỗ Mỹ Nhung - 0012624
  29. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt 2. Tổng quan về phương pháp lập chỉ mục ([I.1], [I.2], [II.1]) Phương pháp lập chỉ mục gồm 2 phần chính yếu sau : đầu tiên là xác định cá c mục từ , khái niệm mà có khả năng đại diện cho văn bản sẽ được lưu trữ (bao gồm cả việc tách từ, loại bỏ stop -word, xử lý hậu tố ) thứ hai là xác định trọng số cho từng mục từ , trọng số này là giá trị phản ánh tầm quan trọng của mục từ đó trong văn bản 2.1 Xác định mục từ quan trọng cần lập chỉ mục ([I.1]) Mục từ hay còn gọi là mục từ chỉ mục, là đơn vị cơ sở cho quá trình lập chỉ mục. Mục từ có thể là từ đơn, từ phức hay một tổ hợp từ có nghĩa trong một ngữ cảnh cụ thể. Ta xác định mục từ của 1 văn bản dựa vào chính nội dung của văn bản đó , hoặc dựa vào tiêu đề hoặc tóm tắt nội dung của văn bản đó. Hầu hết việc lập chỉ mục tự động bắt đầu với việc khảo sát tần số xuất hiện của từng loại từ riêng rẽ trong văn bản. Nếu tất cả các từ xuất hiên trong tập tài liêu với những tần số băng nhau, thì không thể phân biệt các mục từ theo tiêu chuẩn định lượng. Tuy nhiên, trong văn bản ngôn ngữ tự nhiên, tần số xuất hiện của từ có tính thất thường, Do đó những mục từ có thể được phân biệt bởi tần số xuất hiên của chúng. Đặc trưng xuất hiện của từ vựng có thể được định bởi hằng số “thứ hạng - tần số” (Rank_Frequency ) theo luật của Zipf : Tân số xuất hiên * thứ hạng = Hằng số. Lê Thuý Ngọc - 0012745 21 Đỗ Mỹ Nhung - 0012624
  30. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Biểu thức luật Zipf có thể dẫn ra những hệ số ý nghĩa của từ dựa vào những đặc trưng của tân số xuất hiện của mục từ riêng lẽ trong những văn bản tài liệu. Một đề xuất dựa theo sự xem xét chung sau: 1. Cho một tập hợp n tài liệu, trong mỗi tài liệu tính toán tần số xuất hiện của các mục từ trong tài liệu đó. Fik (Frequency): tần số xuất hiện của mục từ k trong tài liệu i 2. Xác định tổng số tập tấn số xuất hiện TF k (Total Frequency) cho mỗi từ bằng cách cộng những tần số của mỗi mục từ duy nhất trên tất cả n tài liệu. n TFk = ∑ Fik. i=1 3. Sắp xếp những thứ tự giảm theo tập tần số xuất hiện của chúng. Quyết định giá trị ngữơng cao và loại bỏ tất cả những từ có tập tần số xuất hiện cao trên ngững nay. Những từ bị loại bỏ là những từ xuất hiện phổ biến ở hầu hết các tài liệu. Đó chính là các stop -word. 4. Tương tư, loại trừ những từ được xem là có tần số xuất hiện thấp. Việc xoá những mục từ như vậy hiếm khi xảy ra trong tập hợp mà sự mặt của chúng không làm ảnh hưởng lớn đến việc thực hiện truy vấn. 5. Những từ xuất hiện trung bình còn lại bây giờ được dùng cho việc ấn định tới những tài liệu như những mục từ chỉ mục. Chú ý: một khái niệm xuất hiện ít nhất hai lần trong cùng một đoạn thì được xem là một khái niệm chính. Một khái niệm xuất hiện trong hai đoạn văn liên tiếp cũng được xem là một khái niệm chính mặc dù nó chỉ xuất hiện duy nhất một lần trong đoạn Lê Thuý Ngọc - 0012745 22 Đỗ Mỹ Nhung - 0012624
  31. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt đang xét. Tất cả những chú giải về những khái niệm chính được liệt kê theo một tiêu chuẩn nhất định nào đó. Thực tế cho thấy rằng ý tưởng trên khá cứng nhắc , vì nếu lọai bỏ tất cả những từ có tần số xuất hiện cao sẽ làm giảm giá trị recall (độ tương tự), tức giảm hiệu quả trong việc trả về số lượng lớn của những mục tin thích đáng. Ngược lại, sự loại bỏ những mục từ có tần số xuất hiện thấp có thể làm giảm giá trị của độ chính xác . Một vấn đề khác là sự cần thiết để chọn những ngưỡng thích hợ p theo thứ tự để phân biệt những mục từ hữu ích có tần số xuất hiện trung bình trong phần còn lại 2.2 Một số hàm tính trọng số mục từ. ([I.1]) Trọng số của mục từ: là sự tần xuất xuất hiện của mục từ trong toàn bộ tài liệu. Phương pháp thường được sử dụng để đánh giá trọng số của từ là dựa vào thống kê, với ý tưởng là những từ thường xuyên xuất hiện trong tất cảcác tài liệu thì “ít có ý nghĩa hơn” là những từ tập trung trong một số tài liệu. Ta xét các khái niệm sau:  Gọi T={t1,t2, ,tn} là không gian chỉ mục, với ti là các mục từ.  Một tài liệu D được lập chỉ mục dựa trên tập T sẽ được biểu diễn dưới dạng: T(D)={w1,w2, wn} với wi là trọng số của ti trong tập tài liệu D. Nếu wi=0 nghĩa là ti không xuất hiện trong D hoặc mục từ ti ít quan trọng trong tài liệu D ta không quan tâm tới. T(D) được gọi là vector chỉ mục của D, nó được xem như biểu diễn cho nội dung của tài liệu D và được lưu lại trong cơ sở dữ liệu của hệ thống tìm kiếm thông tin để phục vụ cho nhu cầu tìm kiếm. Lê Thuý Ngọc - 0012745 23 Đỗ Mỹ Nhung - 0012624
  32. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Mặc dù T(D ) biểu diễn nội dung của tài liệu D nhưng không phải bất cứ từ nào có trong D đều xuất hiện trong T(D) mà chỉ có những từ có trọng lượng (có ý nghĩa quan trọng trong tài liệu D) mới được lập chỉ mục cho D. Sau đây ta xét một số hàm tính trọng số của mục từ 2.2.1 Nghịch đảo trọng số tần số tài liệu (The Inverse Document Frequency Weight) wk : là trọng lượng của mục từ k. nDock : tổng số tài liệu mà mục từ k xuất hiện. nki : số lần xuất hiện mục từ k trong tài liệu i. nk : số lần xuất hiện mục từ k trong toàn tập tài liệu. nDoc : tổng số tài liệu. idfk : giá trị nghịch đảo tần số tài liệu. (Inverse Document Frequency) Trọng lượng mục từ k : nDoc Wk idf k log 2 1 nDoc k Như vậy, trọng số của mục từ k sẽ tăng lên khi tần số xuất hiện của mục từ k trong các tài liệu i tăng lên nhưng giảm xuống khi tấn số xuất hiện của mục từ k trong tập tài liệu (nDock) tăng lên. Biểu thức tổng hợp : wk = nik* [log2 (n)-log2(nDOCk)+ 1] Lê Thuý Ngọc - 0012745 24 Đỗ Mỹ Nhung - 0012624
  33. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Hàm này gán độ quan trọng cao cho những mục từ chỉ xuất hiện trong một số ít tài liệu của một tập hợp tài liệu (đề cao độ phân biệt) 2.2.2 Độ nhiễu tín hiệu (Signal Noise): Trọng số của từ được đo lường bằng sự tập trung hay phân tán của từ. Ví dụ từ "hardware" xuất hiện 1000 lần nhưng trong 200 tài liệu ( tập trung ) thì có trọng lượng cao hơn từ "computer" cũng xuất hiện 1000 lần nhưng trong 800 tài liệu. Độ nhiễu của một mục từ k: noisek =  (nki / nk ).log2 (nki / nk ) i=1,nDoc Hàm số nghịch đảo của độ nhiễu được gọi là độ signal có thể được dùng để tính trọng lượng của mục từ k : wk =signalk = log2( nk ) - noisek 2.2.3 Giá trị độ phân biệt của mục từ : Không ai muốn kết quả của việc tìm kiếm lại trả về tập tất cả các tài liệu có trong tập hợp (nghĩa là tập chỉ mục của các tài liệu chứa nhiều từ giống nhau). Độ phân biệt của mục từ là giá trị phân biệt mức độ tương đương giữa các tài liệu. Nếu một mục từ có trong chỉ mục mà làm cho độ tương tự của các tài liệu ca o thì nó có độ phân biệt kém (nghĩa là từ này thường xuyên xuất hiện trong các tài liệu) và ngược lại. Như vây các mục từ có độ phân biệt cao nên được chọn để lập chỉ mục. Thực chất việc sử dụng độ phân biệt này cũng cho kết quả tương đương với việc sử dụ ng tần số nghịch đảo và tỉ lệ tín hiệu nhiễu. Lê Thuý Ngọc - 0012745 25 Đỗ Mỹ Nhung - 0012624
  34. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Gọi Sim(Di,Dj) là độ tương tự của cặp tài liệu Di, Dj. Độ tương tự trung bình được tính trên tất cả các cặp tài liệu: Arv_Sim =  Sim(Di,Dj) i ≠ j. Gọi Arv_Simk là độ tương tự trung bình được tính trong trường hợp mục từ k bị loại bỏ khỏi tập chỉ mục. Khi đó trọng lượng mục từ k có thể được tính theo giá trị độ phân biệt DiscValueK theo công thức: wk = DiscValueK = Arv_Simk - Arv_Sim Phép tính DiscValueK cho tất cả những mục từ k, những mục từ có thể được xếp theo thứ tự giảm của giá trị phân biệt DiscValueK. Những mục từ chỉ mục có thể thuộc một trong ba nhóm dựa theo giá trị độ phân biệt của chúng như sau:  Độ phân biệt tốt đối vơi DiscValue K dương, những mục từ có độ phân biệt cao.  Đối với DiscValue K gần bằng 0, độ phân biệt giữa các tài liệu không khác nhau khi thêm vào hay bớt đi những mục từ đó.  Độ phân yếu khi DiscValueK âm, những mục từ có độ phân biệt thấp (độ tương tự cao ). 2.2.4 Kết hợp tần số xuất hiện mục từ và nghịch đảo tần số tài liệu Phần này sẽ đề cập đến một số biến thể tần số xuất hiện của mục từ tf(Term Frequency) và sự kết hợp với idf để xác định tầm quan trọng của một mục từ. Lê Thuý Ngọc - 0012745 26 Đỗ Mỹ Nhung - 0012624
  35. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt f(t,d) : tần số xuất hiện của mục từ t trong tài liệu d N : tổng số tài liệu trong tập dữ liệu n : tổng số tài liệu có mục từ t Max[f(t,d)]: số lần xuất hiện cao nhất của mục từ t trong toàn tập tài liệu tf(Term Frequency) vẫn là tần số xuất hiện của một mục từ trong tập tài liệu, có thể được xác định bởi nhiều công thức khác nhau: tf = f(t,d) tf = f(t,d)/Max[f(t,d)] tf = log2(f(t,d)) tf = log2(f(t,d) +1) tf = ln f(t,d) +1 . idf(Inverse Document Frequency) : là tần số nghịch đảo tần số xuất hiện của các tài liệu và được tính như sau: idf = log2(N/n) idf = log2((N-n)/n) idf = log2(N/n)*2 Mỗi công thức trên đều mang một ý nghĩa riêng trong từng trường hợp cụ thể, sự kết hợp của tf và idf sẽ xác định mức độ quan trọng của mục từ cần xét. Lê Thuý Ngọc - 0012745 27 Đỗ Mỹ Nhung - 0012624
  36. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Wit = tf * idf Sự kết hợp hai tiêu chuẩn này cho biết: tầm quan trọng của một mục từ (do tf mang lại) và sự phân biệt giữa các mục từ (do idf mang lại). Một mục từ có tầm quan trọng lớn hơn thì giá trị Wit của nó phải lớn hơn. 2.3 Lập chỉ mục tự động cho tài liệu Vấn đề chính của lập chỉ mục tự động là xác định tự động mục từ chỉ mục cho các tài liệu. Trong các ngôn ngữ gốc Ấn – Âu thì tách từ có thể nói là đơn giản vì khoảng trắng là ký tự để phân biệt từ. Vấn đề cần quan tâm là xác định những từ này là từ khoá, có thể đại diện cho toàn bộ nội dung của tài liệu. Loại bỏ các từ stop-word có tần số xuất hiện cao, những từ này thường chiếm đến 40-50% trong số các từ của một văn bản. Những từ này có độ ph ân biệt kém và không thể sử dụng để xác định nội dung của tài liệu. Trong tiếng Anh, có khoảng 250 từ. Số lượng từ này không nhiều lắm nên giải pháp đơn giản nhất là lưu các từ này vào trong một tự điển, và sau đó chỉ cần thực hiện so sánh từ cần phân tích với từ điển để loại bỏ. Bước tiếp theo là nhận ra các chỉ mục tốt. Để giảm bớt dung lượng lưu trữ, các mục từ cần được biến đổi về nguyên gốc ( step of stemming đối với tiếng Anh), Phải loại bỏ đi các tiền tố, hậu tố, các biến thể số nhiều, quá khứ Giải pháp là sử dụng một danh sách các hâu tố. Trong khi loại bỏ hậu tố thì những hậu tố dài được ưu tiên loại bỏ trước, rồi sau đó mới loại bỏ những hậu tố ngắn hơn. Sau đây là một số vấn đề khi loại bỏ trong tiếng Anh: 1. Chỉ rõ chiều dài tối thiểu của một từ gốc sau khi loại bỏ hậu tố. Ví dụ: việc loại bỏ hậu tố “ability” ra khỏi “computability” hay loại bỏ “ing” ra Lê Thuý Ngọc - 0012745 28 Đỗ Mỹ Nhung - 0012624
  37. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt khỏi “singing” là hợp lý. Tuy nhiên, những hậu tố đó không cần phải loại bỏ trong các từ “ability” và “sing”. 2. Nếu nhiều hậu tố được kết hợp vào một gố c thì ta sẽ áp dụng đệ quy cho quá trình loại bỏ hậu tố vài lần hoặc lập từ điển hậu tố rồi loại bỏ những hậu tố dài hơn trước rồi đến các hậu tố ngắn sau. Ví dụ: “effectiveness” “effective” “effect”. 3. Trong tiếng Anh, từ gốc có thể bị biến đổi sau khi đã loại bỏ hậu tố. Do đó, ta cần phải có những luật nhất định để phục hồi từ gốc. Chẳng hạn loại bỏ một trong hai kí tự trùng nhau của những từ có sự xuất hiện b, d, d, l, m, n, p, r, s, t ở cuối của các từ gốc sau khi đã loại bỏ hậu tố. Ví du như “beginning” “beginn” “begin”. 4. Một số ngoại lệ phụ thuộc vào ngữ cảnh đặc biệt phải được chú ý, sử dụng các quy tắc cảm ngữ cảnh. Ví dụ: một quy tắc cho hậu tố “allic” chỉ rõ chiều dài cực tiểu của từ gốc là ba và không loại bỏ hậu tố sau “met” hoặc “ryst”, hoặc quy tắc chỉ loại bỏ hậu tố “yl” sau “n” hoặc “r”. Tóm lại, giải quyết vấn đề hậu tố không quá khó nếu chúng ta có sẵn một danh sách chứa các hậu tố, một danh sách chứa các luật thêm các hậu tố và phục hồi từ gốc sau khi thêm hậu tố. 3. Lập chỉ mục cho tài liệu tiếng Việt ([III.1], [II.1], [II.2], [II.3], [II.4], [IV.11], [IV.12]) 3.1 Khó khăn cho việc lập chỉ mục tiếng Việt Các điểm khó khăn khi thực hiện quá trình lập chỉ mục cho tài liệu tiếng Việt so với tài liệu tiếng Anh mà chúng ta phải giải quyết : Lê Thuý Ngọc - 0012745 29 Đỗ Mỹ Nhung - 0012624
  38. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt  Xác định ranh giới giữa các từ trong câu. Đối với tiếng Anh điều này quá dễ dàng vì khoảng trắng chính là ranh giới phân biệt các từ ngược lại tiếng Việt thì khoảng trắng không phải là ranh giới để xác định các từ mà chỉ là ranh giới để xác định các tiếng.  Chính tả tiếng Việt còn một số điểm chưa thống nhất như sử dụng " y" hay "i" ( ví dụ "quý" hay "quí" ), cách bỏ dấu ( "lựơng" hay "lượng" ), cách viết hoa tên riêng( "Khoa học Tự nhiên" hay "Khoa Học Tự Nhiên") đòi hỏi quá trình hiệu chỉnh chính tả cho văn bản cần lập chỉ mục và cho từ điển chỉ mục.  Tồn tại nhiều bảng mã tiếng Việ t đòi hỏi khả năng xử lý tài liệu ở các bảng mã khác nhau. Cách giải quyết là đưa tất cả về bảng mã chuẩn của hệ thống.  Sự phong phú về nghĩa của một từ (từ đa nghĩa). Một từ có thể có nhiều nghĩa khác nhau trong những ngữ cảnh khác nhau nên việc tìm kiế m khó có được kết quả với độ chính xác cao.  Từ đồng nghĩa hoặc từ gần nghĩa: có nhiều từ khác nhau nhưng lại có cùng ý nghĩa. Do đó, việc tìm kiếm theo từ khoá thường không tìm thấy các websites chứa từ đồng nghĩa hoặc gần nghĩa với từ cần tìm. Vì vậy, việc tìm kiếm cho ra kết quả không đầy đủ.  Có quá nhiều từ mà mật độ xuất hiện cao nhưng không mang ý nghĩa cụ thể nào mà chỉ là những từ nối, từ đệm hoặc chỉ mang sắc thái biểu cảm như những từ láy. Những từ này cần phải được xác định và loại bỏ ra khỏi t ập các mục từ. Nó giống như stop-word trong tiếng Anh.  Các văn bản có nội dung chính là một vấn đề cụ thể, một đề tài nghiên cứu khoa học nhưng đôi khi trọng số của các từ chuyên môn này thấp so với toàn Lê Thuý Ngọc - 0012745 30 Đỗ Mỹ Nhung - 0012624
  39. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt tập tài liệu. Vì vậy, một số thuật toán tính trọng số bỏ sót những trường hợp như vậy. Kết quả là các từ chuyên môn đó không được lập chỉ mục. Trong các vấn đề trên thì vấn đề xác định ranh giới từ trong câu là quan trọng nhất vì nó ảnh hưởng lớn đến hiệu quả của quá trình lập chỉ mục ( nếu quá trình tách từ sai có nghĩa là nội dung của câu bị phân tích sai ) và cũng là vấn đề khó khăn nhất. Các vấn đề còn lại chỉ là thuần tuý về mặt kỹ thuật mà hầu như chúng ta có thể giải quyết một cách triệt để. 3.2 Đặc điểm về từ trong tiếng Việt và việc tách từ 3.2.1 . Đặc điểm về từ trong tiếng Việt: Tiếng Việt là ngôn ngữ đơn lập. Đặc điểm này bao quát tiếng Việt cả về mặt ngữ âm, ngữ nghĩa, ngữ pháp. Khác với các ngôn ngữ Ấn-Âu, mỗi từ là một nhóm các ký tự có nghĩa được cách nhau bởi một khoảng trắng. Còn tiếng Việt, và các ngôn ngữ đơn lập khác, thì khoảng trắng không phải là căn cứ để nhận diện từ. 3.2.1.a Tiếng:  Trong tiếng Việt trước hết cần chú ý đến đơn vị xưa nay vẫn quan gọi là tiếng. Về mặt ngữ nghĩa, ngữ âm, ngữ pháp, đều có giá trị quan trọng.  Sử dụng tiếng để tạo từ có hai trường hợp:  Trường hợp một tiếng: đây là trường hợp một tiếng được dùng làm một từ, gọi là từ đơn. Tuy nhiên không phải tiếng nào cũng tạo thành một từ.  Trường hợp hai tiếng trở lên: đây là trường hợp hai hay nhiều tiếng kết hợp với nhau, cả khối kết hợp với nhau gắn bó tương đối chặt chẽ, mới có tư cách ngữ pháp là một từ. Đây là trường hợp từ ghép hay từ phức. Lê Thuý Ngọc - 0012745 31 Đỗ Mỹ Nhung - 0012624
  40. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt 3.2.1.b Từ: Có rất nhiều quan niệm về từ trong tiếng Việt , từ nhiều quan niệm về từ tiếng Việt khác nhau đó chúng ta có thể thấy đặc trưng cơ bản của "từ " là sự hoàn chỉnh về mặt nội dung, từ là đơn vị nhỏ nhất để đặt câu. Người ta dùng "từ" kết hợp thành câu chứ không phải dùng "tiếng" do đó quá trình lập chỉ mục bằng cách tách câu thành các "từ" cho kết qua tốt hơn là tách câu bằng “tiếng”. 3.2.2 Tách từ Việc xác định từ trong tiếng Việt là rất khó và tốn nhiều chi phí. Do đó, cách đơn giản nhất là sử dụng từ điển được lập sẵn . Tách tài liệu thành các từ, loại bỏ các từ láy, từ nối, từ đệm, các từ không quan trọng trong tài liệu. Một câu gồm nhiều từ ghép lại, tuy nhiên trong một câu có thể có nhiều cách phân tích từ khác nhau. Ví dụ : xét câu "Tốc độ truyền thông tin sẽ tăng cao" có thể phân tích từ theo các cách sau: Tốc độ / truyền/ thông tin / sẽ / tăng cao. Tốc độ / truyền thông / tin / sẽ / tăng cao. Hiện đã có nhiều giải pháp cho vấn đề này với kết quả thu được rất cao. Tuy nhiên thời gian, chi phí tính toán, xử lý lớn không thích hợp cho việc lập chỉ mục cho hệ thống tìm kiếm thông tin vì số lượng tài liệu phải xử lý là rất lớn. Cách giải quyết: lập chỉ mục cho các từ có thể có trong một tài liệu. Ví dụ câu trên ta nên lập xem xét các từ : tốc độ, truyền , truyền thông ,thông tin, tin , sẽ , tăng cao. Lê Thuý Ngọc - 0012745 32 Đỗ Mỹ Nhung - 0012624
  41. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Sau đó sẽ dùng ngưỡng chặn để loại bỏ các từ, giả sử từ "truyền thông" không phải là một từ xuất hiện thật sự trong tài liệu (chỉ có được do sự kết hợp ngẫu nhiên từ "truyền" và "thông tin") thì xác suất xuất hiện của từ này trong tài liệu sẽ không cao nên khi tính toán trọng lượng thì từ này sẽ bị loại bỏ. Một từ trong tiếng V iệt là sự kết hợp của hai hay nhiều tiếng. Phương pháp xác định một từ được ghép lại thông qua nhiều tiếng dựa trên việc xem xét độ gắn kết (cohesion) giữa chúng: Cohension(nij) = size_factor*pair_freqij/(ni*nj) Trong đó: size_factor: kích thước tập chỉ mục pair_freqij : tần số xuất hiện từ ni , nj : tần số xuất hiện tiếng i, j Hai tiếng có khả năng tạo thành một từ cao khi chúng thường xuất hiện chung với nhau, nghĩa là cohension của chúng cao. Phương pháp này không tách từ chính xác hoàn toàn nhưng có thể chấp nhận trong hệ thống tìm kiếm thông tin vì trong quá trình lập chỉ mục chỉ cần xác định đúng các từ có trọng lượng cao, trong trường hợp việc tách từ là sai thì từ sai chỉ được lập chỉ mục khi nó có trọng lượng cao, việc lập chỉ mục một từ sai sẽ làm tăng chi phí lưu trữ nhưng có lẽ không ảnh hư ởng lớn tính chính xác kết quả tìm kiếm vì dù sao từ này cũng có trọng lượng lớn. Còn trong trường hợp một từ ghép được tách thành nhiều từ đơn ví dụ từ "thông tin" khi được lập chỉ mục sẽ luôn có 3 từ "thông", "tin", "thông tin" , điều này gây ảnh hưởng đến tính chính xác của việc lập chỉ mục vì thực sự các từ "thông", "tin" không Lê Thuý Ngọc - 0012745 33 Đỗ Mỹ Nhung - 0012624
  42. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt cần thiết lập chỉ mục.Ta giải quyết vần đề này bằng cách nếu từ "thông tin" được lập chỉ mục thì khi đó số lần xuất hiện của các từ "thông" và "tin" sẽ được tính toán lại bằng cách trừ đi các trường hợp đã xuất hiện trong từ "thông tin" để tính toán trọng lượng cho các từ đơn. Nếu từ đơn "tin" chỉ luôn xuất hiện trong từ "thông tin" thì số lần xuất hiện của từ "tin" và "thông tin" là bằng nhau nên khi lập chỉ mục cho từ "thông tin" thì số lần xuất hiện riêng của từ đơn "tin" sẽ bằng 0 nên không được lập chỉ mục. 3.3 Giải quyết các vấn đề hiển thị của tiếng Việt (vấn đề chính tả) 3.3.1 Vấn đề bảng mã Sự tồn tại của nhiều bảng mã ( TCVN3, VNI ) dẫn đến việc phải chuyển nội dung các tài liệu được viết trên các bảng mã khác về bảng mã chuẩn cho hệ thống tìm kiếm thông tin xử lý (lập chỉ mục), việc chuyển đổi này là đơn giản trong trường hợp ta biết bảng mã của tài liệu, nhưng vấn đề khó khăn là làm sao cho hệ thống tìm kiếm thông tin nhận ra một tài liệu đang sử dụng bảng mã nào? Khi phân tích một trang tài liệu HTML, dựa vào thông tin thì có thể biết được bảng mã nào đang được sử dụng, ví dụ: charset = UTF -8 thì đó là bảng mã Unicode Tuy nhiên, trong một tài liệu có thể sử dụng nhiều bảng mã khác nhau nên không thể xác định bảng mã của tài liệu theo cách trên. Ta có thể áp dụng phương pháp phân tích từ khoá để xác định bảng mã như sau: dựa trên sự thống kê số lần xuất hiện của các ký tự đặc biệt theo từng bảng mã, bảng mã nào có tầ n số sử dụng nhiều nhất thì xem như trang đó sử dụng bảng mã đó. Lê Thuý Ngọc - 0012745 34 Đỗ Mỹ Nhung - 0012624
  43. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Thật ra, không cần phải xác định bảng mã vẫn có thể lập chỉ mục cho hệ thống bằng cách chuyển mã tài liệu sang một kiểu định dạng, theo bảng mã quy định của hệ thống tìm kiếm. Trong thực tế, các bảng mã đều có một phần chung và một phần các ký tự đặc biệt là khác nhau. Do đó, nhằm hạn chế thời gian và chi phí xử lý, ta sẽ chuyển những ký tự khác nhau về bảng mã quy định. Các bước thực hiện như sau: Đọc một từ, nếu là từ mang dấu tổ hợp nguyên âm hay dấu thanh thì thực hiện so sánh với tất cả các bảng mã chuẩn để xác định bảng mã của từ đó. Nếu bảng mã đó không trùng với bảng mã quy định của hệ thống thì thực hiện chuyển từ bảng mã đó sang bảng mã quy định. Cứ vậy, tiếp tục cho đến hết văn bản và dừng. Có thể dùng một bảng mã thông dụng nào đó để làm bảng mã quy định cho hệ thống, chẳng hạn Unicode vì hiện nay theo xu hướng chung thì số lượng các trang web, tài liệu dùng Unicode rất lớn và đang tăng nhanh, nên sẽ hạn chế được số lượng các trang web cần chuyển đổi. 3.3.2 Vấn đề dấu thanh Do cách bỏ dấu tiếng Việt chưa thống nhất nên có khi cùng một từ lại có nhiều các bỏ dấu khác nhau, ví dụ "thuý" và "thúy", rõ ràng hệ thống tìm kiếm thông tin cần nhận ra hai từ này là một. Phương pháp giải quyết dựa tr ên đặc điểm một từ đơn tiếng Việt chỉ có một dấu nên ta sẽ chuyển dấu từ ra sau cùng, ví dụ: quý -> thuy1 qúy -> thuy1 Khi đó tất cả các từ giống nhau cho dù bỏ dấu khác nhau thì qua quá trình xử lý đều cho chuỗi kí tự giống nhau thuận tiện cho việc so sánh từ. Lê Thuý Ngọc - 0012745 35 Đỗ Mỹ Nhung - 0012624
  44. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt 3.3.3 Vấn đề dấu tổ hợp nguyên âm Một tài liệu hay một câu truy vấn không thể tránh khỏi trường hợp bỏ thiếu dấu tổ hợp nguyên âm. Ví dụ: nuớc(nước), trừong(trường), Như vậy, ta cần phải xây dựng một module xác định và sửa lỗi cho từ. Giải pháp đề ngh ị ở đây là chuyển các từ về một định dạng riêng, gồm hai phần: phần đầu là các k ý tự không dấu, phần sau là dấu tổ hợp nguyên âm và dấu thanh. Giai đoạn chuyển mã sẽ thực hiện chuyển các dấu tổ hợp nguyên âm và dấu thanh ra cuối của từ. Ví dụ: hường truong772 hừơng truong772 hừong truong772 huờng truong772 Như vậy, dù dấu thanh có bỏ ở vị trí nào thì cũng cho chuỗi ký tự giống nhau sau khi xử lý. Ngoài ra, nó còn có khả năng phát hiện ra những từ mà người dùng gõ thiếu dấu tổ hợp nguyên âm. Ví dụ: huờng huong72, chương trình sẽ tìm kiếm trong cơ sở dữ liệu và sẽ thấy đúng được phần đầu, còn về dấu thanh thì sẽ chọn một trong các tổ hợp gần nhất có thể có trong từ điển như: hương huong77 hướng huong771 hường huong772 hưởng huong773 hượng huong775 Lê Thuý Ngọc - 0012745 36 Đỗ Mỹ Nhung - 0012624
  45. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Trong tự điển tiếng Việt, không thể có các từ như trưong hay truơng. Nên người dùng chắc chắn đã gõ thiếu và do đó phải là từ truong772 (trường). 3.4 Giải quyết các vấn đề về từ của tiếng Việt 3.4.1 Luật xác định các từ láy Từ láy không là từ có ý nghĩa quan trọng trong tài liệu. Vì vậy, ta cần xác định từ láy để giảm số lượng các từ ghép cần lập chỉ mục. Trong các loại từ láy thì láy hai là nhiều nhất. Vì vậy, ta cần phải xây dựng luật để xác định nó. Mỗi luật tương ứng với một loại từ láy: Từ láy hoàn toàn. Ví dụ: xanh xanh =>Luật xác định từ láy hoàn toàn Từ láy phụ âm đầu. Ví dụ: biêng biếc=>Luật xác định từ láy phụ âm đầu Từ láy vần. Ví dụ: chót vót =>Luật xác định từ láy vần 3.4.2 Luật xác định các liên từ Liên từ đầu câu cũng không đóng vai trò quan trọng trong tài liệu. Hầu hết các trường hợp thì theo sau các liên từ đầu câu là dấu phẩy. Ví dụ: Vì thê, Do đó, Ta có thể dựa vào cú pháp này để xây dựng luật xác định các liên từ để giảm số lượng từ cần lập chỉ mục. 3.5 Xây dựng từ điển tiếng Việt Việc xác định từ cho tiếng Việt thì phương pháp giải quyết là dùng từ điển từ được lập sẵn. Lê Thuý Ngọc - 0012745 37 Đỗ Mỹ Nhung - 0012624
  46. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Tuy nhiên không thể có một từ điển đầy đủ được vì có những từ có thể "sinh ra thêm" trong tương lai. Ví dụ do sự ra đời của nhiều ngành khoa học công nghệ mới đòi hỏi phải ph át sinh thêm từ mới để mô tả chúng , hoặc do nhu cầu sử dụng tiếng nước ngoài ngày càng tăng dẫn đến tình trạng Việt hoá các từ thông dụng như bit, bite, inch, Do đó bên cạnh việc sử dụng từ điển đòi hỏi phải có phương pháp để phát hiện thêm từ tiếng Việt mới chưa có trong từ điển để bổ sung cho từ điển. Một "từ" tiếng Việt là sự kết hợp của hai hay nhiều "tiếng" có thể dễ dàng xác định bằng khoảng trắng, phương pháp xác định "từ" gồm nhiều "tiếng" ghép lại dựa trên việc xem xét độ gắn kết (cohesion) của chúng: cohesionij = size_factor * pair_freqij / ( ni * nj ) Trong đó: size_factor : kích thước tập chỉ mục. pair_freqị : tần số xuất hiện từ. ni, nj : tần số xuất hiện của tiếng i, j. Sự kết hợp 2 tiếng có khả năng cho ra từ cao khi cohesion của chúng cao (2 tiếng thường xuất hiện chung với nhau thì nó có khả năng là một từ). Giải pháp đề nghị là dùng từ điển được lập sẵn ,với một chi phí thấp hơn ta có thể lập được một từ điển tương đối đầy đủ mà kết quả chính xác hơn rất nhiều. Quá trình xác định thêm số từ thiếu có thể được cài đặt bằng phương pháp xác định từ ghép tự động như đã nêu trên với tập tài liệu mẫu cho việc xác định từ ghép được chỉ định, hoặc bổ sung thêm từ mới vào từ điển Lê Thuý Ngọc - 0012745 38 Đỗ Mỹ Nhung - 0012624
  47. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Tuy nhiên, khi xác định một từ mới thì không thể thêm ngay nó vào từ điển. Vì làm như vậy sẽ dẫn đến tình trạng bùng nổ dữ liệu. Bởi vì một từ là mới do quá trình tách từ chưa hẳn là từ mới thật sự. Do đó, ta sẽ xây dựng thêm từ điển phụ để chứa các từ mới này, sau một khoảng thời gian kiểm tra các thông số như:  Số lần xuất hiện trong tất cả các tài liệu mà hệ thố ng xử lý  Số tài liệu mà từ đó xuất hiện  Nếu các thông số trên đạt một tiêu chuẩn nào đó thì mới chính thức thêm nó vào từ điển chính và xoá nó ra khỏi từ điển phụ. Lê Thuý Ngọc - 0012745 39 Đỗ Mỹ Nhung - 0012624
  48. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Chương 4: BỘ TÌM KIẾM THÔNG TIN – SEARCH ENGINE 1. Vì sao ta cần một công cụ tìm kiếm (SE) ? Tưởng tượng ta muốn tìm vài quyển sách trong một thư viện rất lớn. Với sức lực cá nhân ta không thể xem qua hết tất cả sách, vì vậy ta cần một danh mục sách. Tương tự, tồn tại hàng triệu trang web trên thế giới và mỗi phút trôi qua số lượng được đẩy lên càng nhiều hơn, cho dù ta có trong tay một công cụ lướt web tuyệt vời đến đâu cũng không thể duyệt hết. Tuy nhiên, với sự trợ giúp của SE, ta có thể thậm chí xác định được vị trí của những từ cần tìm trong các trang web khắp nơi trên thế giới. 2. Các phương thức tìm kiếm 2.1 Tìm theo từ khoá – Keyword searching Đây là phương pháp được áp dụng với hầu hết các search engine. Trừ khi tác giả của trang web xác định từ khóa cho tài liệu của mình, ngược lại điều này phụ thuộc vào search engine. Như vậy các search engine sẽ tự mình chọn và đánh chỉ mục cho những từ mà chúng cho quan trọng có thể giúp phân biệt các tài liệu khác nhau. Các từ được đề cập trong phần II chương II hoặc các từ lặp lại nhiều lần đều được chú ý. Một số site lập chỉ mục cho tất cả các từ có trong một trang web, một số khác chỉ chọn một số đoạn văn bản. Các hệ thống đánh chỉ mục trên toàn văn bản (full-text indexing systems) đếm số lần xuất hiện của mỗi từ trong tài liệu ngoại trừ các từ stopword. Có những công cụ tìm kiếm còn phân biệt cả chữ hoa lẫn ch ữ thường. Lê Thuý Ngọc - 0012745 40 Đỗ Mỹ Nhung - 0012624
  49. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt 2.2 Những khó khăn khi tìm theo từ khoá Search engine thường gặp rắc rối với những từ đồng âm khác nghĩa (ví dụ hard cider, hard stone, a hard exam, hard drive) hoặc những từ có các biến thể khác nhau do có tiền tố và hậu tố như big, bigger, student, students, . Bên cạnh đó search engine cũng không thể trả về các tài liệu chứa những từ đồng nghĩa với các từ trong câu truy vấn. 2.3 Tìm theo ngữ nghĩa – Concept-based searching Excite đã từng nổi tiếng với chiến thuật tìm theo ngữ nghĩa nhưng giờ đây chiến thuật này không còn được sử dụng nữa. Không giống các hệ thống tìm theo từ khoá, hệ thống tìm theo ngữ nghĩa sẽ ‘đoán’ ý muốn của người dùng thông qua câu chữ. Tìm theo ngữ nghĩa hoạt động dựa trên hình thức gom nhóm tài liệu, phức tạp hơn thì dựa vào ngôn ngữ học, các thuyết về trí tuệ nhân tạo. Excite tiếp cận dựa vào phương pháp tính toán bằng cách đếm số lần xuất hiện của các từ quan trọng. Khi nhiều từ hoặc những cụm từ có nghĩa đặt gần nhau trong tài liệu thì Excite sẽ cho rằng chúng đang ám chỉ một chủ đề nào đó. Ví dụ, khi từ ‘heart‘ đứng gần các từ như ‘attack‘ (cơn đau tim), ‘blood‘ (sự sống), ‘stroke‘ (sự say nắng), thì search engine sẽ xếp những trang chứa các từ này vào chủ đề y học và sức khoẻ. Ngược lại, khi từ ‘heart‘ đứng gần các từ ‘flowe rs’, ‘candy’, thì search engine sẽ xếp những trang chứa các từ này vào chủ đề trữ tình. Lê Thuý Ngọc - 0012745 41 Đỗ Mỹ Nhung - 0012624
  50. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt 3. Các chiến lược tìm kiếm Mọi người đều nhận xét rằng web là nơi mà ta luôn có được thông tin về bất kỳ chủ đề gì. Nhưng kết quả cuối cùng thường là lãng phí thời g ian cho những URL vô ích. Do đó đã đến lúc ta nghĩ đến các chiến lược tìm kiếm. Ta khởi đầu với một đống thông tin trên một chủ đề khá rộng ? Hoặc ta đã hình dung được cụ thể những gì cần tìm ? Hay ta muốn tìm địa chỉ của ai đó ? Nếu phạm vi quan tâm của ta quá rộng, ta nên xem xét các thư mục web (web directory). Nếu sau đó ta thu hẹp phạm vi cần tìm, hãy xem xét việc lựa chọn một công cụ tìm kiếm thích hợp. 3.1 Tìm thông tin với các thư mục chủ đề Giống như tìm sách trong thư viện, cân nhắc giữa tìm theo t ác giả, tiêu đề, chủ đề, ta thường chọn chủ đề để có thể bao quát một vùng thông tin rộng hơn. Ví dụ : ta muốn tạo một trang chủ (home page) nhưng không biết cách viết một file HTML như thế nào, thậm chí chưa từng tạo một file ảnh, và cũng không biết cách đẩy một trang lên mạng. Tóm lại ta cần những thông tin cho một chủ đề khá rộng - xuất bản một trang web (web publishing). Khi hoàn toàn xác định mình cần tìm những gì ta nên bắt đầu từ một thư mục web như thư mục của Yahoo hoặc Google, vì thư mục web tập trung nhiều vào chủ đề đang được quan tâm hơn là một công cụ tìm kiếm. Gần đây các web site thường kết hợp thư mục web và các công cụ tìm với nhau. Ví dụ nếu ta sử dụng Google để tìm thông tin và một trong những kết quả này nằm Lê Thuý Ngọc - 0012745 42 Đỗ Mỹ Nhung - 0012624
  51. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt trong thư mục web của Google, Google sẽ cung cấp cho ta một liên kết dẫn vào thư mục. 3.2 Tìm thông tin với các công cụ tìm kiếm Một số công cụ tìm kiếm gặp rắc rối với dữ liệu đầu vào của người dùng. Ví dụ : những từ chứa các ký tự đặc biệt như C++ , những từ chứa stopword như to be or not to be. Xét ví dụ khác ít rõ ràng hơn. Giả sử ta là một người rất thích tiểu thuyết trinh thám và muốn tìm những trang nói về các tác giả yêu thích. Nếu đơn giản chỉ nhập vào các từ ‘mystery‘ và ‘writer’, phần lớn các search engine sẽ trả về các li ên kết dẫn đến các trang chứa một trong 2 từ trên hoặc cả 2. Như vậy có khả năng hàng trăm, thậm chí hàng ngàn URL không mong muốn. Tuy nhiên nếu ta nhập vào 1 cụm từ, kết quả sẽ khả quan hơn. 3.3 Tối ưu câu truy vấn Rất nhiều search engine áp dụng các toán tử Boolean (Boolean operators) hoặc các bộ định vị trí (proximai locators) để tối ưu câu truy vấn. Đó là các từ khoá sau : STT Từ khóa Ý nghĩa 1 AND / phép toán + Mọi từ trong câu truy vấn phải có trong tài liệu 2 OR Tài liệu chứa ít nhất một từ cần tìm 3 NOT / phép toán - Tài liệu không chứa [các] từ sau từ khoá Lê Thuý Ngọc - 0012745 43 Đỗ Mỹ Nhung - 0012624
  52. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt 4 NEAR Các từ cần tìm cách nhau bao nhiêu ký tự trong tài liệu 5 FOLLOWED BY / Các từ cần tìm phải đứng cạnh nhau trong tài liệu ADJ Bảng 4.1 : Các từ khóa giúp tối ưu câu truy vấn 3.4 Truy vấn bằng ví dụ Một điểm đáng kích lệ nữa của search engine là truy vấn bằng ví dụ. Sau khi liệt kê một loạt các tài liệu được cho là thoả yêu cầu người dùng, search engine còn ‘gợi ý‘ một vài site có liên quan đến chủ đề ta đang quan tâm. Nếu có thể ta hãy theo sau các liên kết này, biết đâu sẽ có kết quả khả quan! Lê Thuý Ngọc - 0012745 44 Đỗ Mỹ Nhung - 0012624
  53. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Chương 5: MỘT SỐ SEARCH ENGINE THÔNG DỤNG TRÊN THẾ GIỚI VÀ VIỆT NAM Vài nét về các đặc trưng của một số search engine thông dụng trên thế giới Search Google AlltheWeb AltaVista Teoma Engine Database google.com alltheweb.com altavista.com teoma.com Kích thước(# Khoảng 4 tỉ (1 Khoảng 3 tỉ, Khoảng 1 tỉ Khoảng 1 tỉ trang) tỉ không đánh chỉ mục trên chỉ mục trên toàn văn bản. toàn văn bản) Đa phương Hỗ trợ Hỗ trợ Hỗ trợ Không hỗ trợ tiện (multimedia) Toán tử Mặc định AND AND AND AND Loại trừ - - - - Lê Thuý Ngọc - 0012745 45 Đỗ Mỹ Nhung - 0012624
  54. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Cụm từ Dùng dấu “ “ Dùng dấu “ ” Dùng dấu “ ” Dùng dấu “ “ Rút gọn Không hỗ trợ Không hỗ trợ Dùng ký tự * Không hỗ trợ Dùng ký tự * để thay thế cho các ký tự trong dấu “ “ Boolean OR (chỉ dùng AND, OR, AND, OR, OR (chỉ dùng cho danh từ ANDNOT, ANDNOT, cho tên riêng) riêng ) RANK, () NEAR, () Stop words Thông thường Dùng dấu “ “ Thông thường bỏ qua các từ trong search cơ bỏ qua các từ thông dụng bản thông dụng + nếu muốn Bỏ qua trong + nếu muốn tìm tìm và phải đặt search nâng trong cặp dấu “ cao “ Danh từ riêng Không hỗ trợ Không hỗ trợ Hỗ trợ Không hỗ trợ Giới hạn intitle:inurl: normal.title: title:domain: intitle:inurl: field cần tìm allintitle: url.all: link:image: site:geoloc:lang: allinurl: link.all: text:url:host: last: filetype: afterfate: Lê Thuý Ngọc - 0012745 46 Đỗ Mỹ Nhung - 0012624
  55. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt link:site: link.extension: anchor:applet: Trong search nâng cao : cache:info: Các đặc tính ~ tìm từ đồng Duyệt qua các Giới hạn bởi Dùng refine để đặc biệt nghĩa URL ngày, vị trí, tối ưu kết quả. ữ Giới hạn bởi Trong tìm ngôn ng Resource để có ngôn ngữ nâng cao : Trong tìm được các trang ử ết tập Nhiều kiểu file giới hạn bởi nâng cao : s và liên k : pdf, doc, ngày, domain, dụng sortby để trung trên chủ đề ịa chỉ iP lọc và sắp xếp cần tìm. Caches : trang đ kết quả. web khi đánh chỉ mục Ưu điểm Ưu điểm Rất tốt với Tốt như Dùng nhiều Tính độ phổ chính những trang có Google. toán tử biến tốt, dựa vào độ phổ biến Không có stop Boolean trong số lượng trang ếm. ủ đề cao. word. tìm ki web cùng ch Các trang tin Trong tìm với các trang tức gần đây nâng cao hỗ đang xét. ờng đạt kết trợ hiển thị kết Thư quả theo độ quả đáng khích ệ. phổ biến của l Lê Thuý Ngọc - 0012745 47 Đỗ Mỹ Nhung - 0012624
  56. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt từ. Search Google AlltheWeb AltaVista Teoma Engine Bảng 5.1 : Bảng hướng dẫn nhanh về cách sử dụng các search engine phổ biến trên thế giới Search Cơ sở dữ liệu Toán tử Lực chọn tìm Linh tinh engine kiếm Google Toàn văn bản AND (mặc Dùng * để rút Kiểm lỗi của các trang định) gọn. chính tả. oogle.com web, .pdf, OR (danh từ Dùng “” tìm cụm Lưu trữ các .doc, .xls, .ps, Hỗ trợ tìm riêng) từ. trang đã lập .wpd kiếm nâng + cho các stop fields : intitle:, chỉ mục. cao (4.3B, + 1B word thông inurl:, link:, site: Tốt cho tìm một phần của Hệ thống thư dụng, cho các Tìm trên hệ các trang hay chỉ mục ặc các ị lỗi 404. mục chủ đề URL ho thống danh mục b URLs) trang cụ thể (ví (Subject các chủ đề trong Phiên dịch Tin tức : cập dụ +edu) ục web. ến 5 ngôn Directory) thư m đ nhật thường - loại trừ Tìm các trang ngữ. Hệ thống thư xuyên (4500 web tương tự. ~ tìm từ đồng mục mở nguồn ). ĩa. (Open ngh Các dạng file Lê Thuý Ngọc - 0012745 48 Đỗ Mỹ Nhung - 0012624
  57. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Directory) ảnh Nhóm : Usenet từ 1981 đến nay AlltheWeb Toàn bộ văn AND (mặc Không rút gọn. Kiểm lỗi ản các trang ịnh) ả. b đ Dùng dấu “ “ cho chính t eb.com web, .pdf, OR, phải đặt cụm từ. Tìm nâng cao Flash, ừ trong ảnh, Hỗ trợ tìm các t Field intitle:inurl: : tranh (3.1B toàn bộ dấu “ “. video. kiếm nâng link:site: ỉ mục cao ch ANDNOT, Hỗ trợ sử Trong tìm nâng URLs) RANK dụng kỹ thuật cao : Tin tức : cập - để loại bỏ “clusters” để nhật thường giới hạn theo tối ưu câu xuyên (3000 ngày, ngôn ngữ, truy vấn. nguồn) domain, file format, địa chỉ Tranh ảnh iP. Video Audio FPT AltaVista Toàn bộ văn AND (mặc Dấu * để rút gọn. Kiểm lỗi bản các trang định) Dấu “” cho cụm chính tả. web (khoảng Lê Thuý Ngọc - 0012745 49 Đỗ Mỹ Nhung - 0012624
  58. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt a.com 1B) và file Trong tìm nâng từ. Phiên dịch : 8 ặc danh ữ của Hỗ trợ tìm .pdf. cao ho Tìm nâng cao : ngôn ng êng trong kiếm nâng Tin tức (3000 từ ri giới hạn ngày, Châu Âu & ơ bản : ữ cao nguồn), ảnh, tìm c ngôn ngữ. các ngôn ng AND, OR, của Châu Á. Hệ thống thư MP3/Audio, ANDNOT, mục chủ đề Video. AltaVistaPri ấu () NEAR, d ma : tối ưu (Subject lồng nhau. câu hỏi. Directory ) - cho loại trừ. Hệ thống thư mục mở (Open Directory) Teoma Toàn bộ văn AND (mặc Không rút gọn. Kiểm lỗi ản trang web ịnh) ả. b đ Dùng dấu “ “ cho chính t om (khoảng 1B) OR (danh từ cụm từ. Gom nhóm ết quả Hỗ trợ tìm riêng) Field intitle:inurl: k Refine để tối kiếm nâng + hoặc “” cho site:geoloc:lang:l ưu câu hỏi. cao stopword ast: Resource để - để loại bỏ afterdate:befored có các trang ate: hoặc liên kết betweendate: tập trung vào Trong tìm nâng chủ đề. cao : Lê Thuý Ngọc - 0012745 50 Đỗ Mỹ Nhung - 0012624
  59. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt giới hạn theo ngày, ngôn ngữ, domain, file format, địa chỉ iP. AskJeeves Nhận kết quả Giống Teoma. Giống Teoma. Kiểm lỗi www.ask.co từ CSDL của Đối với những Click vào chính tả. m Teoma. câu hỏi đơn Remove Frame Tìm sản phẩm giản, xuất hiện để thấy URLs : cửa sổ đối của các trang. PriceGrabber. thoại. com, Tìm tranh ảnh : Picsearch.co m Tìm tin tức : Moreover.co m. Lê Thuý Ngọc - 0012745 51 Đỗ Mỹ Nhung - 0012624
  60. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt AskJeeves for Trả lời tốt các Hỏi bằng ngôn Click vào No Dẫn đến các Kids câu hỏi đơn ngữ tự nhiên. frames để thấy trang phục vụ www.ajkids.c giản. Không sử dụng URL của trang học tập : tự ết quả. ển, vật lý, om Games cho các toán tử k đi trẻ em, Boolean. khoa học, bản đồ, lịch sử, Tin tức theo từng nhóm tuổi. Bảng 5.2 : Sơ lược về các đặc trưng của một số search engine thông dụng trên internet Meta-search Cơ sở dữ Toán tử Lực chọn tìm Linh tinh engine liệu kiếm Vivisimo Netscape, AND(mặc Tìm trên chủ đề : Gom nhóm kết MSN, định), OR, - tin tức, thương quả. ại, kỹ thuật, mo.com Lycos,LookS m Tốt đối với chủ mart, thể thao. đề về các sự kiện & nhiều khía cạnh khác. Dopgpile Google, Tìm nâng cao : Sắp xếp theo kết Kiểm lỗi chính ả. ả. Yahoo, AND, OR, qu t Lê Thuý Ngọc - 0012745 52 Đỗ Mỹ Nhung - 0012624
  61. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt le.com AltaVista, ANDNOT. Xoá các kết quả Highlight từ cần Teoma/AskJe trùng. tìm trong kết eves, quả. About.com, Gom nhóm kết FAST, quả. FindWhat, Tốt đối với chủ LookSmart đề về các sự kiện & nhiều khía cạnh khác. Bảng 5.3 : Các meta-search engine thông dụng trên internet Thư mục chủ Cơ sở dữ Toán tử Lực chọn tìm Linh tinh đề liệu kiếm Yahoo Xem xét các AND(mặc Cụm từ : “” Nhiều dịch vụ trang web định) Rút gọn : * trong Yahoo: (khoảng ức : từng o.com OR Fields t: title, Tin t 13K) - u:URL giờ. Thể thao :tỉ số, Bản đồ, thời tiết, mua sắm. Lê Thuý Ngọc - 0012745 53 Đỗ Mỹ Nhung - 0012624
  62. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Academic Mức độ cao AND, OR(mặc Dẫn đến các info đẳng hoặc định), NOT, chương trình nghiên cứu dấu () lồng mức độ cao ũng hữu ẳng hoặc các icinfo.net (c nhau. đ ích cho site, các nguồn trung học). tài nguyên ữu ích Được chọn khác h và chú thích cho sinh viên. bởi thủ thư Michael Madin (khoảng 25K) Bảng 5.4 : Các hệ thống thư mục theo chủ đề thông dụng trên internet 1.1 Thư mục của Yahoo, Google  Về bản chất là các danh mục chủ đề.  Sắp xếp các trang theo mức độ quan trọng của chúng.  Tìm theo đề tài hoặc chủ đề. Google là một trong những công cụ tìm kiếm mới nhưng nhanh chóng được ưa chuộng nhờ khả năng tìm nhanh và chính xác. Ý tưởng chính của công cụ này là đo lường độ quan trọng của một trang dựa vào số liên kết đến trang đó. Nói cách khác nếu Lê Thuý Ngọc - 0012745 54 Đỗ Mỹ Nhung - 0012624
  63. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt nhiều webmaster cùng quan tâm đến một website thì website đó xứng đáng được đánh giá cao. Yahoo đã từng dùng Google như một chức năng của mình trong một thới gian dài. Kỹ thuật tìm kiếm của Microsoft và MSN.com dựa trên kỹ thuật inktomi. (inktomi đã được áp dụng cho một trong những search engine nổi tiếng trong những năm 90 là Hobot) Microsoft đã rất nỗ lực trong việc tìm ra một kỹ thuật cho riêng mình nhưng vẫn chưa thành công. 1.2 Alltheweb Alltheweb cũng là một trong những công cụ tìm kiếm mới, được cho là công cụ dò tìm nhanh hơn và hiệu quả hơn các search engine khác nhờ một lượng chỉ mục rất lớn. Alltheweb đã được sử dụng bởi Yahoo. 1.3 AltaVista Đã từng là một trong những công cụ tìm kiếm được ưa chuộng nhất nhưng bị đánh bại bởi Google. Mặc dù vậy nó vẫn là một search engine cho kết quả chính xác và từng được Yahoo sử dụng. 1.4 Lycos Được mô tả như là những cổng truy cập web (web portal) hay nh ững trung tâm truy cập, là nơi mà người dùng đi vào để lấy thông tin cho mọi lĩnh vực, kể cả tán gẫu, gởi thư điện tử, 1.5 HotBot Đã đề cập ở trên, HotBot dựa trên kỹ thuật inktomi, là công cụ tìm kiếm chuyên biệt, cung cấp nhiều thông tin chính xác, nhanh chóng cho lĩnh vực thương mại và các Lê Thuý Ngọc - 0012745 55 Đỗ Mỹ Nhung - 0012624
  64. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt mục đích chuyên môn, hứa hẹn một sự thay thế cho các công cụ thường dùng khác khá tốt. 2. Một số search engine thông dụng ở Việt Nam 2.1 Netnam [IV.12] Là một đơn vị thuộc viện hàn lâm - Viện Công nghệ Thông tin, Netnam đặc biệt chú trọng đến việc thiết kế hệ thống phù hợp với điều kiện cơ sở vật chất - hạ tầng còn khiêm tốn ở Việt Nam. Vì vậy, một trong những ưu tiên quan trọng trong các yêu cầu xây dựng hệ thống là khả năng tiết kiệm chi phí đầu tư cơ sở hạ tầng kỹ thuật, đồng thời phải đáp ứng được nhu cầu mở rộng cao. Do đó Netnam SE được thiết kế theo kiến trúc sử lý song song.với các khối chức năng như hình dưới đây. Kiến trúc này cho phép hệ thống có thể phân tán trên từ một đến hàng trăm máy tính, cho phép sử dụng các máy tính PC cỡ nhỏ thay cho các hệ máy tính chủ cao cấp. Từ đó hệ thống cho phép tiết giảm chi phí tối đa trong việc xây dựng hạ tầng ban đầu, đồng thời khi nhu cầu tính toán hoặc yêu cầu phục vụ liên tục tăng, chỉ cần thêm các má y tính vào hệ thống để tăng cường khả năng xử lý và khả năng phục vụ liên tục mà không cần bổ sung bất cứ thành phần nào khác. Phần kiến trúc này sẽ giới thiệu về mô hình chia sẻ tính toán song song của hệ thống. Về mặt vật lý, các máy tính được có thể kế t nối với nhau đơn giản bằng hệ thống mạng Ethernet 10/100/1000Mbps. Hệ thống cho phép thay đổi nóng (hotswap) một hoặc một vài đơn vị vật lý (máy tính) mà không làm ảnh hưởng đến hoạt động của toàn hệ thống, cũng như cho phép thực hiện thay thế tự động mộ t hoặc một vài đơn vị vật lý của hệ thống khi chúng gặp sự cố bất ngờ. Lê Thuý Ngọc - 0012745 56 Đỗ Mỹ Nhung - 0012624
  65. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Hình 5.1 Sơ đồ hệ thống Search Engine của Netnam Lê Thuý Ngọc - 0012745 57 Đỗ Mỹ Nhung - 0012624
  66. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Hệ thống được chia thành ba tầng chính, gồm tầng Thu thập thông tin, Nhận dạng và chuyển đổi thông tin thành dạng text, Lập cơ sở dữ liệu cho các thông tin text. Mỗi tầng được chia thành nhiều đơn vị độc lập hoạt động theo kiểu chia sẻ tính toán và/hoặc dự trữ (redundant), từ đó tính tin cậy và hiệu năng của hệ thống cho phép rất cao đối với các hệ thống đòi hỏi tính tin cậy và hiệu năng cao.Đơn vị khai thác dữ liệu được tích hợp cùng với phần lập chỉ mục cơ sở dữ liệu, cho phép khai thác qua các clients sử dụng giao thức TCP/iP trên bất cứ hệ thống nào (Windows, Unix ) Bằng việc chia hệ thống thành các khối chức năng phối hợp với nhau thông qua các Bộ điều phối, hệ thống có thể được phân tán để xử lý trên nhiều máy tính nhỏ thay vì tập trung toàn bộ hệ thống trên một máy tính lớn. Vì vậy, một mặt hệ thống cho phép sử dụng các máy tính cỡ nhỏ (PC hoặc PC server) cùng phối hợp tính toán xử lý, do đó làm giảm rất nhiều chi phí đầu tư so với các hệ máy cỡ mini hay mainframe, và có thể đầu tư dần dần theo sự gia tăng của nhu cầu thay vì đầu tư toàn bộ một lần ban đầu. Mặt khác, nó cho phép, về mặt nguyên tắc, năng lực tính toán, phục vụ thông tin của hệ thống là không hạn chế ? khi nhu cầu tăng lên chỉ cần thêm máy tính vào hệ thống mà không phải thay đổi lại hệ thống. Vì vậy, lượng dữ liệu mà hệ thống có thể phục vụ, về mặt nguyên tắc thiết kế hệ thống, cho phép lên đến hàng trăm triệu tài liệu. 2.1.1 Phương pháp Netnam SE lập chỉ mục dữ liệu Thông thường, NetNam lấy tất cả các từ trong tài liệu để lập chỉ mục, và khi trả kết quả tìm kiếm, NetNam Search Engine tìm ra tất cả các từ trong một trang tài liệu đó, và hiển thị một số từ đầu tiên như một bảng tóm tắt ngắn. Với Netnam ta thể dùng thẻ META trong trang web để :  Cung cấp thêm các từ khoá có ảnh hưởng đến kết quả tìm kiếm của NetNam Search Engine (tác dụng tìm ra trang mà ta cần tìm).  Đưa ra các miêu tả để hiển thị kết quả tìm kiếm. Lê Thuý Ngọc - 0012745 58 Đỗ Mỹ Nhung - 0012624
  67. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Ví dụ, giả sử ta có một trang web quảng cáo bán ô tô, xe máy mới 100%, trang search của NetNam sẽ tự động chỉ ra các từ trong trang. Tuy nhiên, có một số từ hoặc cụm từ miêu tả dịch vụ lại không xuất hiện trong trang. Sử dụng thẻ META và ghi rõ tên="từ khoá" để thêm các cụm từ vào chỉ mục và làm tăng cơ hội tìm kiếm cho người sử dụng khi muốn tìm trang web. Miêu tả thẻ META cho phép ta tìm được cái mà ta muốn tìm trong bản tóm tắt kết quả tìm kiếm. Với trang bán xe của mình, ta có thể muốn một cụm từ quảng c áo ngắn như sau: NetNam Search Engine chỉ ra các từ trong thẻ miêu tả cùng với những thẻ từ khoá. Do đó trong ví dụ này, người sử dụng sẽ có thể tì m ra trang web của ta bằng cách tìm từ "chất lượng cao" cũng như "giá phù hợp", "bảo hành chu đáo". Thay vì hiển thị một số dòng đầu của trang web, kết quả tìm kiếm sẽ hiển thị văn bản của thẻ miêu tả: Car Leasing Corp. Bán xe máy và ô tô với chất lượng cao, bảo hành chu đáo, giá phù hợp. - 3K ? 01/11/2001 Chú ý: các thẻ miêu tả và các thẻ từ khoá có thể dài tối đa là 1024 ký tự . 2.1.2 Cú pháp tìm kiếm Cả hai chức năng tìm kiếm đơn giản và nâng cao đều sử dụng những quy tắc cú pháp giống nhau đối với các cụm từ, phân biệt dạng chữ, và tìm những từ liên quan. Lê Thuý Ngọc - 0012745 59 Đỗ Mỹ Nhung - 0012624
  68. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Từ và cụm từ NetNam Search Engine định nghĩa một từ cũng như bất cứ một chuỗi những chữ cái và con số được tách rời nhau :  Ký tự trắng, như dấu cách, dấu tab, chấm xuống dòng, hoặc chỗ bắt đầu hoặc kết thúc của một tài liệu.  Các ký tự đặc biệt và hệ thống chấm câu, ví dụ như %, $, /, #, và _ Ví dụ, hệ thống tìm kiếm của NetNam sẽ giải thích và chỉ rõ những từ Proliant, 60258, www, http, và XeMayCu như những từ riêng lẻ, vì chúng là những chuỗi ký tự liên tiếp, được bao quanh bởi các ký tự không phải là chữ cũng không phải là số. Phần mềm tìm kiếm sẽ chỉ ra tất cả các từ mà nó tìm được trong một trang tài liệu web không quan tâm liệu từ đó có trong từ điển hay đánh vần sai hay không. Tìm kiếm cụm từ Ta có thể tìm thấy các cụm từ, hoặc một nhóm từ liên quan xuất hiện ngay cạnh nhau. Để tìm được một cụm từ, ta đóng mở ngoặc kép ở đầu và cuối cụm từ đó để tạo thành một cụm từ. Cụm từ đảm bảo rằng NetNam Search Engine sẽ tìm được các từ đúng như thế (vị trí, thứ tự, không có từ chen giữa ), chứ không phải là tìm được riêng từng từ một. Hệ thống chấm câu NetNam Search Engine sẽ bỏ qua hệ thống chấm câu trừ trườn g hợp phải thể hiện hệ thống chấm câu đó là một dấu chia cách giữa các từ. Đặt hệ thống chấm câu hoặc các ký tự đặc biệt giữa các từ, và giữa chúng không có dấu cách, cũng là một cách để tìm một cụm từ. Một ví dụ cho thấy hệ thống chấm câu rất hữu dụng trong việc tìm một cụm từ đó là trường hợp tìm số điện thoại. Ví dụ để tìm được một số điện thoại Lê Thuý Ngọc - 0012745 60 Đỗ Mỹ Nhung - 0012624
  69. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt 0903401357 ta gõ 09-0340-1357 thì sẽ dễ tìm hơn là gõ theo kiểu "09 0340 1357", mặc dù đây cũng là một cú pháp có thể chấp nhận được nhưng ít phổ biến. Các từ có dấu nối ở giữa như CD-ROM, cũng tự động làm thành một cụm từ do có dấ u gạch nối ở giữa. Tuy nhiên, thông thường, sử dụng dấu ngoặc kép để tìm một cụm từ là cách được khuyến khích dùng hơn là sử dụng hệ thống chấm câu, vì một số ký tự đặc biệt còn có nghĩa phụ:  Dấu + và - là những toán tử giúp lọc kết quả của một tìm kiếm đơn giản.  &, |, ~ và ! là những toán tử giúp lọc kết quả của một tìm kiếm nâng cao Phân biệt chữ thường/hoa Phân biệt dạng chữ là một loại tìm kiếm dựa vào loại chữ mà ta gõ yêu cầu tìm kiếm của mình vào.  Một yêu cầu bằng chữ thường sẽ có kết quả tìm kiếm không theo dạng chữ ta gõ vào. Ví dụ, nếu ta gõ chữ yết kiêu vào ô yêu cầu, NetNam Search Engine sẽ tìm tất cả các biến thể của từ yết kiêu, gồm có yết kiêu, Yết Kiêu, YếT KiÊU, v.v  Nếu yêu cầu có cả chữ hoa, thì kết quả tìm kiếm sẽ là tìm kiếm theo d ạng chữ. Ví dụ, nếu ta điền Yết Kiêu vào ô yêu cầu, NetNam Search Engine sẽ tìm tất cả các biến thể của Yết Kiêu chỉ với chữ đầu tiên là chữ hoa. Nó sẽ không trả về các văn bản có chữ YếT KiÊU hay yết kiêu. 2.1.3 Sử dụng từ khoá để lọc các tìm kiếm Cả giao diện của công cụ tìm kiếm đơn giản và nâng cao đều hỗ trợ việc sử dụng các từ khoá để hạn chế các tìm kiếm tới các trang đáp ứng tiêu chuẩn được định Lê Thuý Ngọc - 0012745 61 Đỗ Mỹ Nhung - 0012624
  70. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt rõ về nội dung và cấu trúc của một trang web. Sử dụng từ khoá, ta có thể tìm kiếm dựa vào URL hoặc một phần của một URL, hoặc dựa vào các liên kết, hình ảnh, văn bản, mã hoá của một trang web. Các từ khoá sẽ rất có ích trong trường hợp:  Tìm các trang trên một máy chủ nào đó hoặc trong một tên miền chỉ định  Tìm các trang có chứa các liên kết trỏ tới trang web của ta.  Tìm các trang có chứa một lớp Java applets. Tìm kiếm dựa vào từ khoá, gõ một yêu cầu bằng từ khoá:lệnh tìm kiếm Gõ từ khoá bằng chữ thường, sau đó là dấu hai chấm. Quy ước để tìm một cụm từ trong lệnh tìm kiếm sẽ giống với quy ước để tìm một cụm từ trong một yêu cầu bình thường: phương pháp thường được sử dụng nhất là cho cụm từ vào trong ngoặc kép. title:"thời trang" Từ khoá Chức năng applet:class Tìm các trang có chứa một ứng dụng nhỏ (applet) Java hoặc Java class Domain:domainname Tìm các trang có từ hoặc cụm từ trong tên miền của máy chủ web nơi có trang cần tìm. (Phần của tên máy chủ internet là tên miền) host:name Tìm các trang có từ hoặc cụm từ trong tên của máy chủ web, nơi có các trang cần tìm. image:filename Tìm các trang có chứa ảnh filename Lê Thuý Ngọc - 0012745 62 Đỗ Mỹ Nhung - 0012624
  71. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Bảng 5.5 : Bảng miêu tả các từ khoá sử dụng trong việc tìm kiếm. Các từ khoá url, host, domain, đều có một mục đích là tìm kiếm các URL dựa vào một phần URL, hoặc dựa vào tên máy chủ hoặc t ên miền nơi có các trang web cần tìm. Các từ khoá link và anchor cũng tương tự như khi chúng tìm kiếm thông tin về liên kết. Từ khóa link tìm các văn bản trong một URL là đích của một liên kết (ví dụ, trong khi từ khoá anchor lại tìm các văn bản hiện tại của một siêu liên kết khi người dùng nhìn thấy nó trên một trang web (ví dụ, click here). Thẻ title sẽ tìm kiếm nội dung tiêu đề của một tài liệu. Từ khoá tiêu đề sẽ giới hạnviệc tìm kiếm tới văn bản mà tác giả của tài liệu đã mã hoá như một phần của thẻ . Tiêu đề là cụm từ sẽ xuất hiện trong đầu đề cửa sổ trong trình duyệt web. Từ khoá tiêu đề có thể sẽ là một cách tốt để giới hạn tìm kiếm chỉ tới các trang về một chủ đề, gồm các trang được đặt tiêu đề một cách thông minh. Tuy nhiên với các trang mà người lập nên không quan tâm đến tiêu đề trang web hoặc đặt tên kém thì cách tìm này không dùng được. Hơn nữa, hệ thống tìm kiếm của NetNam có thể cấu hình để nhận biết các thuộc tính phụ khác của tài liệu có các thẻ HTML M ETA do người dùng quy định. Lê Thuý Ngọc - 0012745 63 Đỗ Mỹ Nhung - 0012624
  72. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Điều kiện Định nghĩa url: Tìm tất cả các trang có các từ trong URL. host:netnam.vn Thoả mãn tất cả các trang có host:netnam.vn trong tên máy chủ web. domain:org.vn Thoả mãn tất cả các trang có tên miền org.vn trong tên máy chủ của máy chủ web. image:about.jpg Thoả mãn tất các trang có một thẻ hình ảnh liên quan tới image:about.jpg anchor:"click here" Thoả mãn tất cả các trang với cụm từ click here trong đoạn văn bản của một liên kết hoặc một thẻ anchor ( ) khác. link: Thoả mãn tất cả các trang có ít nhất một ml liên kết tới một trang có URL link: Chỉ tìm các trang có các liên kết tới URL ml chỉ định. Lê Thuý Ngọc - 0012745 64 Đỗ Mỹ Nhung - 0012624
  73. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt title:"NetNam Lifestyle" Thoả mãn các trang có cụm từ NetNam Lifestyle trong tiêu đề applet:flower Thoả mãn các trang chứa Java applet có tên gọi flower. Bảng 5.6 : Ví dụ tìm kiếm thông tin của Netnam 2.2 Vinaseek ([IV.11]) Vinaseek được phát triển từ năm 1997 theo mô hình của các search engine như Google, AltaVista, bổ sung khả năng tìm kiếm chính xác theo từ khoá cho Tiếng Việt, theo mọi bảng mã (TCVN3, VNi, TVCN-6909, ViQR ), theo mọi định dạng tài liệu văn bản (html, xml, rtf, word, pdf, PostScript ), theo mọi cách bỏ dấu khác nhau (“hoà” hay “hòa”), tìm kiếm hình ảnh và âm thanh, tìm kiếm gần đúng, tìm kiếm mờ (fuzzy search), tìm kiếm đồng âm và đồng nghĩa, đang lưu trữ chỉ mục và toàn văn của tất cả các trang Web Tiếng Việt trên internet (ước chừng 10 triệu văn bản), và nhận được hàng trăm ngàn lượt truy cập mỗi ngày. Cú pháp tìm kiếm của Vinaseek tương tự như Netnam về tìm kiếm từ, cụm từ, cách phân biệt hoa thường nhưng khác về : Hệ thống chấm câu bao gồm : +, -, khoảng trắng, Toán tử : AND, OR, NOT Field : link:, site:, url:, title: Điểm qua một vài tính năng nổi bật của Vinaseek ta có thể liệt kê như sau : Lê Thuý Ngọc - 0012745 65 Đỗ Mỹ Nhung - 0012624
  74. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt  Tốc độ tìm kiếm nhanh và chính xác và hiển thị kết quả đầy đủ.  Hỗ trợ toàn bộ các bảng mã Tiếng Việt cả trong nước và ngoài nước.  Số lượng đánh index khoảng 10 triệu trang và liên tục được cập nhật.  Cung cấp đầy đủ các tính năng tìm kiếm nâng cao với khả năng hiểu chính xác tiếng Việt.  Cho phép thực hiện các yêu cầu tìm kiếm phức tạp dạng tổ hợp một cách thông minh, hiệu quả  Có thể đặt ô tìm kiếm Vinaseek tại các website trong và ngoài nước một cách dễ dàng. Ô tìm kiếm Vinaseek hiện đang được đặt trên 40 trang web tiếng Việt hàng đầu trong và ngoài nước.  Dịch vụ Vinaseek có thể được tối ưu cho các trang web và mạng intranet của khách hàng làm công cụ tìm kiếm nội tại. Lê Thuý Ngọc - 0012745 66 Đỗ Mỹ Nhung - 0012624
  75. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Phần 2 : THIẾT KẾ VÀ CÀI ĐẶT  Ngôn ngữ lập trình : Java, HTML  Công cụ lập trình : JBuilder X, Microsoft Fontpage  Web Server : Resin  Hệ quản trị CSDL : Mircrosoft SQL Server 2000 Chương 6: THIẾT KẾ DỮ LIỆU Khi thiết kế hệ thống tìm kiếm thông tin vấn đề khó khăn nhất phải đối mặt là tổ chức cấu trúc dữ liệu . Vì khối lượng dữ liệu phải lưu trữ của hệ thống tìm kiếm thông tin là rất lớn, và khối lượng yêu cầu tìm kiếm phải xử lý cũng rất lớn (trên môi trường Web) nên cấu trúc dữ liệu phải được tổ chức tối ưu cho việc đáp ứng (về thời gian) đối với yêu cầu tìm kiếm của người sử dụng. Dữ liệu của hệ thống được xây dựng dựa trên mô hình vector, sử dụng phương pháp tập tin nghịch đảo 1. Cơ sở dữ liệu trong SQL CSDL trong SQL server phục vụ cho toàn bộ hệ thống gồm bảng Url : chứa các thông tin cần thiết cho ứng dụng về 1 URL. Bảng Tên thuộc Ý nghĩa Kiểu dữ liệu Miền giá trị Ghi chú Lê Thuý Ngọc - 0012745 67 Đỗ Mỹ Nhung - 0012624
  76. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt UrlSTT tính 1 Depth Độ sâu Integer 0 : đây là của StartURL FromURL 2 LastModified Ngày cập Bigint nhật nội dung URL gần nhất 3 ContentLength Kích Bigint thước trang web mà URL chỉ tới 4 Status Trạng thái Integer UNDOWNLOAD URL của URL chưa được download GOOD URL đã được download về Lê Thuý Ngọc - 0012745 68 Đỗ Mỹ Nhung - 0012624
  77. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt BROKEN URL bị hỏng trong khi kết nối với server GOOD- URL đã INDEXING download về và đang được lập chỉ mục BROKEN- URL INDEXING đang được lập chỉ mục nhưng bị hỏng liên kết 5 Title Tiêu đề Varchar(255) của trang web mà URL chỉ Lê Thuý Ngọc - 0012745 69 Đỗ Mỹ Nhung - 0012624
  78. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt tới 6 ContentType Cho biết Varchar(50) nội dung của URL thuộc dạng nào 7 UrlId Định Bigint Khóa danh của chính URL 8 UrlName Địa chỉ Varchar(255) Duy nhất của 1 URL 9 OutputPath Tên file Varchar(255) download về 10 RootId Định Bigint danh của StartURL Bảng 6.1 : Bảng URL Lê Thuý Ngọc - 0012745 70 Đỗ Mỹ Nhung - 0012624
  79. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt 2. Hệ thống tập tin Do hệ thống dùng Webserver là Resin nên toàn bộ cơ sở dữ liệu được lưu trong thư mục làm việc của Resin “\doc\se\working”. Ngoài dữ liệu được lưu trữ trong Hệ quản trị Cơ sở dữ liệu SQL Server 2000, ứng dụng còn có hệ thống file như sau: “Index.txt”: chính là từ điển chỉ mục, chứa thông tin về một mục từ như trọng số, số tài liệu có chứa mục từ này, là từ tiếng Anh hay tiếng Việt, trang bắt đầu và trang kết thúc trong tập tin nghịch đảo, và sẽ được trình bày cụ thể ở phần dưới. “Inverse.dat”: tập tin nghịch đảo, chứa các thông tin về các tài liệu và trọng số của các mục từ trong tài liệu đó, xem cụ thể trong phần tập tin nghịch đảo ở phần dưới. “UnicodetoUTF8.txt”: font chữ Unicode. Lê Thuý Ngọc - 0012745 71 Đỗ Mỹ Nhung - 0012624
  80. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Chương 7: THU THẬP THÔNG TIN 1. Cấu trúc dữ liệu Với mong muốn không chỉ đảm bảo được các nhiệm vụ của web robot mà còn giúp cho quản trị chủ động hơn nữa trong công việc của mình, module web robot sẽ hỗ trợ những chức năng sau :  URL bắt đầu (StartURL)  Định độ sâu liên kết  Các tuỳ chọn khi phân tích một URL : cùng site, cùng thư mục gốc, khác site.  Project  Mỗi project có thể có nhiều StartURL. Các project khác nhau có thể có cùng một / nhiều StartURL.  Chỉ phân tích URL để tạo CSDL hoặc download file.  Download vớI 2 tuỳ chọn.  Quy định các dạng và kích thước file cần download.  Không quy định các dạng và kích thước file cần download.  Tạm dừng 1 StartURL để xử lý 1 project khác hoặc 1 StartURL khác cùng project. Lê Thuý Ngọc - 0012745 72 Đỗ Mỹ Nhung - 0012624
  81. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt  Hệ thống  Định số spider hoạt động đồng thờI, thờI gian đợI giữa 2 lần truy xuất server liên tiếp.  Định số connection ban đầu, thờI gian đợI được cấp tài nguyên, số lần truy xuất CSDL khi hệ thống bận.  Định chu kỳ lưu thông tin một project. Nhằm đáp ứng những chức năng đã nêu ra, hệ thống thu thập thông tin sẽ được bổ sung thêm các cấu trúc dữ liệu như : 1.1 Cấu trúc UrlInfo UrlInfo là ánh xạ của bảng URL trong CSDL. Ngoài những thuộc tính kể trên, UrlInfo còn có các thuộc tính : STT Tên thuộc tính Ý nghĩa Kiểu dữ Miền giá Ghi chú liệu trị 1 Depth Độ sâu của URL Integer 2 ErrorCode Mã lỗI truy xuất integer 0 Không có lỗI CSDL 1 SQLException 3 RootId Định danh của Long URL liên kết tới Lê Thuý Ngọc - 0012745 73 Đỗ Mỹ Nhung - 0012624
  82. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt nó Bảng 7.1 : Cấu trúc URLInfo 1.2 Cấu trúc StartUrlInfo STT Tên thuộc tính Ý nghĩa Kiểu dữ Miền giá Ghi chú liệu trị 1 Alias Tên khác của String URL 2 Account Tên để truy cập String URL 3 MaxDepth Độ sâu lớn nhất Integer của StartURL 4 ProcessStatus Trạng thái xử lý Integer NONE Chưa được của StartURL xử lý BEING Đang xử lý DONE Đã xử lý 5 Password Password truy String cập StartURL Bảng 7.2 : Cấu trúc StartURLInfo Lê Thuý Ngọc - 0012745 74 Đỗ Mỹ Nhung - 0012624
  83. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt 1.3 Cấu trúc FileRetrieval STT Tên thuộc tính Ý nghĩa Kiểu dữ Miền giá Ghi chú liệu trị 1 Description Miêu tả dạng String file cần lấy 2 Extensions Danh sách các String đuôi file cần lấy 3 MaxSize Kích thước file Integer lớn nhất 4 MinSize Kích thước file nhỏ nhất Bảng 7.3 : Cấu trúc FileRetrieval 1.4 Cấu trúc ProjectInfo STT Tên thuộc tính Ý nghĩa Kiểu dữ liệu Miền Ghi chú giá trị Lê Thuý Ngọc - 0012745 75 Đỗ Mỹ Nhung - 0012624
  84. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt 1 ConnDBTimes Số lần truy Integer xuất CSDL cho mỗI thao tác thêm, xoá, sửa 2 LastUpdate Ngày cập Long nhật project gần nhất 3 HasRun Project đã Boolean được thực thi lần nào chưa 4 NumSpiders Số spider Integer dùng cho project 5 NumResource Số kết nối Integer ban đầu của project 6 PrjName Tên project String Duy nhất Lê Thuý Ngọc - 0012745 76 Đỗ Mỹ Nhung - 0012624
  85. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt 7 SpiderTimeout Thời gian Long delay giữa 2 lần truy xuất liên tiếp vào server 8 StartUrl Danh sách StartUrlVector các StartURL 9 ResourceTimeout Thời gian Long delay để được cấp phát tài nguyên 10 RetrievableExt Những đuôi FileRetrievalVector file cần xử lý 11 Outputpath Tên file chứa String thông tin project lưu trên đĩa Lê Thuý Ngọc - 0012745 77 Đỗ Mỹ Nhung - 0012624
  86. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt 12 UpdatingMode Kiểu cập Integer 21 giá trị nhật các StartURL của project Bảng 7.4 : Cấu trúc ProjectInfo StartUrlVector là một vector mà mỗi phần tử là một biến cấu trúc kiểu StartUrlInfo. Tương tự FileRetrievalVector cũng là một vector mà mỗi phần tử là một biến cấu trúc kiểu FileRetrieval. 2. Xử lý của web robot Thiết kế module phải thoả các yêu cầu sau :  Đảm bảo vai trò của web robot trong hệ thống : tìm kiếm liên kết, thu thập thông tin, tạo và duy trì cơ sở dữ liệu.  Không ảnh hưởng đến hoạt động của các module khác. Nhìn chung quy trình hoạt động của web robot đều giống nhau. Tuy nhiên, các ứng dụng hỗ trợ những tính năng khác nhau sẽ có sự thay đổi về quy trình hoạt động. Các bước xử lý : (1) Khởi tạo. (2) Nếu vẫn còn URL chưa xử lý và user không chọn chức năng tạm dừng (pause) Lê Thuý Ngọc - 0012745 78 Đỗ Mỹ Nhung - 0012624
  87. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Qua (3) ngược lại qua (14) (3) Lấy URL đầu tiên. Nếu lấy được qua (4) ngược lại quay lại (2) (4) Lưu thông tin cũ (5) Kết nối vớI server Nếu kết nối được qua (6 ) ngược lại Thêm URL vào danh sách hỏng Cập nhật trạng thái của URL trong CSDL = BROKEN Đánh dấu URL đã xử lý trong CSDL. Nếu truy xuất CSDL không được Đưa URL này trở lại hàng đợi. Quay lại (2) (6) Huỷ URL ra khỏi danh sách hỏng nếu URL nằm trong danh sách đó. (7) So sánh với thông tin cũ Nếu giống qua (8) ngược lại Cập nhật thông tin mới (8) Đánh dấu URL tốt ( trạng thái = GOOD ) Lê Thuý Ngọc - 0012745 79 Đỗ Mỹ Nhung - 0012624
  88. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt (9) Thêm URL vào danh sách đã xử lý. (10) Đây là file HTML ? Nếu cần phân tích lại thì tiến hành phân tích. (11) Thoả yêu cầu download của quản trị ? Nếu thoả Download Trả kết quả về để hiện thị thông tin đã xử lý Qua (12) ngược lại Quay lại (2) (12) Ghi nhận thông tin mới xuống CSDL gồm : Cập nhật thông tin mới cho URL Đánh dấu URL đã được xử lý. Nếu truy xuất CSDL không được Gán lại thông tin cũ cho URL Xóa URL khỏi danh sách đã xử lý. Thêm URL vào lại hàng đợi Quay lại (2) (13) Đủ số spider chưa ? Nếu chưa Tạo thêm Lê Thuý Ngọc - 0012745 80 Đỗ Mỹ Nhung - 0012624
  89. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt Tạm dừng Quay lại (2) (14) Đã hết URL chưa ? Nếu chưa (ứng dụng dừng do user chọn pause) Qua (15) ngược lại Đánh dấu StartURL đã thực hiên xong (processStatus = DONE) (15) Kết thúc. Giải thích thêm về thuật toán :  Khi phân tích file HTML, ta dò tìm các liên kết và những thông tin cần thiết để cập nhật bảng URL trong CSDL. Những liên kết tìm được muốn vào hàng đợi trước tiên nó phải là URL chưa được xử lý lần nào và không có trong danh sách đang đợi xử lý, sau đó phải qua tiền xử lý. Thuật toán chỉ xem xét danh sách đợi và danh sách đã thực hiện nhưng không xét danh sách bị hỏng nhằm tạo điều kiện để sửa chữa URL hỏng nếu có 1 URL khác liên kết tới nó. Trong trường hợp không có URL nào liên kết tới nó, quản trị vẫn biết nó bị hỏng do trạng thái này đã được ghi nhận trước đó.  Số spider tạo thêm = min ( số liên kết hiện có, số spider theo yêu cầu ). Ta luôn có lượng spider vừa đủ dùng, nhờ vậy mà tránh lãng phí tài Lê Thuý Ngọc - 0012745 81 Đỗ Mỹ Nhung - 0012624
  90. Tìm hiểu về Search Engine và xây dựng ứng dụng mi nh hoạ cho Search Engine tiếng Việt nguyên hệ thống do mỗi spider cần khá nhiều tài nguyên cho hoạt động của mình. Các bước tiền xử lý 1 URL tìm được : (1) Tuỳ theo yêu cầu của quản trị mà ta kiểm tra URL mới, ví dụ : cùng thư mục gốc, cùng site, Nếu thoả yêu cầu Qua (2) ngược lại Trả về thông tin cho biết không tiếp tục xét URL này. (2) Kiểm tra độ sâu liên kết Nếu chưa vượt quá giới hạn Qua (3) ngược lại Trả về thông tin cho biết không tiếp tục xét URL này. (3) Kiểm tra dạng file (content type)của URL có nằm trong danh sách các dạng file cần download hay không ? Nếu có Trả về thông tin cho biết tiếp tục xét URL này. ngược lại Trả về thông tin cho biết không tiếp tục xét URL này. Lê Thuý Ngọc - 0012745 82 Đỗ Mỹ Nhung - 0012624