Luận văn thạc sĩ về phương pháp nén chỉ số trong hệ thống tìm kiếm

Luận văn thạc sĩ phân tích nghiên cứu các phương pháp nén chỉ số trong các hệ thống tìm kiếm 04, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả thi cho thực tiễn.

• Tác giả: Lê Thị Hoài Thu
• Người hướng dẫn: PGS.TS Hà Quang Thụy
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Nghiên Cứu Phương Pháp Nén Chỉ Số Trong Hệ Thống Tìm Kiếm
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. 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
• 1.1. Khái niệm bộ công cụ tìm kiếm thông tin
• 1.2. Tổng quan về hệ thống tìm kiếm
• 1.3. Quy trình tìm kiếm thông tin
• 1.4. Một số vấn đề trong tìm kiếm thông tin
• 1.5. Cấu trúc điển hình của một máy tìm kiếm
• 2. CHƯƠNG 2: 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.2.1. Lưu trữ theo khối
• 2.2.2. Nén bộ từ điển từ vựng như một chuỗi
• 2.2.3. Nén tập tin posting
• 2.3. Các phương pháp nén chỉ số cập nhật
• 2.4. Cải tiến thuật toán PFD
• 3. CHƯƠNG 3: TÌM HIỂU VỀ LUCENE
• 3.1. Tìm hiểu về Lucene
• 3.1.1. Giới thiệu chung về Lucene
• 3.1.2. Tìm hiểu các lớp đối tượng lập chỉ mục
• 3.1.3. Tìm hiểu các lớp đối tượng tìm kiếm
• 3.2. Lập chỉ số trong Lucene
• 3.2.1. Các tiến trình lập chỉ số
• 3.2.2. Các toán tử cơ bản trong lập chỉ số với Lucene
• 3.2.3. Khuếch đại các tài liệu và các trường
• 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.3.2. Bộ chuyển đổi câu truy vấn của người dùng: QueryParser
• 3.3.3. Sử dụng lớp IndexSearcher
• 3.3.4. Tiến trình phân tích của Lucene
• 3.3.5. Định dạng chỉ số trong Lucene
• 3.3.5.1. Cấu trúc chỉ số
• 3.3.5.2. Chỉ số ngược
• 4. CHƯƠNG 4: CÀI ĐẶT THỬ NGHIỆM VÀ KẾT QUẢ THỰC HIỆN
• 4.1. Giới thiệu chương trình thử nghiệm
• 4.2. Kết quả thử nghiệm
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về nén chỉ số trong hệ thống tìm kiếm

Nén chỉ số là một phương pháp quan trọng trong việc tối ưu hóa hiệu suất của hệ thống tìm kiếm. Việc nén chỉ số giúp giảm thiểu không gian lưu trữ cần thiết cho các chỉ số, từ đó cải thiện tốc độ truy xuất dữ liệu. Phương pháp nén chỉ số có thể được áp dụng cho nhiều loại dữ liệu khác nhau, bao gồm văn bản, hình ảnh và âm thanh. Trong bối cảnh công nghệ tìm kiếm, nén chỉ số không chỉ giúp tiết kiệm tài nguyên mà còn nâng cao hiệu quả tìm kiếm. Theo nghiên cứu, việc áp dụng các thuật toán nén hiệu quả có thể giảm thiểu thời gian truy xuất thông tin, từ đó cải thiện trải nghiệm người dùng. Một số phương pháp nén phổ biến bao gồm nén theo khối và nén bộ từ điển từ vựng. Những phương pháp này không chỉ giúp giảm kích thước dữ liệu mà còn duy trì tính toàn vẹn của thông tin. Việc tối ưu hóa chỉ số là một yếu tố then chốt trong việc phát triển các hệ thống tìm kiếm hiện đại.

1.1. Tầm quan trọng của nén chỉ số

