Đề tài Công cụ tìm kiếm search engine

Tr­êng ®¹i häc s­ ph¹m hµ néi Khoa C«ng nghÖ th«ng tin -----˜&™----- BÁO CÁO NGHIÊN CỨU KHOA HỌC Đề tài CÔNG CỤ TÌM KIẾM SEARCH ENGINE Gi¶ng viªn h­íng dÉn : TS. TrÇn C«ng Nh­îng Th.S NguyÔn ThÞ HuyÒn Sinh viªn thùc hiÖn : NguyÔn ThÞ Kim Liªn Kho¸ : K54 B Hµ néi, th¸ng 4 – 2008 LỜI MỞ ĐẦU Ngày nay, với sự ra đời của mạng Internet và sự phát triển nhanh chóng, vượt bậc của mạng truyền thông, khối lượng rất lớn các thông tin được cập nhật và đưa lên mạng. Đa số các thông tin là các tập tin phi cấu trúc, nằm rải rác ở nhiều nơi. Câu hỏi đặt ra làm thế nào để tìm được đúng thông tin một cách nhanh chóng và hiệu quả nhất. Để đáp ứng yêu cầu đó, đã có rất nhiều bộ công cụ tìm kiếm thông tin trên mạng ra đời như Google, Yahoo, Altavista,…Và để hiểu được cơ chế hoạt động của những bộ công cụ này, tôi đã lựa chọn đề tài “Công cụ tìm kiếm”. Thông tin được lưu dưới dạng cơ sở dữ liệu thường là có cấu trúc nên tìm kiếm rất nhanh vì hầu hết đã được lập chỉ mục. Tuy nhiên, thông tin rất nhiều và đa dạng được đề cập ở đây là thông tin dưới dạng phi cấu trúc, thách thức đối với người dùng tin. Thông tin dưới dạng phi cấu trúc muốn tìm nhanh trong thời gian ngắn phải được sắp xếp lại để có thể tìm và sử dụng được, để biến chúng thành thông tin có giá trị cho mỗi người. Như đã đề cập ở trên hiện này có rất nhiều bộ công cụ nổi tiếng, nhứ Google đã cung cấp mộ công cụ tìm kiếm rất hoàn hảo.Tại sao lại phải nỗ lực để làm việc này? Câu trả lời là chúng ta vẫn phải nghiên cứu, tìm hiểu để khám phá và hiểu biết sâu hơn về cách thu thập, lưu trữ, biểu diễn, tổ chức tìm kiếm thông tin hiệu quả và nhanh nhất. Tìm kiếm Tiếng Việt trên Web vẫn đang là vấn đề khá mới đối với Việt Nam. Nên trong quá trình tìm hiểu lý thuyết tôi cũng đặc biệt chú trọng hơn. Luận văn này có cấu trúc: Phần giới thiệu, phần nội dung gồm 3 chương, phần kết luận và tài liệu tham khảo. Chương 1: Giới thiệu về công cụ tìm kiếm (Search Engine). Chương này giới thiệu về khái niệm và các mô hình truyển thống và các mô hình tìm kiếm thông tin trên mạng. Chương 2: Chương này trình bày về các công cụ cơ bản trong bộ tìm kiếm thông tin như bộ thu thập thông tin, bộ lập chỉ mục, bộ sắp xếp,… Chương 3: Thiết kế và cài đặt. Nội dung chương này trình bày cách thiết kế, tổ chức,… trong bộ tìm kiếm thông tin. Chương 1: GIỚI THIỆU VỀ CÔNG CỤ TÌM KIẾM (SEARCH ENGINE) Tóm tắt nội dung chương: Khái niệm công cụ tìm kiếm. Mô hình bộ công cụ tìm kiếm. Các bộ phận cấu thành hệ thống search engine. Một số Search engine thông dụng trên Thế giới và Việt Nam. Khái quát về công cụ tìm kiếm thông tin Khái niệm công cụ tìm kiếm thông tin Thuật ngữ tìm kiếm thông tin xuất hiện từ khá sớm, thông tin ở đây có thể là dạng văn bản, hình ảnh hoặc âm thanh,…mà phổ biến nhất là dạng văn bản. Thuật ngữ Search engine là một công cụ phần mềm nhằm tìm ra các trang trên mạng dựa vào các thông tin mà nó có. Dữ lượng thông tin của search engine thực chất là một loại cở sở dữ liệu (database) cực lớn. Công cụ này tìm các tài liệu dưạ trên các từ khoá (keyword) và trả về một danh mục cuả các trang có chứa từ khoá. Một hệ thống tìm kiếm thông tin là chương trình phần mềm, dùng để lưu trữ và quản lý thông tin trong các tài liệu. Hệ thống này sẽ giúp người sử dụng tìm kiếm thông tin mà họ quan tâm. Một số tài liệu tìm thấy thỏa mãn yêu cầu của người dùng gòi là tài liệu phù hợp hay các tài liệu liên quan. Về cơ bản có 3 loại công cụ tìm kiếm: một số được vận hành bởi các crawler, hoặc các spider; một số được vận hành bởi Human submissions, và một số là sự kết hợp của hai loại trên. Các công cụ dựa trên Crawler gửi các crawler, hoặc là spider ra ngoài. Các crawler này sẽ đến một trang web, đọc các thông tin thực sự của trang web đó, đọc các meta tag của trang web và nó cũng đến tận các link mà trang web đó link đến. Các crawler này sẽ gửi tất cả các thông tin về trung tâm lưu trữ để liệt kê các dư liệu ra. Crawler sẽ quay trở lại trang web đó một cách định kỳ để cập nhập sự thay đổi trên trang web đó, và chu kỳ cập nhật này là do ngưòi quản trị của công cụ tìm kiếm đó đặt cấu hình. Các công cụ tìm kiếm Human-powered thì lại tin vào các thông tin được liệt kê ra bởi người quản trị trang web, rồi sau đó các thông tin này sẽ được liệt kê và đưa vào bảng liệt kê. Chỉ những thông tin được đưa ra bởi nhà quản trị web mới được đưa vào bảng liệt kê. Mô hình bộ công cụ tìm kiếm Biểu diễn Truy vấn thông tin Bài toán thông tin Văn bản Biểu diễn Văn bản đã chỉ số So sánh Phản hồi Các văn bản được tìm kiếm Tìm kiếm thông tin nói chung là giải quyết các vấn đề như: biểu diễn, lưu trữ, tổ chức và truy cập đến các mục thông tin. Việc tổ chức và biểu diễn thông tin giúp người sử dụng dễ dàng truy cập thông tin mà mình quan tâm. Nhưng để mô tả các thông tin đó không phải là điều dễ dàng. Do vậy, hệ thống tìm kiếm thông tin bao gồm quá trình cơ bản sau: Biểu diễn nội dung các tài liệu, biểu diễn yêu cầu người dùng và so sánh hai biểu diễn này. Hình 1: Quy trình tìm kiếm Quy trình biểu diễn tài liệu thường gọi là quá trình chỉ số hóa. Quá trình này có thể lưu trữ thực sự các tài liệu trong hệ thống nhưng thường chỉ lưu một phần tài liệu, chẳng hạn như phần tiêu đề, phần tóm tắt. Quá trình biểu diễn yêu cầu của người dùng gọi là quá trình truy vấn. Truy vấn biểu thị sự tương tác giữa hệ thống và người sử dụng. Việc so sánh truy vấn với tài liệu cũng được gọi là quá trình đối sánh và cho kết quả là một danh sách các tài liệu được sắp xếp theo thứ tự mức độ liên quan với truy vấn. Rõ ràng, để mô tả thông tin yêu cầu một cách đầy đủ, người sử dụng không thể trực tiếp yêu cầu thông tin sử dụng các giao diện hiện thời của hệ thống tìm kiếm. Thay vì người sử dụng đầu tiên phải chuyển đổi thông tin yêu cầu này thành một truy vấn mà có thể được xử lý bởi hệ thống tìm kiếm (hoặc hệ thống thu hồi thông tin (Information Retrieval - IR)). Thông thường, phép chuyển đổi này tạo ra một tập hợp các từ khoá (hoặc các term chỉ số) mô tả khái quát yêu cầu của người sử dụng. Như vậy, việc tìm kiếm các tài liệu dựa trên nội dung thực sự của văn bản mà không phụ thuộc vào các từ khoá gắn với văn bản đó. Các công cụ tìm kiếm văn bản nổi tiếng hiện nay như Google, Altavista, Yahoo,…là những hệ tìm kiếm đưa ra danh sách các văn bản theo độ quan trọng của câu hỏi đưa vào. Để xây dựng một hệ tìm kiếm văn bản có hiệu quả cao, trước hết các văn bản và truy vấn ở dạng ngôn ngữ tự nhiên phải được tiền xử lý và chuẩn hoá. Sau đây là hai mô hình chi tiết cho bộ công cụ tìm kiếm thông tin truyền thống và bộ công cụ tìm kiếm thông tin trên mạng. Mô hình bộ công cụ tìm kiếm truyền thống Vào những năm 70, khi các mô hình tìm kiếm thông tin chủ yếu được xử lý với các truy vấn không có cấu trúc. Nguyên tắc hoạt động của hệ thống truy vấn tự động chỉ số hóa và thiết lập công thức truy vấn, kết quả đưa ra là một biểu diễn có ý nghĩa gần với ý nghĩa thực của văn bản, loại bỏ các từ không theo quy tắc trong ngôn ngữ tự nhiên đến mức có thể. Bộ công cụ tìm kiếm trên mạng Do các trang Web phân tán ở khắp mọi nơi nên điều đầu tiên là chúng ta phải thu thập được tất cả các dữ liệu Web có liên quan tới truy vấn, lập chỉ mục, sau đó thực hiện tìm kiếm để đưa ra tập kết quả có liên quan tới nội dung truy xuất. Mô hình này rất phức tạp bởi kho dữ liệu cực lớn với tỷ lệ thay đổi nội dung cao. Các bộ phận cấu thành hệ thống search engine Bộ thu thập thông tin Cơ sở dữ liệu cuả các search engine được cập nhật hoá bởi các chương trình đặc biệt thường gọi là "robot", "spider" hay "Webcrawler". Các chương trình này sẽ tự động dò tìm và phân tích từ những trang có sẵn trong cơ sở dữ liệu để kiếm ra các liên kết (links) từ các trang và trở lại bổ xung dữ liệu cho các search engine sau khi phân tích. 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. 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ả. Lập chỉ mục là giai đoạn phân tích tài liệu (document) để xác định các chỉ mục biểu diễn nội dung của tài liệu. 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. 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 và trả về những tài liệu thoả yêu cầu của user. Bộ Query Engine Bộ công cụ truy vấn có nhiệm vụ nhận và tìm kiếm các yêu cầu của người sử dụng, Bộ công cụ này sẽ dựa vào bảng chỉ mục và các kho lưu trữ. Bởi kích thước của web rất lớn, thêm nữa khi sử dụng chỉ đưa vào một hay hai từ khóa sau đó sẽ nhận được tập kết quả. Do đó phải có một modul sắp xếp kết quả theo thứ tự sao cho nó gần với nội dung đang cần tìm nhất. Sắp xếp Đây là một modul có chức năng sàng lọc thông tin từ hàng triệu trang tương tự nhau để sắp xếp vị trí từng trang sao cho phù hợp nhất. Một số Search engine thông dụng trên Thế giới và Việt Nam Một số search engine trên Thế Giới 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: - Trang kiểu Spider: Google: www.google.com Ask Jeeves www.ask.com/ Teoma: www.teoma.com/ Altavista: www.altavista.com/ Excite: www.excite.com/ Gigablast: www.gigablast.com/ lycos: www.lycos.co.uk/ - Kiểu Meta: Dog Pile: www.dogpile.com tìm trên LookSmart, GoTo.com, Thunderstone, Yahoo!, Open Directory, About.com, Direct Hit, Lycos, and AltaVista. Meta Find: www.metafind.com tìm trên Meta Find Excite, AltaVista, Infoseek, and WebCrawler Meta crawlwr: www.metacrawler.com tìm trên Lycos, WebCrawler, Infoseek, Excite, Thunderstone, AltaVista, GoTo, và Yahoo. Vivisimo: tìm trên Netscape, MSN, Lycos,LookSmart. - Kiểu Directory: Yahoo: www.yahoo.com Infomine: infomine.ucr.edu/ Academic Info: www.academicinfo.net About: www.about.com Một số search engine thông dụng ở Việt Nam - Netnam 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. - Vinaseek VinaSeek là một S.E cho các web site tiếng Việt của Công ty Công nghệ Tin học Tinh Vân. 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. Chương 2: CÁC CÔNG CỤ CƠ BẢN Tóm tắt nội dung chương: Thu hồi trang web. Bộ lập chỉ mục. Bộ tìm kiếm thông tin. Sắp xếp và phân tích liên kết. Thu hồi trang Web Module Robot có nhiệm vụ thu hồi các trang web để hỗ trợ cho các module sau. Module Robot có đầu vào là một tập các giá trị khởi tạo URL, chúng được thu hồi và sắp xếp theo thứ tự ưu tiên nào đó. Robot lấy một giá trị URL, tải trang tương ứng xuống rồi trích tất cả giá trị URL nằm trong trang, đặt vào kho lưu trữ, quá trình này được lập đi lập lại cho tới khi Robot quyết định dừng. Hoạt động của Robot thường được sử dụng vào những mục đích sau: Phân tích, thống kê 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, … Duy trì siêu liên kết 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 khi 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. Á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 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. Phát hiện nguồn tài nguyên 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. Các chiến thuật thu thập dữ liệu Trước khi các trang web được đánh chỉ mục, tất cả các trang web phải được lấy về máy của robot. Để lấy được tất cả các trang web, robot phải có chiến thuật. Từ một số trang web có sẵn, robot lọc ra danh sách các liên kết, rồi từ đó dò tìm các trang khác. 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. Những vấn đề cần lưu ý của web robot - 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. - Quá tải mạng và server. - Sự cập nhật quá mức. BỘ LẬP CHỈ MỤC Khái quát về hệ thống lập chỉ mục Lập chỉ mục tài liệu, hiểu một cách đơn giản, là việc sắp xếp các tài liệu nhằm đáp ứng nhanh chúng yêu cầu tìm kiếm thông tin của người sử dụng. Hiệu quả của một phương pháp lập chỉ mục được đánh giá qua không gian lưu trữ mà nó đòi hỏi và thời gian cần thiết để thực hiện việc tìm kiếm thông tin. Các phương pháp lập chỉ mục giữ vai trò quan trọng trong việc xây dựng một hệ tìm kiếm thông tin hiệu quả. 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. Tổng quan về phương pháp lập chỉ mục Module lập chỉ mục xây dựng hai chỉ mục cơ bản: Chỉ mục cho nội dung (cho văn bản) và chỉ mục cho liên kết. Phương pháp lập chỉ mục cho nội dung Phương pháp lập chỉ mục này 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. 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 đó. Đặ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ố 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. 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. Các cấu trúc lưu chỉ mục - Phương pháp chia sẻ block Trong phương pháp này nhiều từ có thể dùng chung một block, có kích thước mặc định là 32KB, để chứa các vị trí xuất hiện của chúng trong tài liệu. Từng block lại được chia thành nhiều slot có kích thước khác nhau, mỗi slot chứa các vị trí xuất hiện của một từ. Tuỳ thuộc vào độ lớn của dữ liệu vị trí này mà kích thước của mỗi slot sẽ được điều chỉnh phù hợp. Tuy nhiên, kích thước này luôn luôn là bội số của 8 (tính theo byte) nhưng không vượt quá 32KB. Phương pháp chia sẻ block được sử dụng khi kích thước được dùng để lưu trữ vị trí xuất hiện trong tài liệu cho một từ không quá 32KB (nếu lớn hơn, sẽ dùng cây B+Tree). Công việc quan trọng hàng đầu khi lập chỉ mục tài liệu là tìm ra phương pháp lưu trữ để thể hiện mối quan hệ giữa từ và vị trí xuất hiện của nó trong tài liệu. Chất lượng của công việc này thể hiện chất lượng của chỉ mục tài liệu. Trong phương pháp chia sẻ block, mối quan hệ giữa từ và vị trí xuất hiện của nó trong tài liệu được thể hiện theo sơ đồ. - Phương pháp sử dụng cây B+Tree. Khi sử dụng phương pháp B+Tree để lưu trữ vị trí xuất hiện của từ trong tài liệu, thì cũng tương tự như phương pháp chia sẻ block, mỗi từ trong file WRD sẽ có một trường trỏ đến một block trong file POS. Lúc này, mỗi block trong file POS là một nút gốc của cây B+Tree. Các nút cành của cây B+Tree được lưu trữ trong một file có tên là PND. Các nút lá của cây B+Tree được chứa trong một file có tên là PLF. File PLF cũng được chia ra thành các block có kích thước 4 KB, mỗi block này được xem như một nút lá. Dữ liệu về vị trí xuất hiện của từ trong tài liệu được lưu trữ tại nút lá này. Phương thức lưu trữ dữ liệu vị trí cũng được áp dụng như phương pháp chia sẻ block. Có một cải tiến đáng kể trong phương pháp sử dụng cây B+Tree, đó là sử dụng các cấu trúc pinpoint trong block dữ liệu của mỗi nút lá. Cơ chế hoạt động của pin-point cũng giống như cơ chế hoạt động của bảng băm (hash table), dùng để chia các vùng dữ liệu đó sắp xếp ra thành 8 khối, và pin-point có các con trỏ trỏ đến điểm đầu và điểm cuối của 8 khối dữ liệu này, nhằm tăng tốc độ khi tìm kiếm trên nút lá. Phương pháp lập chỉ mục cho liên kết Để xây dựng bảng chỉ mục cho liên kết thì các phần được thu hồi trên web được mô hình hóa như một đồ thị với các cạnh và các nút. Mỗi nút trong đồ thị tương ứng với một trang web, và mỗi cạnh có hướng từ A tới B diễn tả liên kết siêu văn bản trong trang A tới trang B. Bảng chỉ mục cho cấu trúc liên kết phải là một diễn mở rộng và hiệu quả của đồ thị này. Thông thường các thông tin cấu trúc này được sử dụng trong tìm kiếm các thông tin hàng xóm. Ví dụ, trang P, hãy tìm kiếm một tập các trang được P trở tới (liên kết đi ra) hoặc một tập các trang trỏ tới P (liên kết đi vào). Cấu trúc danh sách liền kề của đồ thị web đầu tiên và của đò thị web đã được đảo có thể cung cấp phép truy cập tới các thông tin hàng xóm một cách hiệu quả. Các thuộc tính cấu trúc của đồ thị web có thể được đưa ra một cách dễ dàng từ những thông tin cơ bản lưu trữ trong danh sách liền kề. Các đồ thị với hàng trăm hoặc thậm trí hàng nghìn nút có thể diễn tả một cách hiệu quả dưới bất kì cấu trúc dữ liệu đã biết nào. Tuy nhiên làm công việc đó đối với vài triệu nút là một thách thức về công nghệ. Lập chỉ mục tự động cho tài liệu Lập chỉ mục cho tài liệu tiếng Anh 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: 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ọng 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ể. 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ỏ. 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ố. Lập chỉ mục cho tài liệu tiếng Việt 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 : 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 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 để. Đặc điểm về từ trong tiếng Việt và việc tách từ - Đặc điểm về từ trong tiếng Việt: + Tiếng: + Từ: + Tách từ Giải quyết các vấn đề hiển thị của tiếng Việt (vấn đề chính tả) 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). 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 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. 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ừ 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ừ. 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. BỘ TÌM KIẾM THÔNG TIN – SEARCH ENGINE 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 Các phương thức tìm kiếm 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. * 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. Tìm theo ngữ nghĩa – Concept-based searching Tìm kiếm theo ngữ nghĩa là tìm đúng theo nghĩa mình mong muốn trong số những nghĩa của từ mình muốn truy vấn. Bên cạnh đó tìm kiếm theo ngữ nghĩa còn là tìm những từ có ngữ nghĩa liên quan chứ không đơn thuần là tìm chính xác nghĩa. Trong một số trường hợp tìm đúng nghĩa của từ sẽ có kết quả hạn chế và không có tính ứng dụng cao. Các chiến lược tìm kiếm 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. 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. 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. 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ừ có sau NOT (dấu -) 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 / ADJ Các từ cần tìm phải đứng cạnh nhau trong tài liệu 6 Dấu ( ) Thể hiện mức ưu tiên trong truy vấn 7 Dấu “ ” Khi muốn tìm nguyên văn của cụm từ 8 Dấu * Dấu này sẽ thay thế cho một dãy bất kì các kí tự (chữ, số, hay dấu). 9 Dấu ? Dùng thay cho một kí tự duy nhất nào đó Bảng 1 : Các từ khóa giúp tối ưu câu truy vấn Sắp xếp và phân tích liên kết Cấu trúc liên kết web cho ta những thông tin quan trọng và có thể hỗ trợ trong việc lọc và sắp xếp các trang web. Cụ thể, từ một liên kết A tới trang b cho ta biết trang B được sinh từ trang A. Một vài thuật toán đã được đề xuất để khai thác cấu trúc liên kết này – không chỉ cho việc tìm từ khóa mà còn cho cả những công việc khác như nhận dạng nhóm truyền thông trên web. Hiệu suất của thuật toán này cao hơn các thuật toán IR bời chúng sử dụng nhiều thông tin hơn. Sau đây là hai kỹ thuật dựa trên các cấu trúc liên kết – PageRank và HITS. PageRank là một mô hình sắp xếp toàn cục được sử dụng để sắp xếp các kết quả tìm kiếm, còn thuật toán HITS thì xác định một tập các trang hub và các trang authority đối với một truy vấn đã cho Phương pháp PageRank Page và Brin đưa ra một mô hình sắp xếp chung, được gọi là PageRank. - Tính PageRank đơn giản - Tính PageRank thực tế PageRank đơn giản chỉ được tính cho đồ thị liên kết mạnh. Trong khi đó, môi trường web thường không phải là một đồ thị liên kết mạnh. Cụ thể, đưa ra hai vấn đề: rank sinks, rank leads. Công thức PageRank có dạng: Trong đó: m: tổng số lượng các nút trong đồ thị Chú ý rằng công thức PageRank đơn giản là trường hợp đặc biệt khi d=1. - Các vấn đề trong tính toán Để cho bước lặp luỹ thừa được thực hiện, nó không chỉ cần hội tụ tới PageRank mà còn phải thực hiện rất ít bước lặp. Một cách lý thuyết, sự hội tụ các bước lặp luỹ thừa cho một ma trận phụ thuộc vào engine value gap (được định nghĩa như sự khác biệt giữa module của hai giá trị lớn nhất của ma trận đã cho). Page và Brin cho rằng điều này là đúng và bước lặp luỹ thừa hội tụ một cách nhan chóng (trong khoảng 100 buớc lặp). Cũng chú ý rằng chúng ta quan tâm tới thứ tự liên quan của các trang dựa vào PageRank (thứ tự này được sử dụng để sắp xếp các trang) hơn là giá trị thực của PageRank. Vì thế chúng ta có thể kết thúc bước lặp khi thứ tụ các trang vào độ hội tụ của PageRank nhanh hơn khi ta đi tính giá trị thực của PageRank. Phương pháp HITS Một thuật toán sắp xếp khác cũng dựa trên các mối liên kết, được goi là HITS (Hypertext Induced Topic Search). Thuật toán này đuợc đề xuất đầu tiên bởi Kleinberg. Thuật toán HITS Ý tưởng có bản của thuật toán HITS là xác định một đồ thị con của web và áp dụng sự phân tích liên kết trên đồ thị con này để xác định các authority và các hub với truy vấn đã cho. Đồ thị con này phụ thuộc vào truy vấn của người sử dụng. Sự lựa chọn đồ thị con (cụ thể khoảng vài nghìn trang) không chỉ tập trung vào việc liên kết trên hầu hết các phần liên quan trong web mà đồng thời cũng giảm số lượng công việc của pha tiếp theo (do việc chọn lựa đồ thị con và phân tích nó đều được thực hiện trong thời gian truye vấn nên nó quan trọng để hoàn thành chúng trong một thời ngắn). Các mô hình sắp xếp và đánh giá Mô hình Boolean Định nghĩa: Cho một mô hình Boolean, các term chỉ số đều được biểu diễn bởi các giá trị nhị phân w1,jÎ{0, 1}. Một truy vấn q là một biểu thức Boolean theo qui ước. Cho là véc tơ liên kết DNF với truy vấn q, lấy là thành phần liên kết nào đó của . Độ tương tự của tài liệu dj với truy vấn q được xác định: 1, nÕu $ | (Î)Ù("ki, (2.1) sim(dj,q) = 0, cßn l¹i Nếu sim(dj, q) = 1 thì mô hình Boolean dự đoán rằng tài liệu dj là phù hợp với truy vấn q (có thể là không). Còn lại, là không phù hợp. Mô hình Boolean cung cấp một cách nhìn khá trực quan, đơn giản và dễ hiểu cho người sử dụng của một hệ thống IR. Tuy nhiên, mô hình Boolean cũng có một số mặt hạn chế. Bởi chiến lược tìm kiếm của chúng dựa trên tiêu chuẩn quyết định nhị thức (một tài liệu được dự đoán chỉ trong hai khả năng là phù hợp hoặc không phù hợp) mà không có bất kỳ một khái niệm chia mức độ lựa chọn nào. Do vậy, mô hình Boolean không đưa ra danh sách các văn bản được sắp xếp theo mức độ liên quan đến yêu cầu của người dùng, dẫn đến việc mô hình này không thoả mãn các yêu cầu trong các hệ thống tìm kiếm văn bản hiện nay như các công cụ tìm kiếm web. Mô hình không gian véc tơ Ta nhận thấy rằng, khi biểu diễn văn bản và truy vấn dưới dạng các véc tơ thì tích vô hướng của hai véc tơ đó có thể được xem như là độ liên quan giữa văn bản và truy vấn mà chúng ta biểu diễn. Cụ thể, giả thiết tập tài liệu bao gồm n Term khác nhau. Khi đó văn bản và truy vấn sẽ được biểu diễn thành các véc tơ n chiều. Giả sử truy vấn và tài liệu lần lượt được biểu diễn thành các véc tơ Q và Dd như sau : Một cách đơn giản nhất ta gán bằng 1 nếu term thứ i trong từ điển có mặt trong truy vấn (hoặc tài liệu) và bằng 0 trong trường hợp còn lại. Độ liên quan giữa truy vấn và văn bản được tính theo công thức Một số hạn chế sau : Không thể hiện được tần suất xuất hiện của các Term trong mỗi văn bản. Không thể hiện được thuộc tính khan hiếm của một Term khi nó xuất hiện chỉ trong một số ít văn bản. Có sự phân biệt giữa độ dài các văn bản, cụ thể là những văn bản dài, chứa nhiều Term khác nhau được ưu tiên khi tính toán độ liên quan. Chương 3: THIẾT KẾ VÀ CÀI ĐẶT Modul lập chỉ mục. Modul tìm kiếm thong tin. TÀI LIỆU THAM KHẢO Website