Tài liệu Luận văn thạc sĩ xây dựng hệ thống truy xuất thông tin

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI …………………………………….. LUẬN VĂN THẠC SĨ KHOA HỌC XÂY DỰNG HỆ THỐNG TRUY XUẤT THÔNG TIN NGÀNH: CÔNG NGHỆ THÔNG TIN MÃ SỐ: TRẦN THỊ HOÀNG THẢO Người hướng dẫn khoa học: TS. LÊ THANH HƯƠNG HÀ NỘI 2006 MỤC LỤC MỤC LỤC......................................................................................................... 2 DANH MỤC CÁC TỪ VIẾT TẮT .................................................................. 4 DANH MỤC BẢNG......................................................................................... 5 DANH MỤC HÌNH .......................................................................................... 6 MỞ ĐẦU........................................................................................................... 8 U CHƯƠNG 1. TỔNG QUAN VỀ TRUY XUẤT THÔNG TIN ..................... 10 1.1. Khái niệm truy xuất thông tin............................................................... 10 1.2. Quá trình truy xuất thông tin ................................................................ 13 1.2.1. Giai đoạn tiền xử lý........................................................................ 15 1.2.2. Giai đoạn thu thập .......................................................................... 20 1.3. Các hướng tiếp cận giải quyết bài toán truy xuất thông tin.................. 22 1.4. Đánh giá hiệu quả truy xuất thông tin .................................................. 22 1.4.1. Độ chính xác và độ bao phủ........................................................... 23 1.4.2. Độ chính xác trung bình................................................................. 25 1.4.3. Độ đo F và độ đo E ........................................................................ 26 1.4.4. Các tiếp cận đánh giá lấy người dùng làm trung tâm .................... 28 1.5. Một số hệ thống truy xuất thông tin ..................................................... 29 1.6. Kết chương............................................................................................ 34 CHƯƠNG 2. CÁC CÔNG CỤ TRUY XUẤT THÔNG TIN CƠ BẢN ........ 35 2.1. Lập chỉ mục .......................................................................................... 35 2.2. Xếp hạng ............................................................................................... 43 2.2.1. Tổng quan các mô hình truy xuất thông tin ................................... 43 2.2.2. Các mô hình lôgíc .......................................................................... 46 2.2.3. Các mô hình đại số ......................................................................... 52 2.2.4. Các mô hình xác suất ..................................................................... 56 2.3. Kết chương............................................................................................ 61 3 Truy xuất thông tin CHƯƠNG 3. CƠ CHẾ HOẠT ĐỘNG CỦA LUCENE................................. 62 3.1. Giới thiệu Lucene ................................................................................. 62 3.2. Lập chỉ mục .......................................................................................... 63 3.2.1. Khung nhìn lôgíc của chỉ mục ....................................................... 64 3.2.2. Cấu trúc chỉ mục ............................................................................ 65 3.2.3. Inverted index................................................................................. 73 3.2.4. Chiến lược lập chỉ mục .................................................................. 77 3.3. Tìm kiếm............................................................................................... 78 3.3.1. Mô hình không gian véctơ ............................................................. 78 3.3.2. Xếp hạng ........................................................................................ 81 3.4. Kết chương............................................................................................ 84 CHƯƠNG 4. CHƯƠNG TRÌNH VÀ KẾT QUẢ THỰC NGHIỆM ............. 85 4.1. Kiến trúc hoạt động của chương trình .................................................. 85 4.2. Kết quả thực nghiệm............................................................................. 87 4.3. Kết chương............................................................................................ 94 CHƯƠNG 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA LUẬN VĂN 95 5.1. Kết luận................................................................................................. 95 5.2. Hướng phát triển của luận văn.............................................................. 96 TÀI LIỆU THAM KHẢO............................................................................... 98 TÀI LIỆU THAM KHẢO CHÉO................................................................. 100 Trần Thị Hoàng Thảo Luận văn thạc sĩ 4 Truy xuất thông tin DANH MỤC CÁC TỪ VIẾT TẮT BIR Binary Independence Retrieval: truy xuất độc lập nhị phân CLM Coordination Level Matching: đối sánh mức đồng hạng GVSM Generalized Vector Space Model: mô hình không gian véctơ suy rộng idf Inverse Document Frequency: nghịch đảo tần số văn bản IR Information Retrieval: truy xuất thông tin LSI Latent Semantic Indexing: lập chỉ mục ngữ nghĩa tiềm ẩn tf Term Frequency: tần số thuật ngữ tf – idf Phương pháp tần số kết hợp của tf và idf TREC Text REtrieval Conference : hội nghị truy xuất văn bản VSM Vector Space Model: mô hình không gian véctơ Trần Thị Hoàng Thảo Luận văn thạc sĩ 5 Truy xuất thông tin DANH MỤC BẢNG Bảng 1-1 Số thứ tự các hệ thống trong biểu đồ .............................................. 31 Bảng 3-1 Ví dụ các tệp chỉ mục ...................................................................... 66 Bảng 3-2 Ví dụ các tệp chỉ mục ...................................................................... 67 Bảng 3-3 Ví dụ các tệp chỉ mục ...................................................................... 69 Bảng 3-4 Ví dụ chỉ mục ghép ......................................................................... 71 Bảng 4-1 So sánh kết quả lập chỉ mục của chương trình và Google Desktop 88 Bảng 4-2 Các loại truy vấn được thử nghiệm ................................................. 90 Bảng 4-3 So sánh hiệu quả truy vấn của chương trình và Google Desktop ... 91 Trần Thị Hoàng Thảo Luận văn thạc sĩ 6 Truy xuất thông tin DANH MỤC HÌNH Hình 1-1 Quy trình truy xuất thông tin nói chung (nguồn: [1])...................... 13 Hình 1-2 Khung nhìn lôgíc của tài liệu thông qua các giai đoạn tiền xử lý (nguồn: [1]) ..................................................................................................... 15 Hình 1-3 Văn bản A ban đầu .......................................................................... 16 Hình 1-4 Văn bản A sau khi phân tích............................................................ 16 Hình 1-5 Văn bản A sau khi loại các từ trong danh sách stopword của Smart ......................................................................................................................... 17 Hình 1-6 Văn bản A sau khi lấy gốc từ........................................................... 18 Hình 1-7 Ví dụ đồ thị độ chính xác-độ bao phủ trung bình............................ 24 Hình 1-8 Các tài liệu được thu thập so với các tài liệu có liên quan (nguồn: [5]) ................................................................................................................... 27 Hình 1-9 Biểu đồ so sánh tính chính xác của một số hệ thống IR.................. 30 Hình 1-10 Biểu đồ so sánh tính hiệu quả của một số hệ thống IR ................. 30 Hình 1-11 Biểu đồ so sánh một số hệ thống IR .............................................. 31 Hình 2-1 Tần số tập hợp (cf) và tần số tài liệu (df) thể hiện khác nhau ......... 37 Hình 2-2 Ví dụ các giá trị idf .......................................................................... 38 Hình 2-3 Một ví dụ tạo nhãn với mỗi khối logic có D = 2 từ, kích thước nhãn F = 12 bit, m = 4 bit ........................................................................................ 39 Hình 2-4 Cấu trúc File dạng SSF .................................................................... 40 Hình 2-5 Minh hoạ một Inverted File ............................................................. 42 Hình 3-1 Quy trình lập chỉ mục với Lucene ................................................... 63 Hình 3-2 Khung nhìn lôgíc của một chỉ mục Lucene..................................... 65 Hình 3-3 Chỉ mục không được tối ưu hoá gồm 3 phân đoạn, chứa 24 tài liệu ......................................................................................................................... 68 Hình 3-4 Ví dụ minh hoạ định dạng chỉ mục của Lucene (nguồn: [4]).......... 74 Trần Thị Hoàng Thảo Luận văn thạc sĩ 7 Truy xuất thông tin Hình 3-5 Một sơ đồ lập chỉ mục Lucene......................................................... 78 Hình 3-6 Minh họa độ tương tự côsin............................................................. 79 Hình 4-1 Kiến trúc hoạt động của chương trình ............................................. 85 Hình 4-2 Phần client thực hiện tìm kiếm ........................................................ 87 Hình 4-3 Biểu đồ độ chính xác giữa chương trình và Google Desktop ......... 89 Hình 4-4 Biểu đồ R-Precision của chương trình (R = 10) .............................. 93 Hình 4-5 Biểu đồ so sánh thời gian thực hiện giữa chương trình với Google Desktop............................................................................................................ 93 Trần Thị Hoàng Thảo Luận văn thạc sĩ 8 Truy xuất thông tin MỞ ĐẦU Ngày nay, sự phát triển mạnh mẽ của công nghệ thông tin dẫn tới dung lượng dữ liệu được lưu trên máy tính gia tăng nhanh chóng. Trong những tập dữ liệu khổng lồ đó ẩn chứa hàm lượng thông tin vô cùng lớn. Vấn đề đặt ra là làm thế nào khai thác được khối thông tin đó để nó trở nên có ích đối với người dùng. Những tiến bộ đạt được về lý thuyết và công nghệ trong lĩnh vực xử lý thông tin đã giải quyết được phần nào nhu cầu nêu trên, chẳng hạn, các bài toán trong xử lý văn bản như tìm kiếm, phân loại, phân cụm văn bản. Information Retrieval (tạm dịch là truy xuất thông tin) là một trong số các vấn đề rất được quan tâm hiện nay. Đây là vấn đề khó, ngay cả với những hệ thống tìm kiếm phổ biến trên mạng Internet như Google, Altavista, Yahoo thì vẫn còn nhiều hạn chế. Có thể liệt kê các hạn chế thường gặp như sau: thứ nhất là với mỗi truy vấn, hệ thống thường trả về tập kết quả gồm hàng nghìn tài liệu, thậm chí còn lớn hơn nhiều, khiến người dùng phải mất nhiều thời gian để đọc nội dung của từng tài liệu nhằm tìm thông tin mà họ quan tâm; thứ hai là vấn đề tìm kiếm theo trọng số của từ khoá, ví dụ nếu người dùng đưa ra truy vấn “software engineering” với mong muốn rằng từ “software” có ưu tiên cao hơn từ “engineering” thì nhiều khi không nhận được kết quả như ý; thứ ba là vấn đề sắp xếp các tài liệu trả về theo độ liên quan với truy vấn. Ngày càng nhiều tổ chức và cá nhân có nhu cầu tìm kiếm thông tin trong tập dữ liệu đặt trên một máy tính hoặc một mạng máy tính. Yêu cầu đặt ra là cần có những hệ thống truy xuất thông tin chạy trên Desktop với hiệu quả và độ chính xác cao. Trong luận văn này, chúng tôi tập trung nghiên cứu cơ sở lý thuyết truy xuất thông tin và xây dựng thử nghiệm một hệ thống truy xuất thông tin cho phép tìm kiếm các tài liệu mang nội dung tiếng Trần Thị Hoàng Thảo Luận văn thạc sĩ 9 Truy xuất thông tin Anh chứa trong một máy tính. Hệ thống được xây dựng dựa trên thư viện mã nguồn mở truy xuất thông tin Lucene. Nội dung luận văn gồm 5 chương : • Chương 1: trình bày tổng quan về truy xuất thông tin, các bước cần thực hiện trong quá trình truy xuất thông tin, các phương pháp đánh giá hiệu quả truy xuất thông tin và so sánh một số hệ thống truy xuất thông tin trên thế giới. • Chương 2: trình bày các công cụ truy xuất thông tin quan trọng là lập chỉ mục và sắp xếp kết quả tìm kiếm. • Chương 3: giới thiệu và trình bày cơ chế lập chỉ mục và tìm kiếm của thư viện mã nguồn mở Lucene. • Chương 4: trình bày kiến trúc hoạt động của chương trình và kết quả thực nghiệm. • Chương 5: kết luận và hướng phát triển tiếp theo của luận văn. Trần Thị Hoàng Thảo Luận văn thạc sĩ 10 Truy xuất thông tin CHƯƠNG 1. TỔNG QUAN VỀ TRUY XUẤT THÔNG TIN Mục đích của chương này là giới thiệu tóm tắt về vấn đề truy xuất thông tin: 9 Truy xuất thông tin là gì? 9 Các bước thực hiện trong quá trình truy xuất thông tin 9 Các phương pháp đánh giá hiệu quả truy xuất 9 So sánh một số hệ thống truy xuất thông tin 1.1. Khái niệm truy xuất thông tin Thuật ngữ truy xuất thông tin (Information Retrieval – IR), phát biểu bởi Rijsbergen [12] , thường được định nghĩa một cách rộng và không chặt chẽ. Do vậy, thường có sự nhập nhằng giữa các lĩnh vực truy xuất dữ liệu (data retrieval), truy xuất tài liệu (document retrieval), truy xuất thông tin và truy xuất văn bản (text retrieval). Một định nghĩa đây đủ, dễ hiểu, tránh được sự nhầm lẫn đó được đưa ra bởi Lancaster [19] : Một hệ thống truy xuất thông tin không cho người dùng biết (ví dụ như thay đổi tri thức của người dùng) về chủ đề mà họ yêu cầu. Nó chỉ đơn thuần cho biết sự tồn tại (hoặc không tồn tại) và vị trí của các tài liệu có liên quan tới yêu cầu của người dùng. Trong thực tế nghiên cứu, có thể định nghĩa truy xuất thông tin như sau [7] : Truy xuất thông tin là việc tìm kiếm tài liệu ở trạng thái phi cấu trúc (thường là văn bản) thoả mãn một nhu cầu thông tin nào đó từ các tập hợp lớn (thường là trên các máy chủ cục bộ hoặc trên mạng). Hành động đó xác định rõ cốt lõi của IR. Hàng ngày, có hàng trăm triệu người thực hiện truy xuất thông tin mỗi khi họ sử dụng một máy tìm kiếm web hoặc tìm kiếm trong hộp thư điện tử của mình. IR đang nhanh chóng trở thành hình thức truy nhập thông tin vượt trội, vượt qua dạng tìm kiếm kiểu cơ sở dữ liệu truyền thống. IR là lĩnh vực khoa học máy tính chuyên về lý thuyết và thực hành việc tìm kiếm thông tin. Do văn bản là phương tiện phổ biến nhất được sử dụng để Trần Thị Hoàng Thảo Luận văn thạc sĩ 11 Truy xuất thông tin biểu diễn và phân bố thông tin một cách hiệu quả, hầu hết các nghiên cứu IR đều tập trung vào việc tìm kiếm trong các tập hợp tài liệu dạng văn bản. Như hàm ý của thuật ngữ IR, nhiệm vụ chính của IR là tìm kiếm thông tin thoả mãn nhu cầu thông tin của người dùng. Người sử dụng của một hệ thống IR quan tâm nhiều tới việc thu nhận thông tin về một chủ đề hơn là thu thập dữ liệu phù hợp với một câu truy vấn cho trước. Trái lại, truy xuất dữ liệu chỉ nhằm mục tiêu cung cấp các tập hợp thông tin "vừa khít" với các từ khoá của một câu truy vấn. IR có lịch sử lâu dài giống như lịch sử của việc lưu trữ thông tin, vào khoảng 4000 năm. Cùng với sự phát triển của lượng thông tin được lưu trữ, con người phải phát triển ngày càng nhiều phương thức để tổ chức lượng thông tin đó để phục vụ cho việc truy xuất về sau. Quá trình phát triển đó được tóm lược như dưới đây [14] . Phương pháp đầu tiên là hệ thống bảng chữ cái. Các tài liệu cần được sắp xếp theo cách này, khi mà số lượng tác phẩm văn học Hy Lạp tăng lên buộc các thủ thư của thư viện Alexandria phải nghĩ ra một cách tổ chức các tác phẩm, vào thế kỷ thứ 3 trước Công nguyên. Mục lục là một ví dụ khác về các công cụ ban đầu của IR, nó trở nên thiết yếu khi mà các tác phẩm văn học gia tăng theo số lượng trang. Một ví dụ khác về IR thủa ban đầu là chỉ mục (index). Danh mục đầu tiên là những mảnh giấy da dê nhỏ, chứa đầu đề (title) và đôi khi tác giả của tác phẩm. Trong khoảng 20 năm cuối thế kỷ 20, lĩnh vực IR phát triển tốt dựa trên những mục đích cơ bản của nó là lập chỉ mục văn bản và tìm kiếm các tài liệu có ích trong một tập hợp. Ngày nay, nghiên cứu trong IR bao gồm việc mô hình hóa, phân loại văn bản, kiến trúc hệ thống, giao diện người dùng, trực quan hóa dữ liệu, lọc, ngôn ngữ… Một trong những dạng IR ban đầu là Memex được mô tả bởi Vanevar Bush. Ngoài ra còn có kết quả của Warren Weaver. Warren Weaver tập trung vào việc xử lý ngôn ngữ, coi đó là nền tảng của IR. Hơn nữa, sự phát triển của IR hiện đại được củng cố cùng sự phát triển của Trí tuệ nhân tạo. Trong khi chờ đợi, Trí tuệ nhân tạo chỉ được sử dụng trong một số phần của IR. Thuật Trần Thị Hoàng Thảo Luận văn thạc sĩ 12 Truy xuất thông tin ngữ IR được Moer đặt ra vào năm 1952. Các hệ thống thương mại đầu tiên được phát triển từ năm 1975 trở về sau. Chúng được sử dụng chủ yếu trong các thư viện. Cuối cùng, kể từ năm 1993, IR được phổ biến rộng rãi nhờ vào sự phát triển và tầm quan trọng ngày càng lớn của World Wide Web. Sự phát triển của World Wide Web dẫn đến sự gia tăng khổng lồ về số lượng các tài liệu, đòi hỏi phải có những kỹ thuật IR hiệu quả. Trước khi xuất hiện World Wide Web, hầu hết các hệ thống lưu trữ và truy xuất thông tin đều được sử dụng riêng bởi những người lập chỉ mục và tìm kiếm chuyên nghiệp. Thông thường, những người tìm kiếm chuyên nghiệp hoạt động như những “phương tiện tìm kiếm trung gian” cho các người dùng cuối hoặc các khác hàng. Họ cố gắng tìm hiểu trong một cuộc đối thoại tương tác với hệ thống và khách hàng xem nhu cầu của khách hàng là gì và thông tin này nên được sử dụng như thế nào để tìm kiếm thành công. Những người dùng chuyên nghiệp khác với người dùng không chuyên bởi họ biết về tập hợp tài liệu, họ biết cách thức các tài liệu được biểu diễn trong hệ thống và họ biết cách sử dụng các toán tử tìm kiếm Boolean để giới hạn số lượng tài liệu được thu thập. Nhiều hệ thống IR hiện đại được thiết kế cho những người dùng không biết rõ về tập hợp tài liệu, sự biểu diễn của các tài liệu và cách sử dụng các toán tử Boolean. Những hệ thống như vậy cần đáp ứng những yêu cầu chính sau đây. Thứ nhất, người dùng có thể nhập (các) câu, (các) cụm từ, (các) từ vào hệ thống mà không cần phải nhập các toán tử. Điều này thường được hiểu là một hệ thống IR toàn văn bản (full text), hệ thống này tự động lập chỉ mục tất cả các từ trong một tài liệu. Thứ hai, hệ thống có thể xếp hạng các tài liệu thu thập được bằng cách đánh giá mức độ hoặc khả năng có ích đối với người dùng. Thứ ba, hệ thống có thể hỗ trợ việc tự động biến đổi câu lệnh tìm kiếm theo phản hồi của người dùng. Yêu cầu thứ ba có thể không quan trọng như hai yêu cầu kia. Một hệ thống IR là một chương trình phần mềm lưu trữ và quản lý thông tin về các tài liệu. Hệ thống trợ giúp người dùng tìm kiếm thông tin họ cần. Nó cho biết về sự tồn tại và vị trí của các tài liệu có thể chứa thông tin Trần Thị Hoàng Thảo Luận văn thạc sĩ 13 Truy xuất thông tin cần thiết. Có thể một số tài liệu được đề xuất sẽ thoả mãn nhu cầu thông tin của người dùng. Những tài liệu đó được gọi là các tài liệu có liên quan. Một hệ thống IR hoàn hảo sẽ chỉ thu thập những tài liệu có liên quan và bỏ qua những tài liệu không liên quan. Tuy nhiên, sẽ không thể tồn tại những hệ thống như vậy bởi các câu lệnh tìm kiếm thường không đầy đủ và độ liên quan (relevance) phụ thuộc vào ý kiến chủ quan của người dùng. Hai người dùng có thể đưa ra cùng truy vấn giống nhau cho một hệ thống IR nhưng lại có cách đánh giá độ liên quan khác nhau đối với các tài liệu được thu thập. Hệ thống IR theo một nghĩa nào đó, phải “thông dịch” nội dung của các phần tử thông tin (các tài liệu) trong một tập hợp và xếp hạng chúng theo mức độ liên quan tới câu truy vấn của người dùng. Việc “thông dịch” một nội dung tài liệu bao gồm việc chắt lọc thông tin cú pháp và ngữ nghĩa từ văn bản tài liệu và sử dụng thông tin này để đối sánh với yêu cầu thông tin của người dùng. Khó khăn không chỉ là việc phải biết cách chắt lọc thông tin mà còn là phải biết cách sử dụng nó để lựa chọn độ liên quan. Do đó, quan điểm về độ liên quan là trọng tâm của IR. Thực tế, mục tiêu chính của một hệ thống IR là thu thập tất cả các tài liệu có liên quan tới một truy vấn của người dùng đồng thời thu thập ít nhất có thể các tài liệu không liên quan [1] . 1.2. Quá trình truy xuất thông tin User Interface Text User Need User Feedback Query Text Operations Logical View Query Operations Searching Indexing Index Database Manager Inverted file Text Database Ranked Docs Ranking Retrieved Docs Hình 1-1 Quy trình truy xuất thông tin nói chung (nguồn: [1] ) Trần Thị Hoàng Thảo Luận văn thạc sĩ 14 Truy xuất thông tin Quá trình truy xuất thông tin diễn ra theo nhiều giai đoạn. Hình 1-1 thể hiện mô hình hệ thống truy xuất thông tin nói chung, được đưa ra bởi Baeza và cộng sự [1] . Trước khi bắt đầu quá trình thu thập, cần xác định cơ sở dữ liệu văn bản (text database): tập tài liệu được sử dụng, các thao tác được thực hiện trên văn bản và mô hình văn bản (ví dụ như cấu trúc văn bản và những phần tử có thể được thu thập). Các thao tác văn bản (text operation) biến đổi các tài liệu ban đầu và sinh ra một khung nhìn lôgíc (logical view) của chúng. Tiếp theo là quá trình xây dựng chỉ mục (indexing) cho văn bản nhằm tăng tốc độ truy nhập trong giai đoạn truy xuất. Có nhiều loại cấu trúc chỉ mục nhưng phổ biến nhất là Inverted Files. Khi tập tài liệu đã được đánh chỉ mục, có thể bắt đầu quá trình thu thập. Đầu tiên, người sử dụng xác định yêu cầu của mình (user need), yêu cầu này sẽ được phân tích (parse) và biến đổi (transformed) bằng các thao tác xử lý đã được áp dụng đối với văn bản. Tiếp theo, các thao tác truy vấn (query operations) có thể được áp dụng để tạo nên truy vấn thật sự. Sau đó, truy vấn được xử lý (searching) để nhận được các tài liệu được thu thập (retrieved documents). Trước khi chuyển tới người dùng, các tài liệu thu thập được sẽ được xếp hạng (ranking) theo mức độ liên quan (likelihood relevance). Khi nhận được, người dùng có thể đánh dấu một tập con các tài liệu thực sự đáng quan tâm và khi đó sẽ khởi đầu một chu trình phản hồi của người dùng (relevance feedback). Trong chu trình như vậy, hệ thống sử dụng các tài liệu được chọn bởi người dùng để cải thiện đổi công thức truy vấn. Truy vấn đã được biến đổi này sẽ biểu diễn tốt hơn nhu cầu thực sự của người dùng. Tóm lại, trong quá trình truy vấn, hệ thống IR chắt lọc các phần thông tin có thể sẽ đáp ứng được nhu cầu thông tin được phát biểu bởi người dùng. Trần Thị Hoàng Thảo Luận văn thạc sĩ 15 Truy xuất thông tin Quá trình này thường được chia thành hai giai đoạn, tiền xử lý (preprocessing) và thu thập (retrieval). Giai đoạn truy xuất có thể lặp đi lặp lại nếu như người dùng muốn tinh chỉnh các kết quả truy xuất. 1.2.1. Giai đoạn tiền xử lý 1.2.1.1. Tiền xử lý tài liệu Trong giai đoạn tiền xử lý, hệ thống IR tạo ra biểu diễn bên trong của thông tin trong từng tài liệu thông qua quy trình đánh chỉ mục. Trước hết, tập tài liệu văn bản được tiền xử lý bằng một số phương pháp thao tác văn bản tự động như phân tích từ vựng (lexical analysis), loại bỏ từ dừng (stopword removing), lấy gốc từ (stemming) từ dạng văn bản đơn giản (plain text) của tài liệu. Kết quả nhận được là tập các từ (term) hay còn được hiểu là các khái niệm (concept), được coi là khung nhìn lôgíc (logical view [1] ) của tài liệu. Hình 1-2 Khung nhìn lôgíc của tài liệu thông qua các giai đoạn tiền xử lý (nguồn: [1] ) Trong luận văn này, chúng tôi sẽ dùng thuật ngữ tiếng Anh “term” để nói tới “từ” nhằm phân biệt với các thuật ngữ khác. Một term có thể là một Trần Thị Hoàng Thảo Luận văn thạc sĩ 16 Truy xuất thông tin từ (word), nhưng cũng có thể là một gốc từ (stem), một cụm danh từ hoặc một cụm từ (phrase). Gốc từ là một từ được rút gọn thành gốc của nó sau khi loại bỏ các phụ tố: ví dụ, ‘system2’ và ‘component_123’ sẽ trở thành ‘system’ và ‘component’ sau bước lấy gốc từ. Giả thiết cơ bản (đôi khi bị nghi ngờ) nằm sau việc lấy gốc từ là không có sự khác biệt đáng kể về ý nghĩa giữa các từ có chung một gốc. Một cụm từ chứa ít nhất hai từ liên tiếp có nghĩa rõ ràng, ví dụ ‘office application’ hoặc ‘Hanoi University of Technology’. Nếu có thể, những từ khóa (keyword) được chỉ định một cách thủ công, mô tả nội dung của tài liệu cũng có thể được dùng cho việc lập chỉ mục (ví dụ Google). Phân tích từ vựng Là quá trình biến đổi các ký tự trong tài liệu thành một tập các từ được đề cử để chọn làm từ chỉ mục bằng cách xử lý các chữ số, dấu nối, các ký hiệu chấm câu và chữ viết hoa viết thường. CHAPTER 1 PREAMBLE 1.1 Humanity stands at a defining moment history. We are confronted with a perpetuation of disparities between and within nations, a worsening of poverty, hunger, ill health and illiteracy, and the continuing deterioration of the ecosystem on which we depend for out well-being. Hình 1-3 Văn bản A ban đầu chapter 1 preamble 1 1 humanity stands at a defining moment history we are confronted with a perpetuation of disparities between and within nations a worsening of poverty hunger ill health and illiteracy and the Hình 1-4 Văn bản A sau khi phân tích Bước đầu tiên là lọc ra các ký tự không mong muốn và ký hiệu (các thẻ HTML, dấu chấm câu, các con số…). Tiếp theo, văn bản cần được chia thành Trần Thị Hoàng Thảo Luận văn thạc sĩ 17 Truy xuất thông tin các thẻ (token, còn gọi là từ khóa) sử dụng khoảng trắng phân tách và các ký tự kết thúc câu. Việc này không đơn giản vì các từ trong các văn bản không phải lúc nào cũng được phân tách rõ ràng (ví dụ, nếu văn bản là I can’t go thì có thể xem dấu nháy là một dấu phân tách từ để có hai từ là can và t, hoặc có thể không coi nó là dấu phân tách và xem là một từ can’t, hoặc có thể mở rộng dạng liên kết thành hai từ can và not và sử dụng khoảng trắng để phân tách. Loại bỏ từ dừng Việc loại bỏ từ dừng có ý nghĩa làm giảm kích cỡ của cấu trúc chỉ mục. Đây là bước tiền xử lý nhằm loại bỏ những từ có tần suất xuất hiện cao trong hầu hết các tài liệu mà lại không mang nội dung có ý nghĩa. Những từ như vậy được gọi là từ dừng (stopword), bao gồm các mạo từ, giới từ, liên từ, chẳng hạn như a, the. It, of, could… Một ví dụ về danh sách các từ dừng trong tiếng Anh có tại: http://www.lextek.com/manuals/onix/stopwords1.html. chapter 1 preamble 1 1 humanity stands defining moment history confronted perpetuation disparities nations worsening poverty hunger ill health illiteracy continuing deterioration ecosystem depend well being Hình 1-5 Văn bản A sau khi loại các từ trong danh sách stopword của Smart Quá trình loại bỏ từ dừng có thể được chia thành hai loại : • Từ cần loại bỏ nằm trong danh sách từ dừng, quá trình này sẽ được thực hiện trong phần nhận dạng từ, có nghĩa là từ này sẽ không thể đi qua bộ nhận dạng từ và vì thế chúng không được lập chỉ mục. • Từ cần loại bỏ không nằm trong danh sách từ dừng nhưng nó xảy ra quá thường xuyên trong tập tài liệu của ta (từ quá thường xuyên ở đây có nghĩa là nó xuất hiện vượt quá một ngưỡng qui định của ta, ví dụ như có mặt trên 80% số lượng File, hoặc trên 200 file), quá trình này Trần Thị Hoàng Thảo Luận văn thạc sĩ 18 Truy xuất thông tin được thực hiện sau khi ta đã lập chỉ mục song toàn bộ tài liệu và bảng chỉ mục đang được lưu trong bộ đệm bộ nhớ chính. Khi đó ta thực hiện việc duyệt trên bảng băm để tìm các từ dừng, thêm chúng vào danh sách danh sách từ dừng và loại phần tử chứa từ đó khỏi bảng băm. Lấy gốc từ Lấy gốc từ là quá trình thu gọn một từ về dạng ngữ pháp gốc của nó. Nhằm xác định và nhóm các từ có chung ngữ nghĩa sao cho người dùng không phải xác định quá cụ thể trong truy vấn. Ví dụ: computes, computing, computer có gốc là comput . chapter 1 preambl 1 1 human stand defin moment histori confront perpetu dispar nation worsen poverti hunger ill health and illiteraci continu deterior ecosystem depend well be Hình 1-6 Văn bản A sau khi lấy gốc từ Việc lấy gốc từ trước khi xây dựng chỉ mục có ưu điểm là làm giảm kích thước chỉ mục và cho phép truy xuất các tài liệu với nhiều dạng biến tố của cùng một từ (ví dụ, khi tìm kiếm với từ computation, kết quả sẽ bao gồm các tài liệu có chứa từ computations và computing ). Một phương pháp lấy gốc từ nhanh và phổ biến là giải thuật của Porter (1980), giải thuật này áp dụng tập các quy tắc đối với hậu tố của một từ nhằm loại bỏ nó. Như vậy, giai đoạn tiền xử lý tài liệu tập trung vào việc chắt lọc tập các khái niệm mô tả cho từng tài liệu. Các khái niệm đó thường được gán trọng số riêng, thể hiện độ liên quan của chúng đối với chủ đề của tài liệu. Thông thường, nếu một term xuất hiện càng nhiều lần trong một tài liệu và ít xuất hiện hơn trong các tài liệu khác của tập hợp thì nó càng là ký hiệu mô tả tốt hơn cho tài liệu đó. Những tiêu chí khác như vị trí của từ khóa, phần lôgíc mà Trần Thị Hoàng Thảo Luận văn thạc sĩ 19 Truy xuất thông tin từ đó nó đã được chắt lọc hoặc độ dài của tài liệu có thể được dùng để tính toán trọng số của khái niệm liên quan trong tài liệu. 1.2.1.2. Lập chỉ mục Bước lập chỉ mục sử dụng các term mô tả khung nhìn lôgíc của các tài liệu để xây dựng chỉ mục. Như trên đã nêu, cấu trúc chỉ mục phổ biến nhất là Inverted Files, trong đó tập tài liệu được biến đổi thành một tập các term kèm theo một danh sách tương ứng các tài liệu mà chúng xuất hiện. Trong một Inverted File, mỗi term trỏ tới một danh sách tất cả các tài liệu mà nó xuất hiện. Cấu trúc chỉ mục như vậy đóng vai trò rất quan trọng vì nó "cho phép tìm kiếm nhanh trên tập dữ liệu lớn" [1] . Quy trình này có thể được thực hiện thủ công (đòi hỏi sức người nên rất tốn kém) hoặc tự động bằng cách tách các term từ văn bản của phần tử thông tin, sử dụng một thủ tục dựa trên thông kê hoặc ngôn ngữ. Một số term có thể biểu diễn tốt hơn chủ đề của tài liệu. Do đó, mỗi term có thể được gán một trọng số thể hiện tầm quan trọng của nó trong tài liệu. Như vậy, cấu trúc chỉ mục bao gồm một tập các term đã được xử lý, kèm theo một danh sách các tài liệu chứa chúng và trọng số của chúng. Trọng số của một term trong một tài liệu có thể chỉ đơn giản là số lần xuất hiện của chúng trong tài liệu. Tần số càng lớn thì tầm quan trọng của nó càng lớn. Điều này được gọi là gán trọng số theo tần số từ (term frequency weighting – tf). Số lượng tài liệu mà một term xuất hiện trong đó cũng có thể được sử dụng làm yếu tố trong việc gán trọng số. Một term xuất hiện trong càng nhiều tài liệu thì khả năng phân biệt của nó đối với càng tài liệu càng kém. Điều này gọi là tần số tài liệu đảo ngược (inverse document frequency – idf). Lược đồ gán trọng số tf-idf được sử dụng phổ biến trong các hệ thống truy xuất văn bản. Trần Thị Hoàng Thảo Luận văn thạc sĩ 20 Truy xuất thông tin 1.2.2. Giai đoạn thu thập 1.2.2.1. Xử lý truy vấn Nhu cầu thông tin của người dùng được phát biểu bằng một yêu cầu (request), là đầu vào của hệ thống IR. Một yêu cầu có thể được viết ở dạng ngôn ngữ tự nhiên, là một tập các từ khóa với từ vựng giới hạn, hoặc có thể được phát biểu với các toán tử Boolean. Bước lấy yêu cầu là bước quan trọng trong quá trình truy xuất. Hệ thống IR có cách biểu diễn bên trong của riêng nó đối với yêu cầu. Ở bước đầu trong giai đoạn truy xuất, hệ thống IR thực hiện các thao tác xử lý đối với truy vấn của người dùng tương tự như đối với các tài liệu ban đầu trong quá trình tiền xử lý. Các thao tác xử lý văn bản là những phương thức chính được dùng để biểu diễn những nhu cầu của người dùng, và đây là điểm khác biệt chủ yếu của truy xuất thông tin với truy xuất dữ liệu (trong truy xuất dữ liệu không có thao tác xử lý lôgíc đối với truy vấn ban đầu trước khi thực hiện tìm kiếm). Kết quả nhận được là một danh sách các từ, đó chính là biểu diễn bên trong của nhu cầu thông tin của người dùng. 1.2.2.2. Tìm kiếm Trong giai đoạn tìm kiếm, mỗi term thu được từ thao tác xử lý văn bản được dùng để xác định, thông qua tập chỉ mục, một danh sách các tài liệu mà trong đó nó xuất hiện. Nếu có nhiều từ xuất hiện trong truy vấn thì bước tìm kiếm sẽ trả về hợp của các tài liệu thu thập được theo tất cả các từ hoặc một số từ, tùy theo kiểu truy vấn. Tóm lại, tìm kiếm là quá trình đối sánh (matching) các term trong các tài liệu với các term trong truy vấn. Cụ thể, hệ thống IR thực hiện đối sánh giữa truy vấn với từng biểu diễn của tài liệu để đánh giá độ liên quan của nó với nhu cầu thông tin. Kết quả đối sánh có thể là phù hợp tuyệt đối hoặc một phần, nhưng do tính không rõ ràng vốn có của quá trình truy xuất nên phù hợp một phần ngày càng được ưa Trần Thị Hoàng Thảo Luận văn thạc sĩ