Nén chỉ số đóng vai trò quan trọng trong việc quản lý và lưu trữ dữ liệu trong hệ thống tìm kiếm. Khi khối lượng dữ liệu ngày càng lớn, việc lưu trữ và truy xuất thông tin trở nên khó khăn hơn. Nén chỉ số giúp giảm thiểu không gian lưu trữ, từ đó tiết kiệm chi phí và tài nguyên. Hơn nữa, việc nén chỉ số còn giúp tăng tốc độ truy xuất dữ liệu, điều này rất quan trọng trong các ứng dụng yêu cầu thời gian phản hồi nhanh. Theo một nghiên cứu gần đây, các thuật toán nén hiện đại có thể giảm kích thước chỉ số lên đến 90% mà vẫn đảm bảo hiệu suất tìm kiếm. Điều này cho thấy rằng công nghệ tìm kiếm không chỉ cần hiệu quả mà còn cần phải tiết kiệm tài nguyên. Do đó, việc nghiên cứu và phát triển các phương pháp nén chỉ số là cần thiết để đáp ứng nhu cầu ngày càng cao của người dùng.

II. Các phương pháp nén chỉ số

Có nhiều phương pháp nén chỉ số khác nhau được áp dụng trong hệ thống tìm kiếm. Một trong những phương pháp phổ biến là nén theo khối, trong đó dữ liệu được chia thành các khối nhỏ và nén riêng lẻ. Phương pháp này giúp tối ưu hóa không gian lưu trữ và tăng tốc độ truy xuất. Ngoài ra, nén bộ từ điển từ vựng cũng là một kỹ thuật quan trọng, giúp giảm kích thước của từ điển mà vẫn đảm bảo khả năng tìm kiếm chính xác. Các thuật toán nén như PforDelta và Variable Byte (VB) đã được chứng minh là hiệu quả trong việc nén chỉ số. Việc áp dụng các phương pháp này không chỉ giúp tiết kiệm không gian mà còn cải thiện hiệu suất tìm kiếm. Theo một nghiên cứu, việc sử dụng các thuật toán nén hiện đại có thể giảm thời gian truy xuất thông tin xuống còn một phần nhỏ so với các phương pháp truyền thống. Điều này cho thấy rằng nén chỉ số là một yếu tố quan trọng trong việc tối ưu hóa hệ thống tìm kiếm.

2.1. Nén theo khối

Nén theo khối là một trong những phương pháp nén chỉ số hiệu quả nhất trong hệ thống tìm kiếm. Phương pháp này chia dữ liệu thành các khối nhỏ và nén từng khối một cách độc lập. Điều này không chỉ giúp giảm kích thước dữ liệu mà còn tăng tốc độ truy xuất. Theo nghiên cứu, nén theo khối có thể giảm kích thước dữ liệu lên đến 80% mà không làm giảm chất lượng thông tin. Hơn nữa, phương pháp này cho phép truy xuất dữ liệu nhanh chóng, điều này rất quan trọng trong các ứng dụng yêu cầu thời gian phản hồi nhanh. Việc áp dụng nén theo khối trong các công nghệ tìm kiếm hiện đại đã chứng minh được hiệu quả của nó trong việc tối ưu hóa không gian lưu trữ và cải thiện hiệu suất tìm kiếm.

III. Ứng dụng thực tiễn của nén chỉ số

Nén chỉ số không chỉ là một khái niệm lý thuyết mà còn có nhiều ứng dụng thực tiễn trong hệ thống tìm kiếm. Các công cụ tìm kiếm lớn như Google và Bing đã áp dụng các phương pháp nén chỉ số để tối ưu hóa hiệu suất của họ. Việc nén chỉ số giúp giảm thiểu thời gian truy xuất và tăng tốc độ tìm kiếm, từ đó cải thiện trải nghiệm người dùng. Hơn nữa, nén chỉ số còn giúp tiết kiệm chi phí lưu trữ, điều này rất quan trọng trong bối cảnh dữ liệu ngày càng gia tăng. Theo một nghiên cứu, việc áp dụng các phương pháp nén chỉ số có thể giảm chi phí lưu trữ lên đến 50%. Điều này cho thấy rằng nén chỉ số không chỉ mang lại lợi ích về hiệu suất mà còn về kinh tế cho các hệ thống tìm kiếm.

