Tìm kiếm và trình diễn thông tin

(IT4853) Tìm kiếm và trình diễn thông tin Các khái niệm cơ bản, phương pháp Boolean, chỉ mục ngược Giảng viên  TS. Nguyễn Bá Ngọc  Địa chỉ: Viện CNTT & TT/BM HTTT/B1-603  Email: ngocnb@soict.hust.edu.vn  Website: Tìm kiếm thông tin là gì? Nếu không giới hạn các dạng thể hiện của thông tin cũng như những đối tượng chứa thông tin, thì tìm kiếm thông tin là một khái niệm vô cùng rộng lớn, khó có thể bao quát hết được trong phạm vi một học phần. Đặt ra một giả thiết rằng những gì có thể biết đều đã được mô tả dưới dạng văn bản số và được lưu trữ trên các hệ thống máy tính. Trong giới hạn đó, tìm kiếm thông tin là tìm kiếm các văn bản chứa những thông tin hữu ích nhằm đáp ứng nhu cầu thông tin của người dùng. Trong định nghĩa này, văn bản có thể là văn bản phi cấu trúc hoặc có cấu trúc. Thuật ngữ tiếng Anh là Information Retrieval. Tìm kiếm vs. phản hồi thông tin Nếu xét trên khía cạnh tương tác người-máy, thì tìm kiếm thông tin là một quá trình tương tác. Trong quá trình tương tác này, người dùng là người đi tìm, còn máy tính phản hồi lại những thông tin có thể đáp ứng nhu cầu đó. Hành động đầu tiên trong quá trình tương tác này được thực hiện bởi người dùng. Trước khi có thể phản hồi kết quả, hệ thống phải thực hiện tìm kiếm. Những định hướng mang tính lịch sử  Memex được mô tả là một thiết bị có thể lưu trữ sách điện tử, nhật ký, và những thông tin cá nhân khác. Đây là một thiết bị cơ khí nhỏ gọn, có giao diện cực kỳ đơn giản và hoạt động với tốc độ rất cao. Thiết bị này giống như phần mở rộng cho bộ nhớ của con người. Vannevar Bush, As we may think, Atlantic monthly, tháng 7 năm 1945.  Sứ mệnh của Google là tổ chức thông tin toàn thế giới và làm cho nó trở nên phổ cập và hữu ích. Larry Page, Sergey Brin, Google’s mission statement, ~1998. Mô hình tìm kiếm thông tin  Nền tảng lý thuyết để xây dựng công cụ tìm kiếm  Là cơ sở để giải thích hành vi của hệ thống Mô hình tìm kiếm thông tin Các thành phần cơ bản của một mô hình tìm kiếm:  D: Tập biểu diễn logic văn bản.  Biểu diễn logic đôi khi còn được gọi là mô hình văn bản.  Q: Tập truy vấn  Truy vấn được coi như mô hình của nhu cầu thông tin  F: Cơ sở lý thuyết để định nghĩa D, Q và so sánh các biểu diễn logic của văn bản và nhu cầu thông tin.  Lý thuyết tập hợp, đại số, xác suất,...  R(d, q): Hàm xếp hạng, định lượng mức độ phù hợp giữa văn bản và nhu cầu thông tin. Mô hình Boolean  Phương pháp tìm kiếm phổ biến nhất khoảng 3 thập kỷ trước  Hiện nay vẫn được sử dụng trong nhiều hệ thống  Vd, Thư viện số  nhiều TB dữ liệu, > 700 000 người dùng Mô hình Boolean D: Văn bản được biểu diễn dưới dạng tập từ xuất hiện trong văn bản đó Q: Biểu thức Boolean trên từ +) Ràng buộc sự xuất hiện của từ trong văn bản F: Lý thuyết tập hợp, đại số Boolean R: Một văn bản phù hợp nếu nó thỏa mãn biểu thức truy vấn Ví dụ phù hợp Boolean Truy vấn: ((văn bản ˅ thông tin) ˄ tìm kiếm ˄ ¬lý thuyết) Văn bản:  “Tìm kiếm thông tin  “Lý thuyết thông tin”  “Tìm kiếm thông tin hiện đại: lý thuyết và thực hành”  “Phương pháp nén văn bản” Ví dụ phù hợp Boolean Truy vấn: ((văn bản ˅ thông tin) ˄ tìm kiếm ˄ ¬lý thuyết) Văn bản:  “Tìm kiếm thông tin  “Lý thuyết thông tin”  “Tìm kiếm thông tin hiện đại: lý thuyết và thực hành”  “Phương pháp nén văn bản” Giải pháp cho dữ liệu nhỏ  Kiểm tra tuần tự tất cả văn bản:  Đơn giản, nhưng  Bất khả thi với bộ dữ liệu lớn Ý tưởng sử dụng chỉ mục  1: từ xuất hiện trong văn bản; 0: từ không xuất hiện. Xử lý truy vấn trên ma trận đánh dấu  Xử lý các truy vấn Boolean có thể quy về thực hiện phép toán logic theo bit:  Ví dụ, truy vấn a AND b AND NOT d được thực hiện như sau:  1101001 AND  1001101 AND  1011010 =  1001000  Nhanh hơn kiểm tra tuần tự, nhưng sẽ cần rất nhiều bộ nhớ. Cấu trúc dữ liệu chỉ mục ngược  Chỉ mục ngược là cấu trúc dữ liệu hỗ trợ tìm kiếm phổ biến nhất  Nếu chỉ lưu các giá trị 1 trong ma trận đánh dấu, thì chúng ta sẽ thu được một dạng chỉ mục ngược.  Trong thực tế có nhiều loại chỉ mục ngược khác nhau, được phân biệt bởi các dữ liệu lưu trữ trong đó. Cấu trúc chỉ mục ngược Cấu trúc chỉ mục ngược  Mỗi từ trong chỉ mục ngược được liên kết với một danh sách chứa thông tin về những văn bản sử dụng từ này. Mỗi phần tử của danh sách lưu thông tin ứng với một văn bản (ví dụ, mã văn bản, các vị trí, v.v.), có vai trò hỗ trợ xác định vị trí xuất hiện của một từ, vì vậy được gọi là thẻ định vị (posting). Tương ứng, danh sách gắn với mỗi từ được gọi là danh sách thẻ định vị (hoặc danh sách ngược), và tất cả các thẻ định vị gộp lại được gọi là bộ thẻ định vị. Các bước cơ bản để xây dựng chỉ mục ngược  Tách từ→ Sinh thẻ định vị → Sắp xếp thẻ định vị → Tổng hợp danh sách thẻ định vị → Lưu bộ từ vựng và bộ thẻ định vị Ví dụ xây dựng chỉ mục ngược  D1. “Dế mèn phiêu lưu kí" là tác phẩm văn xuôi đặc sắc và nổi tiếng nhất của Tô Hoài viết về loài vật, dành cho lứa tuổi thiếu nhi  D2. Tô Hoài (sinh ngày 27 tháng 9 năm 1920) là một nhà văn Việt Nam nổi tiếng. Một số tác phẩm đề tài thiếu nhi của ông được dịch ra ngoại ngữ.  D1. Dế mèn phiêu lưu kí, là, tác phẩm, văn xuôi, đặc sắc, và, nổi tiếng nhất, của, Tô Hoài, viết về, loài vật, dành cho, lứa tuổi thiếu nhi  D2. Tô Hoài, sinh, ngày 27 tháng 9 năm 1920, là, một, nhà văn, Việt Nam, nổi tiếng, Một số, tác phẩm, đề tài, thiếu nhi, của, ông, được, dịch, ra, ngoại ngữ Tách từ  D1. Dế mèn phiêu lưu kí, là, tác phẩm, văn xuôi, đặc sắc, và, nổi tiếng nhất, của, Tô Hoài, viết về, loài vật, dành cho, lứa tuổi thiếu nhi  D2. Tô Hoài, sinh, ngày 27 tháng 9 năm 1920, là, một, nhà văn, Việt Nam, nổi tiếng, Một số, tác phẩm, đề tài, thiếu nhi, của, ông, được, dịch, ra, ngoại ngữ Từ Mã văn bản DMPLK 1 là 1 tác phẩm 1 văn xuôi 1 đặc sắc 1 và 1 nổi tiếng nhất 1 của 1 Tô Hoài 1 viết về 1 loài vật 1 dành cho 1 lứa tuổi thiếu nhi 1 Tô Hoài 2 sinh 2 27-9-1920 2 là 2 một 2 nhà văn 2 Việt Nam 2 nổi tiếng 2 Một số 2 tác phẩm 2 đề tài 2 thiếu nhi 2 của 2 ông 2 được 2 dịch 2 ra 2 ngoại ngữ 2 *DMPLK: Dế mèn phiêu lưu kí 27-9-1920: ngày 27 tháng 9 năm 1920 Sinh thẻ định vị Từ Mã văn bản DMPLK 1 là 1 tác phẩm 1 văn xuôi 1 đặc sắc 1 và 1 nổi tiếng nhất 1 của 1 Tô Hoài 1 viết về 1 loài vật 1 dành cho 1 lứa tuổi thiếu nhi 1 Tô Hoài 2 sinh 2 27-9-1920 2 là 2 một 2 nhà văn 2 Việt Nam 2 nổi tiếng 2 Một số 2 tác phẩm 2 đề tài 2 thiếu nhi 2 của 2 ông 2 được 2 dịch 2 ra 2 ngoại ngữ 2 Từ Mã văn bản DMPLK 1 27-9-1920 2 của 1 của 2 đặc sắc 1 dành cho 1 đề tài 2 dịch 2 được 2 là 1 là 2 loài vật 1 lứa tuổi thiếu nhi 1 một 2 Một số 2 ngoại ngữ 2 nhà văn 2 nổi tiếng 2 nổi tiếng nhất 1 ông 2 ra 2 sinh 2 tác phẩm 1 tác phẩm 2 thiếu nhi 2 Tô Hoài 1 Tô Hoài 2 và 1 văn xuôi 1 Việt Nam 2 viết về 1 Sắp xếp Từ Mã văn bản DMPLK 1 27-9-1920 2 của 1 của 2 đặc sắc 1 dành cho 1 đề tài 2 dịch 2 được 2 là 1 là 2 loài vật 1 lứa tuổi thiếu nhi 1 một 2 Một số 2 ngoại ngữ 2 nhà văn 2 nổi tiếng 2 nổi tiếng nhất 1 ông 2 ra 2 sinh 2 tác phẩm 1 tác phẩm 2 thiếu nhi 2 Tô Hoài 1 Tô Hoài 2 và 1 văn xuôi 1 Việt Nam 2 viết về 1 Từ , tần suất vb danh sách thẻ vị trí DMPLK, 1 → 1 27-9-1920, 1 → 2 của, 2 → 1, 2 đặc sắc, 1 → 1 dành cho, 1 → 1 đề tài, 1 → 2 dịch, 1 → 2 được, 1 → 2 là, 2 → 1, 2 loài vật, 1 → 1 lứa tuổi thiếu nhi, 1 → 1 một, 1 → 2 Một số, 1 → 2 ngoại ngữ, 1 → 2 nhà văn, 1 → 2 nổi tiếng, 1 → 2 nổi tiếng nhất, 1 → 1 ông, 1 → 2 ra, 1 → 2 sinh, 1 → 2 tác phẩm, 2 → 1, 2 thiếu nhi,1 → 2 Tô Hoài, 2 → 1, 2 và, 1 → 1 văn xuôi, 1 → 1 Việt Nam, 1 → 2 viết về, 1 → 1 Tổng hợp danh sách Lưu bộ từ vựng và bộ thẻ định vị  Bộ từ vựng và bộ thẻ định vị thường được tách rời và lưu trữ riêng rẽ vì những lý do kỹ thuật.