Bài giảng Tìm kiếm và trình diễn thông tin - Nguyễn Bá Ngọc

Nội dung text: Bài giảng Tìm kiếm và trình diễn thông tin - Nguyễn Bá Ngọc

1. (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
2. 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:
3. 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.
4. 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.
5. 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.
6. 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
7. 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.
8. 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
9. 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
10. 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”
11. 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”
12. 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
13. Ý 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.
14. 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ớ.
15. 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 đó.
16. Cấu trúc chỉ mục ngược
17. 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ị.
18. 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ị
19. Ví dụ xây dựng chỉ mục ngược  D1. “Dế mèn phiêu lưu kí" là  D1. Dế mèn phiêu lưu kí, là, tác phẩm văn xuôi đặc sắc và tác phẩm, văn xuôi, đặc sắc, nổi tiếng nhất của Tô Hoài viết và, nổi tiếng nhất, của, Tô về loài vật, dành cho lứa tuổi Hoài, viết về, loài vật, dành thiếu nhi cho, lứa tuổi thiếu nhi  D2. Tô Hoài (sinh ngày 27  D2. Tô Hoài, sinh, ngày 27 tháng 9 năm 1920) là một nhà tháng 9 năm 1920, là, một, văn Việt Nam nổi tiếng. Một số nhà văn, Việt Nam, nổi tiếng, tác phẩm đề tài thiếu nhi của Một số, tác phẩm, đề tài, thiếu ông được dịch ra ngoại ngữ. nhi, của, ông, được, dịch, ra, ngoại ngữ Tách từ
20. 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  D1. Dế mèn phiêu lưu kí, dành cho 1 là, tác phẩm, văn xuôi, Sinh thẻ lứa tuổi thiếu nhi 1 đặc sắc, và, nổi tiếng Tô Hoài 2 sinh 2 nhất, của, Tô Hoài, viết định vị 27-9-1920 2 về, loài vật, dành cho, lứa là 2 tuổi thiếu nhi một 2 nhà văn 2  D2. Tô Hoài, sinh, ngày 27 Việt Nam 2 tháng 9 năm 1920, là, nổi tiếng 2 một, nhà văn, Việt Nam, Một số 2 tác phẩm 2 nổi tiếng, Một số, tác đề tài 2 phẩm, đề tài, thiếu nhi, thiếu nhi 2 của, ông, được, dịch, ra, của 2 ngoại ngữ ông 2 được 2 dịch 2 *DMPLK: Dế mèn phiêu lưu kí ra 2 ngoại ngữ 2 27-9-1920: ngày 27 tháng 9 năm 1920
21. Từ Mã văn bản Từ Mã văn bản DMPLK 1 DMPLK 1 là 1 27-9-1920 2 tác phẩm 1 của 1 văn xuôi 1 của 2 đặc sắc 1 đặc sắc 1 và 1 dành cho 1 nổi tiếng nhất 1 đề tài 2 của 1 dịch 2 Tô Hoài 1 được 2 viết về 1 là 1 loài vật 1 là 2 dành cho 1 Sắp xếp loài vật 1 lứa tuổi thiếu nhi 1 lứa tuổi thiếu nhi 1 Tô Hoài 2 một 2 sinh 2 Một số 2 27-9-1920 2 ngoại ngữ 2 là 2 nhà văn 2 một 2 nổi tiếng 2 nhà văn 2 nổi tiếng nhất 1 Việt Nam 2 ông 2 nổi tiếng 2 ra 2 Một số 2 sinh 2 tác phẩm 2 tác phẩm 1 đề tài 2 tác phẩm 2 thiếu nhi 2 thiếu nhi 2 của 2 Tô Hoài 1 ông 2 Tô Hoài 2 được 2 và 1 dịch 2 văn xuôi 1 ra 2 Việt Nam 2 ngoại ngữ 2 viết về 1
22. Từ Mã văn bản DMPLK 1 27-9-1920 2 của 1 Từ , tần suất vb danh sách của 2 thẻ vị trí đặc sắc 1 DMPLK, 1 → 1 dành cho 1 27-9-1920, 1 → 2 đề tài 2 của, 2 → 1, 2 dịch 2 đặc sắc, 1 → 1 được 2 dành cho, 1 → 1 là 1 đề tài, 1 → 2 là 2 dịch, 1 → 2 loài vật 1 được, 1 → 2 lứa tuổi thiếu nhi 1 là, 2 → 1, 2 một 2 Tổng hợp loài vật, 1 → 1 Một số 2 danh sách lứa tuổi thiếu nhi, 1 → 1 ngoại ngữ 2 một, 1 → 2 nhà văn 2 Một số, 1 → 2 nổi tiếng 2 ngoại ngữ, 1 → 2 nổi tiếng nhất 1 nhà văn, 1 → 2 ông 2 nổi tiếng, 1 → 2 ra 2 nổi tiếng nhất, 1 → 1 sinh 2 ông, 1 → 2 tác phẩm 1 ra, 1 → 2 tác phẩm 2 sinh, 1 → 2 thiếu nhi 2 tác phẩm, 2 → 1, 2 Tô Hoài 1 thiếu nhi,1 → 2 Tô Hoài 2 Tô Hoài, 2 → 1, 2 và 1 và, 1 → 1 văn xuôi 1 văn xuôi, 1 → 1 Việt Nam 2 Việt Nam, 1 → 2 viết về 1 viết về, 1 → 1
23. 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.