3.1. Tối ưu hóa hiệu suất tìm kiếm

Tối ưu hóa hiệu suất tìm kiếm là một trong những ứng dụng quan trọng của nén chỉ số. Khi khối lượng dữ liệu ngày càng lớn, việc tìm kiếm thông tin trở nên khó khăn hơn. Nén chỉ số giúp giảm thiểu thời gian truy xuất và tăng tốc độ tìm kiếm. Theo một nghiên cứu, việc áp dụng các thuật toán nén hiện đại có thể giảm thời gian truy xuất thông tin xuống còn một phần nhỏ so với các phương pháp truyền thống. Điều này cho thấy rằng nén chỉ số là một yếu tố quan trọng trong việc tối ưu hóa hiệu suất của hệ thống tìm kiếm. Hơn nữa, việc tối ưu hóa hiệu suất tìm kiếm không chỉ giúp cải thiện trải nghiệm người dùng mà còn giúp tiết kiệm tài nguyên và chi phí cho các tổ chức.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh xã hội hiện đại, thông tin đã trở thành nguồn tài nguyên vô cùng quan trọng, đóng vai trò then chốt trong mọi hoạt động kinh tế - xã hội. Sự phát triển nhanh chóng của mạng Internet và sự bùng nổ dữ liệu số đã tạo ra các kho dữ liệu khổng lồ với dung lượng ngày càng tăng. Theo ước tính, lượng dữ liệu trên toàn cầu tăng trưởng với tốc độ hàng nghìn tỷ byte mỗi ngày, đặt ra thách thức lớn trong việc khai thác và tìm kiếm thông tin hiệu quả. Vấn đề cốt lõi là làm thế nào để tổ chức, lưu trữ và truy xuất thông tin một cách nhanh chóng, chính xác và tiết kiệm tài nguyên.

Luận văn tập trung nghiên cứu các phương pháp nén chỉ số trong các hệ thống tìm kiếm thông tin, đặc biệt là chỉ số ngược (inverted index) – thành phần quan trọng giúp tăng tốc độ truy vấn và giảm dung lượng lưu trữ. Mục tiêu cụ thể của nghiên cứu là khảo sát, đánh giá các kỹ thuật nén chỉ số hiện có, đồng thời triển khai cài đặt thử nghiệm các thuật toán nén cơ bản và cải tiến trên tập dữ liệu thực tế nhằm tối ưu hóa hiệu suất hệ thống tìm kiếm. Phạm vi nghiên cứu tập trung vào lĩnh vực Công nghệ Thông tin, chuyên ngành Hệ thống Thông tin, với dữ liệu thử nghiệm được thu thập và xử lý trong môi trường lập trình Java tại Việt Nam, giai đoạn năm 2015.

Nghiên cứu có ý nghĩa thiết thực trong việc nâng cao hiệu quả hoạt động của các công cụ tìm kiếm, giảm chi phí lưu trữ và tăng tốc độ phản hồi truy vấn, góp phần cải thiện trải nghiệm người dùng và hỗ trợ các ứng dụng khai thác dữ liệu lớn trong nhiều lĩnh vực khác nhau.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình nghiên cứu sau:

• Lý thuyết hệ thống tìm kiếm thông tin (Information Retrieval - IR): Bao gồm các khái niệm về biểu diễn tài liệu, truy vấn, quá trình lập chỉ mục và đối sánh truy vấn với tài liệu. Khung lý thuyết này giúp hiểu rõ cách thức tổ chức và truy xuất thông tin trong các hệ thống tìm kiếm.

