- NGHIÊN CỨU CÁC PHƢƠNG PHÁP NÉN CHỈ SỐ TRONG CÁC HỆ THỐNG TÌM KIẾM. - Ngành: Công Nghệ Thông Tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104. - LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN. - KIẾN TRÚC CHUNG CỦA MÁY TÌM KIẾM. - THÀNH PHẦN CHỈ SỐ TRONG MÁY TÌM KIẾM. - 1.1 Khái niệm bộ công cụ tìm kiếm thông tin. - 1.1.1 Tổng quan về hệ thống tìm kiếm. - 1.1.2 Quy trình tìm kiếm thông tin. - 1.1.3 Một số vấn đề trong tìm kiếm thông tin. - 1.1.4 Cấu trúc điển hình của một máy tìm kiếm. - 10 1.2 Tập chỉ số trong máy tìm kiếm. - 1.2.1 Các bƣớc để xây dựng hệ thống tìm kiếm thông tin . - 1.2.2 Cấu trúc của bảng chỉ số ngƣợc. - 1.2.3 Chia bảng chỉ số. - 1.3 Tổng quan về phƣơng pháp lập chỉ số. - MỘT SỐ PHƢƠNG PHÁP NÉN CHỈ SỐ, NÉN CHỈ SỐ NGƢỢC TRONG MÁY TÌM KIẾM. - 2.1 Chỉ số ngƣợc. - 2.2 Phƣơng pháp nén chỉ số. - 2.3 Các phƣơng pháp nén chỉ số cập nhật. - Tìm hiểu các lớp đối tƣợng tìm kiếm. - 3.2 Lập chỉ số trong Lucene. - Các tiến trình lập chỉ số. - 3.2.4 Điều khiển tiến trình lập chỉ số. - 3.2.5 Tối ƣu hóa việc lập chỉ số. - 3.3 Tìm kiếm trên tập chỉ số. - 3.3.1 Tìm kiếm một thuật ngữ cụ thể. - 3.5 Định dạng chỉ số trong lucene. - 3.5.1 Cấu trúc chỉ số. - 3.5.2 Chỉ số ngƣợc. - Trong xã hội phát triển, thông tin thực sự trở thành nguồn tài nguyên quan trọng, nguồn của cải to lớn của xã hội. - Hệ thống càng phát triển tức là càng có nhiều yếu tố tạo thành mối quan hệ giữa chúng càng phức tạp do đó lƣợng thông tin càng phong phú. - Chính vì vậy mà ngày nay cùng với sự phát triển của Công nghệ Thông tin cũng nhƣ sự phát triển nhanh chóng của mạng máy tính toàn cầu và sự bùng nổ thông tin, các kho dữ liệu số đã đƣợc hình thành ở khắp mọi nơi và không ngừng gia tăng về dung lƣợng, nhƣng thông tin thì vẫn luôn là cần thiết thậm chí thiếu với họ. - Các kho dữ liệu này ẩn chứa một lƣợng thông tin vô cùng lớn. - Nhƣng vấn đề đặt ra là làm thế nào để “khai thác, tìm kiếm” tổng hợp kho thông tin đó để cho nó trở nên hiệu quả và có giá trị đối với ngƣời dùng. - Những thông tin này đƣợc lƣu trữ và biểu diễn ở rất nhiều dạng khác nhau nhƣ văn bản, âm thanh, hình ảnh vv. - có thể thấy khối lƣợng dữ liệu khổng lồ mà ngƣời sử dụng có thể truy xuất nếu không đƣợc tổ chức lƣu trữ tốt và kèm theo một phƣơng thức xử lý hiệu quả để có thể khai thác và tìm kiếm lƣợng thông tin trong đó thì chúng cũng chỉ là những thông tin không mang lại chút lợi ích nào cho ngƣời dùng.. - Để giải quyết vấn đề này, ngƣời ta đã xây dựng các hệ thống tìm kiếm thông tin. - Nó giúp con ngƣời tìm kiếm và chọn lọc ra những tài liệu có chứa thông tin cần thiết. - Do ngƣời sử dụng luôn yêu cầu kết quả tìm kiếm chính xác, đầy đủ và với các vận tốc tìm kiếm nhanh nên các hệ thống tìm kiếm thông tin luôn đƣợc nghiên cứu và phát triển cùng với các kỹ thuật lƣu trữ, thuật toán tìm kiếm hiệu quả và tối ƣu nhất.. - Nhƣ đã biết, tập hợp các trang Web đáp ứng một câu hỏi trả về từ máy tìm kiếm nói chung là rất lớn. - Mặc dù các kỹ thuật dựa trên các liên kết đã nâng cao chất lƣợng và độ chính xác của kết quả tìm kiếm, nhƣng tìm kiếm dựa trên văn bản (chẳng hạn tìm kiếm các trang chứa đựng từ khóa) vẫn tiếp tục phƣơng pháp chính để xác định các trang liên quan tới vấn đề đang đƣợc truy vấn. - Bảng chỉ mục văn bản hỗ trợ cho việc tìm kiếm có thể đƣợc thực hiện sử dụng bất kỳ phƣơng pháp truy cập truyền thống nào để tìm kiếm trên toàn tập tài liệu. - Vì vậy việc lập chỉ số trong máy tìm kiếm là một thao tác vô cùng quan trọng trong các hệ thống tìm kiếm. - 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. - Công cụ tìm kiếm web cũng nhƣ nhiều hệ thống tìm kiếm khác đều dựa vào chỉ số đảo ngƣợc với cấu trúc đơn giản và hiệu quả cho phép tìm thấy tất cả các tài liệu có chứa từ cụ thể.. - Luận văn tập trung khảo sát các phƣơng pháp nén chỉ số, chỉ số ngƣợc trong máy tìm kiếm và đánh giá kết thử nghiệm của các phƣơng pháp nén trong các bài báo . - Chƣơng 1 – Kiến trúc chung của máy tìm kiếm, thành phần chỉ số trong máy tìm kiếm. - Chƣơng này giới thiệu những nội dung cơ bản nhất, cung cấp một cách nhìn khái quát về kiến trúc của máy tìm kiếm trong mô hình hệ thống thông tin. - Đồng thời luận văn cũng mô tả chi tiết các thành phần của cấu trúc chỉ số trong máy tìm kiếm và nhu cầu nén chỉ số cho máy tìm kiếm.. - Chƣơng 2 – Các phƣơng pháp nén chỉ số trong máy tìm kiếm. - Ban đầu nội dung chƣơng mô tả cấu trúc chỉ số ngƣợc và phân tích quy trình lập chỉ số ngƣợc trong máy tìm kiếm. - Chƣơng trình đã hoạt động cho kết quả để đánh giá 2 thuật toán nén, tuy nhiên do thời gian hạn chế nên luận văn chƣa xây dựng đƣợc thuật toán vào trong máy tìm kiếm.. - KIẾN TRÚC CHUNG CỦA MÁY TÌM KIẾM THÀNH PHẦN CHỈ SỐ TRONG MÁY TÌM KIẾM 1.1 Khái niệm bộ 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, các thông tin thể hiện ở nhiều dạng khác nhau, có thể là dạng văn bản, âm thanh hoặc hình ảnh,vv. - Mà phổ biến nhất là tìm kiếm văn bản (bao gồm việc tìm kiếm hoặc sắp xếp văn bản), đặc biệt là trong các công cụ tìm kiếm. - Nhiều lúc, thuật ngữ này đƣợc dùng nhƣ là toàn bộ quá trình từ việc xử lý văn bản tới việc phân lớp và tìm kiếm văn bản. - Thuật ngữ tìm kiếm văn bản theo nghĩa bao gồm việc lập chỉ mục tài liệu, tìm kiếm và sắp xếp các văn bản tìm kiếm theo thứ tự liên quan đến yêu cầu ngƣời sử dụng (văn bản ở đây có thể là một File hoặc là một trang Web). - Internet là một kho thông tin khổng lồ và phức tạp. - Thông tin trên các trang Web đa dạng về mặt nội dung cũng nhƣ hình thức. - Tuy nhiên cùng với sự đa dạng và số lƣợng lớn thông tin nhƣ vậy đã nảy sinh vấn đề quá tải thông tin. - Cùng với sự thay đổi và phát triển hàng ngày hàng giờ về nội dung cũng nhƣ số lƣợng của các trang Web trên Internet thì vấn đề tìm kiếm thông tin đối với ngƣời sử dụng lại ngày càng khó khăn. - Đối với mỗi ngƣời dùng chỉ một phần rất nhỏ thông tin là có ích, chẳng hạn có ngƣời chỉ quan tâm đến trang Thể thao, Văn hóa mà không mấy khi quan tâm đến Kinh tế. - Ngƣời ta không thể tìm kiếm địa chỉ trang Web chứa thông tin mà mình cần, do vậy đòi hỏi cần phải có một trình tiện ích quản lý nội dung của các trang Web và cho phép tìm thấy các địa chỉ trang Web có nội dung giống với yêu cầu của ngƣời tìm kiếm.. - Theo tìm hiểu từ các nguồn thông tin khái niệm máy tìm kiếm (search engine) là một hệ thống đƣợc xây dựng nhằm tiếp nhận các yêu cầu tìm kiếm của ngƣời dùng (thƣờng là một tập các từ khóa), sau đó phân tích yêu cầu này và tìm kiếm thông tin trong cơ sở dữ liệu đƣợc tải xuống từ Web và đƣa ra kết quả là các trang web có liên quan cho ngƣời dùng.. - Bên cạnh đó có thể định nghĩa một hệ thống tìm kiếm thông tin là một chƣơng trình phần mềm dùng để lƣu trữ và quản lý thông tin nằm trong các tài liệu. - Hệ thống này giúp ngƣời sử dụng tìm kiếm thông tin mà họ quan tâm. - Các hệ thống này không giống nhƣ các hệ thống trả lời câu hỏi, nó chỉ ra sự tồn tại và vị trí các tài liệu có chứa thông tin cần thiết. - Một số tài liệu “tìm kiếm đƣợc” thỏa mãn yêu cầu của ngƣời sử dụng gọi là các tài liệu phù hợp hay tài liệu liên quan (relevanl document). - Một hệ thống tìm kiếm hoàn hảo sẽ chỉ tìm và đƣa ra các tài liệu liên quan mà không đƣa ra. - Tuy nhiên các hệ thống này không tồn tại bởi các thể hiện tìm kiếm là không đầy đủ mà mức độ liên quan phụ thuộc vào quan điểm chủ quan của từng ngƣời. - Hai ngƣời sử dụng có thể đƣa ra cùng một truy vấn với một hệ thống tìm kiếm thông tin và sau đó sẽ có những đánh giá khác nhau về mức độ liên quan trên các tài liệu đã tìm đƣợc. - Cụ thể, ngƣời dùng gửi một truy vấn, dạng đơn giản nhất là một danh sách các từ khóa, và máy tìm kiếm sẽ làm việc để trả lại một danh sách các trang Web có liên quan hoặc có chứa các từ khóa đó. - Một số máy tìm kiếm điển hình hiện nay: Yahoo, Google, Alvista, ASPSeek, VietSeek.... - Quy trình tìm kiếm thông tin nói chung thực hiện 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 hệ thống tìm kiếm nhanh thông tin mà ngƣời dùng cần. - Nhƣng để mô tả đặc điểm thông tin yêu cầu của ngƣời sử dụng không phải dễ dàng. - Vì thế, hệ thống tìm kiếm thông tin bao gồm ba 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 của ngƣời sử dụng và so sánh hai biểu diễn này.. - Hình 1.1 – Quy trình tìm kiếm thông tin [1]. - Vậy để mô tả thông tin một cách rõ ràng đầy đủ, ngƣời sử dụng không thể trực tiếp yêu cầu các giao diện hiện thời của hệ thống tìm kiếm cung cấp thông tin cần dùng.. - Thay vào đó ngƣời sử dụng 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 IR). - Cho một truy vấn ngƣời dùng, mục đích chính của một hệ thống tìm kiếm là tìm kiếm thông tin mà có thể trở thành hữu ích hoặc phù hợp với ngƣời sử dụng.. - Để đạt đƣợc hiệu quả đáp ứng thông tin yêu cầu của ngƣời dùng, hệ thống tìm kiếm phải bằng cách nào “hiểu” đƣợc các nội dung của thông tin (các văn bản) trong một tập hợp và sắp xếp chúng theo mức độ phù hợp với truy vấn. - Sự “hiểu biết” về nội dung văn bản này bao gồm sự trích chọn cú pháp và ngữ nghĩa thông tin từ văn bản và sử dụng thông tin này để so khớp với thông tin ngƣời dùng. - Cái khó là không chỉ hiểu để trích chọn thông tin này nhƣ thế nào mà còn là hiểu cách sử dụng nó để quyết định mối liên quan nhƣ thế nào. - Do vậy khái niệm mức độ liên quan (revlevance) cũng là một phần quan trọng trong tìm kiếm tất cả các tài liệu liên quan với một truy vấn ngƣời dùng mặc dù việc tìm kiếm có thể đƣa ra một tài liệu không thích hợp.. - Vậy, tìm kiếm thông tin là một quá trình nhận dạng, xác định và chỉ ra các tài liệu liên quan dựa trên mô tả yêu cầu thông tin của ngƣời sử dụng. - 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ừ khóa gắn với văn bản đó. - Các công cụ tìm kiếm nổi tiếng hiện nay nhƣ Google, Altavista, Yohoo. - 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 hóa.. - Kể từ những năm 40, các vấn đề trong việc lƣu trữ thông tin và tìm kiếm thông tin đã thu hút sự chú ý rất lớn. - Với một lƣợng thông tin khổng lồ thì việc tìm kiếm chính xác và nhanh chóng càng trở nên khó khăn hơn. - ý tƣởng lớn đƣợc đƣa ra nhằm cung cấp một hệ thống tìm kiếm thông minh và chính xác. - Tuy nhiên, vấn đề tìm kiếm sao cho hiệu quả vẫn chƣa đƣợc giải quyết.. - Về nguyên tắc, việc lƣu trữ thông tin và tìm kiếm thông tin thì đơn giản. - Do đó, mục tiêu của một hệ thống tìm kiếm thông tin tự động là truy tìm đƣợc tất cả các tài liệu có liên quan đến yêu cầu của ngƣời sử dụng.. - Mặc dù trong thực tiễn, mỗi máy tìm kiếm có cách thực thi riêng mà theo đó các thành phần đƣợc trình bày nhƣ dƣới đây có thể đƣợc nhập hoặc tách ra. - Tuy nhiên, một máy tìm kiếm điển hình thƣờng gồm các thành phần chức năng sau:. - Thành phần Crawling (Crawler): Đây là thành phần có chức năng thu thập tài nguyên trang Web cho máy tìm kiếm. - Nhờ có bảng chỉ mục này, máy tìm kiếm nhanh chóng cung cấp đƣợc tất cả các địa chỉ URL của các trang Web đáp ứng truy vấn ngƣời dùng