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

Chia sẻ: Codon_02 Codon_02 | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

195
lượt xem 24
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mời các bạn cùng tham khảo bộ bài giảng Tìm kiếm và trình diễn thông tin do TS.Nguyễn Bá Ngọc biên soạn. Nội dung của bài 1 giới thiệu đến người học các kiến thức cơ bản về: Các khái niệm cơ bản, phương pháp Boolean, chỉ mục ngược.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

(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: http://is.hust.edu.vn/~ngocnb
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ố  http://www.westlaw.com: 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à  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ừ
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 Tô Hoài 1 2 đặc sắc, và, nổi tiếng nhất, của, Tô Hoài, viết định vị sinh 27-9-1920 2 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