• Mô hình chỉ số ngược (Inverted Index): Là cấu trúc dữ liệu chủ đạo trong các hệ thống tìm kiếm văn bản, bao gồm bộ từ điển từ vựng (dictionary) và danh sách các vị trí xuất hiện của từ khóa (posting list). Mô hình này giúp tăng tốc độ truy vấn và giảm không gian lưu trữ.

• Các thuật toán nén số nguyên (Integer Compression Algorithms): Bao gồm các phương pháp như Variable Byte (VB) code, Elias Gamma code, Simple9, PforDelta (PFD) và các cải tiến như OptPFD. Các thuật toán này nhằm giảm kích thước của chỉ số ngược mà vẫn đảm bảo tốc độ giải nén nhanh.

• Khái niệm về tần suất xuất hiện (Term Frequency - TF) và trọng số mục từ: Giúp xác định mức độ quan trọng của từ khóa trong tài liệu, ảnh hưởng đến hiệu quả lập chỉ mục và xếp hạng kết quả tìm kiếm.

Phương pháp nghiên cứu

• Nguồn dữ liệu: Tập dữ liệu thử nghiệm được lấy từ các bộ dữ liệu chuẩn trong lĩnh vực tìm kiếm thông tin, bao gồm các tài liệu văn bản đa dạng về nội dung và kích thước. Ngoài ra, dữ liệu được thu thập và xử lý trong môi trường lập trình Java, sử dụng thư viện Lucene để lập chỉ mục và thử nghiệm các thuật toán nén.

• Phương pháp phân tích: Nghiên cứu sử dụng phương pháp phân tích định lượng, đánh giá hiệu suất các thuật toán nén dựa trên các chỉ số như kích thước chỉ số sau nén, tốc độ giải nén, và thời gian phản hồi truy vấn. Các thuật toán được so sánh trực tiếp qua các thử nghiệm thực tế.

• Timeline nghiên cứu: Quá trình nghiên cứu được thực hiện trong năm 2015, bao gồm các giai đoạn: khảo sát tài liệu và lý thuyết (3 tháng), thiết kế và cài đặt thử nghiệm (4 tháng), thu thập và phân tích kết quả (3 tháng), hoàn thiện luận văn (2 tháng).

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả nén của các thuật toán: Thuật toán Variable Byte (VB) code giảm kích thước chỉ số ngược khoảng 50% so với dữ liệu chưa nén, trong khi Elias Gamma code đạt tỷ lệ nén tốt hơn khoảng 15% so với VB code, giảm kích thước xuống còn khoảng 101MB trên tập dữ liệu RCV1. Thuật toán Simple9 và PforDelta (PFD) tiếp tục cải thiện tỷ lệ nén, với PFD đạt hiệu quả nén cao hơn và tốc độ giải nén nhanh hơn.

2. Tốc độ giải nén: PforDelta và các cải tiến như OptPFD cho phép giải nén với tốc độ trên 1200 triệu docID/giây, đáp ứng yêu cầu xử lý truy vấn nhanh trong các hệ thống tìm kiếm quy mô lớn. Các phương pháp nén bitwise như Gamma code tuy có tỷ lệ nén cao nhưng tốc độ giải nén thấp hơn so với VB code.

3. Ảnh hưởng của kích thước khối (block size): Việc lưu trữ theo khối giúp giảm không gian lưu trữ và tăng hiệu quả truy vấn. Kích thước khối tăng lên giúp nén tốt hơn nhưng làm tăng thời gian tìm kiếm từ khóa trong từ điển, cần cân bằng giữa tốc độ và tỷ lệ nén.

4. Ứng dụng Lucene: Thư viện Lucene hỗ trợ hiệu quả việc lập chỉ mục và tìm kiếm dựa trên chỉ số ngược. Việc tích hợp các thuật toán nén trong Lucene giúp giảm dung lượng lưu trữ chỉ số và tăng tốc độ truy vấn, tuy nhiên việc tích hợp thuật toán nén nâng cao vào Lucene còn gặp hạn chế do thời gian nghiên cứu có giới hạn.

Thảo luận kết quả

Kết quả thử nghiệm cho thấy các phương pháp nén chỉ số đóng vai trò quan trọng trong việc tối ưu hóa hệ thống tìm kiếm thông tin. Việc sử dụng các thuật toán nén như PforDelta và OptPFD không chỉ giảm đáng kể dung lượng lưu trữ mà còn đảm bảo tốc độ giải nén nhanh, phù hợp với yêu cầu xử lý truy vấn thời gian thực. So sánh với các nghiên cứu trước đây, kết quả này tương đồng với báo cáo của ngành về hiệu quả của các thuật toán nén bitwise và bytewise.

Việc lưu trữ theo khối và nén bộ từ điển từ vựng như một chuỗi giúp giảm thiểu lãng phí bộ nhớ và tăng tốc độ tìm kiếm từ khóa. Tuy nhiên, cần lưu ý rằng việc tăng kích thước khối có thể làm giảm tốc độ tìm kiếm từ điển, do đó cần lựa chọn kích thước phù hợp tùy theo đặc điểm tập dữ liệu và yêu cầu hệ thống.

Ứng dụng Lucene trong nghiên cứu cho thấy tiềm năng lớn của các thư viện mã nguồn mở trong phát triển hệ thống tìm kiếm, đồng thời cũng chỉ ra những thách thức trong việc tích hợp các thuật toán nén nâng cao vào hệ thống thực tế. Việc tiếp tục nghiên cứu và phát triển các thuật toán nén phù hợp với kiến trúc Lucene sẽ là hướng đi quan trọng trong tương lai.

Dữ liệu có thể được trình bày qua các biểu đồ so sánh kích thước chỉ số trước và sau khi nén, tốc độ giải nén của từng thuật toán, cũng như bảng tổng hợp các thông số kỹ thuật của các phương pháp nén.

Đề xuất và khuyến nghị

1. Tích hợp thuật toán nén PforDelta và OptPFD vào hệ thống tìm kiếm: Động từ hành động: triển khai; Target metric: giảm dung lượng chỉ số ít nhất 30% và tăng tốc độ truy vấn trên 20%; Timeline: 6 tháng; Chủ thể thực hiện: nhóm phát triển phần mềm hệ thống tìm kiếm.

2. Tối ưu kích thước khối lưu trữ trong chỉ số ngược: Động từ hành động: điều chỉnh; Target metric: cân bằng giữa tốc độ tìm kiếm từ điển và tỷ lệ nén; Timeline: 3 tháng; Chủ thể thực hiện: nhóm nghiên cứu dữ liệu và kỹ thuật lưu trữ.

3. Phát triển module nén chỉ số tích hợp trong Lucene: Động từ hành động: phát triển; Target metric: tích hợp thành công thuật toán nén nâng cao, giảm dung lượng chỉ số ít nhất 25%; Timeline: 9 tháng; Chủ thể thực hiện: nhóm kỹ sư phần mềm và nghiên cứu.

4. Đào tạo và nâng cao nhận thức về kỹ thuật nén chỉ số cho đội ngũ kỹ thuật: Động từ hành động: tổ chức đào tạo; Target metric: 100% nhân viên kỹ thuật được đào tạo; Timeline: 2 tháng; Chủ thể thực hiện: phòng nhân sự và đào tạo.

5. Thường xuyên cập nhật và đánh giá hiệu suất các thuật toán nén: Động từ hành động: giám sát và đánh giá; Target metric: duy trì hiệu suất hệ thống ổn định và cải tiến liên tục; Timeline: liên tục hàng năm; Chủ thể thực hiện: bộ phận vận hành và nghiên cứu phát triển.

Đối tượng nên tham khảo luận văn

1. Nhà phát triển hệ thống tìm kiếm thông tin: Luận văn cung cấp kiến thức chuyên sâu về cấu trúc chỉ số ngược và các thuật toán nén, giúp cải thiện hiệu suất và tiết kiệm tài nguyên trong phát triển công cụ tìm kiếm.

2. Chuyên gia xử lý dữ liệu lớn (Big Data): Các phương pháp nén chỉ số được trình bày giúp tối ưu hóa lưu trữ và truy xuất dữ liệu quy mô lớn, phù hợp với các ứng dụng phân tích và khai thác dữ liệu.

3. Nhà nghiên cứu công nghệ thông tin và hệ thống thông tin: Luận văn cung cấp cơ sở lý thuyết và thực nghiệm về kỹ thuật lập chỉ mục và nén dữ liệu, hỗ trợ nghiên cứu và phát triển các giải pháp mới trong lĩnh vực.

4. Sinh viên và học viên cao học ngành Công nghệ Thông tin: Tài liệu là nguồn tham khảo quý giá cho việc học tập, nghiên cứu và thực hành về hệ thống tìm kiếm, lập chỉ mục và nén dữ liệu.

Câu hỏi thường gặp

1. Tại sao cần nén chỉ số trong hệ thống tìm kiếm?
   Nén chỉ số giúp giảm dung lượng lưu trữ, tiết kiệm chi phí phần cứng và tăng tốc độ truy xuất dữ liệu, từ đó cải thiện hiệu suất tổng thể của hệ thống tìm kiếm.

2. Phương pháp nén nào hiệu quả nhất cho chỉ số ngược?
   PforDelta và các cải tiến như OptPFD được đánh giá cao về tỷ lệ nén và tốc độ giải nén, phù hợp với các hệ thống tìm kiếm quy mô lớn.

3. Lucene hỗ trợ những tính năng gì trong lập chỉ mục?
   Lucene cung cấp API để lập chỉ mục toàn văn bản, hỗ trợ nhiều định dạng dữ liệu, tối ưu hóa chỉ mục và tìm kiếm nhanh dựa trên cấu trúc chỉ số ngược.

4. Làm thế nào để cân bằng giữa tốc độ tìm kiếm và tỷ lệ nén?
   Cần điều chỉnh kích thước khối lưu trữ và lựa chọn thuật toán nén phù hợp, đồng thời đánh giá hiệu suất thực tế để đạt được sự cân bằng tối ưu.

5. Có thể áp dụng các thuật toán nén này cho ngôn ngữ khác ngoài tiếng Anh không?
   Có thể, tuy nhiên cần chú ý đến đặc điểm ngôn ngữ như tách từ và xử lý ngôn ngữ tự nhiên để đảm bảo hiệu quả lập chỉ mục và nén.

Kết luận

• Luận văn đã phân tích và đánh giá các phương pháp nén chỉ số trong hệ thống tìm kiếm, tập trung vào chỉ số ngược và các thuật toán nén số nguyên như VB code, Gamma code, Simple9, PforDelta và OptPFD.
• Kết quả thử nghiệm cho thấy các thuật toán nén nâng cao giúp giảm đáng kể dung lượng lưu trữ và tăng tốc độ giải nén, đáp ứng yêu cầu xử lý truy vấn nhanh trong môi trường dữ liệu lớn.
• Việc ứng dụng thư viện Lucene trong nghiên cứu minh họa tiềm năng phát triển hệ thống tìm kiếm hiệu quả dựa trên mã nguồn mở, đồng thời chỉ ra những thách thức trong tích hợp thuật toán nén nâng cao.
• Đề xuất các giải pháp thực tiễn nhằm tối ưu hóa hệ thống tìm kiếm thông tin, bao gồm tích hợp thuật toán nén, điều chỉnh kích thước khối và đào tạo nhân lực.
• Hướng nghiên cứu tiếp theo tập trung vào phát triển module nén tích hợp trong Lucene và mở rộng thử nghiệm trên các tập dữ liệu đa dạng hơn.

Các nhà phát triển và nghiên cứu trong lĩnh vực hệ thống tìm kiếm thông tin được khuyến khích áp dụng và tiếp tục cải tiến các thuật toán nén chỉ số để nâng cao hiệu quả hệ thống, đồng thời chia sẻ kết quả nghiên cứu nhằm thúc đẩy sự phát triển chung của ngành.

Trích đoạn nội dung tài liệu

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.

Nội dung của chương này xem xét và đánh giá một số phương pháp nén chỉ số cơ bản và cập nhật. 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. Từ đó đưa ra các phương pháp cập nhật và cải tiến để nén các tập chỉ số một cách tối ưu. Chương 3 – Tìm hiểu về Lucene.

Giới thiệu chi tiết về Lucene, các thành phần cơ bản trong Lucene, cấu trúc chỉ số trong Lucene và tối ưu hóa lập chỉ số trong Lucene. Chương 4 – Cài đặt thử nghiệm. Chương trình trình bày kết quả thực nghiệm nén chỉ số ngược trên cơ sở thuật toán nén Khoảng cách byte (VB code) và OptPFD. Chương trình cài đặt thử nghiệm được viết bởi ngôn ngữ Java trên nền Console.

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. Phần Kết luận. Trình bày tổng hợp các kết quả thực hiện luận văn và phương hướng nghiên cứu tiếp theo về các nội dung của luận văn. 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 Tổng quan về hệ thống tìm kiếm 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 z 11 các tài liệu không liên quan. 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 đó. Phức tạp hơn, thì truy vấn là cả một văn bản hoặc một đoạn văn bản hoặc nội dung tóm tắt của văn bản. Một số máy tìm kiếm điển hình hiện nay: Yahoo, Google, Alvista, ASPSeek, VietSeek.2 Quy trình tìm kiếm thông tin 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.1 – Quy trình tìm kiếm thông tin [1]  Quá trình biểu diễn tài liệu được gọi là quá trình chỉ số hóa (indexing). Quá trình này có thể lưu trữ thực sự các tài liệu trong hệ thống, thông thường chỉ lưu trữ một phần tài liệu, chẳng hạn như phần tiêu đề và tóm tắt.

 Quá trình biểu diễn yêu cầu người sử dụng gọi là quá trình biểu diễn truy vấn (query formulation process). Truy vấn biểu thị sự tương tác giữa hệ thống và người sử z 12 dụng, do đó quá trình này không chỉ đưa ra một truy vấn phù hợp mà còn phải thể hiện được sự hiểu biết về yêu cầu của người sử dụng. Sự thiết lập tự động các truy vấn liên tiếp được gọi là phản hồi độ liên quan (relevance feedback).  So sánh truy vấn với tài liệu cũng được gọi là quá trình đối sánh (matching process) và cho kết quả là một danh sách các tài liệu được sắp xếp theo mức độ liên quan tới truy vấn.

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). Thường thì phép chuyển đổi này tạo ra một tập hợp các từ khóa (hoặc các term chỉ số) mô tả khái quát yêu cầu của người sử dụng. 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.3 Một số vấn đề trong tìm kiếm thông tin 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. Với sự ra đời của máy tính, rất nhiều z 13 ý 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. Giả sử có một kho chứa các tài liệu và một người muốn tìm các tài liệu liên quan đến yêu cầu của mình. Người đó có thể đọc tất cả các tài liệu trong kho, giữ lại các tài liệu liên quan và bỏ đi các tài liệu không liên quan. Rõ ràng giải pháp này không thực tế bởi vì tốn rất nhiều thời gian.

Với sự ra đời của máy vi tính tốc độ cao, máy tính có thể “đọc” thay cho con người để trích ra các tài liệu có liên quan trong toàn bộ tập dữ liệu.