Tìm kiếm và trình diễn thông tin - Ngôn ngữ truy vấn

(IT4853) Tìm kiếm và trình diễn thông tin Ngôn ngữ truy vấn 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: 2 Nội dung chính  1. Tìm kiếm trong bộ từ vựng  2. Ngôn ngữ tìm kiếm  3. Đối sánh từ khóa 3 Bộ từ vựng dạng mảng cấu trúc char[20] int Postings * 20 bytes 4/8 bytes 4/8 bytes  Tối ưu hóa lưu trữ: giảm kích thước, tăng tốc độ tìm kiếm Sec. 3.1 Từ Số lượng văn bản Con trỏ tới danh sách thẻ định vị a 3212 ---> b 35 ---> c 128 ---> ... tn 620 ---> 4 Cấu trúc dữ liệu tối ưu cho tìm kiếm  Bảng băm  Cây Sec. 3.1 5 Bảng băm  Ưu điểm:  Tốc độ tìm kiếm nhanh hơn so với cây  Nhược điểm:  Không có quan hệ thứ tự giữa các từ  Hạn chế kiểu truy vấn, vd, rất khó cài đặt phương pháp tìm kiếm với giới hạn khoảng cách trên bảng băm Sec. 3.1 6 Cây  Ưu điểm:  Thuật ngữ được sắp xếp theo thứ tự  Đơn giản hơn trong việc thực hiện nhiều loại truy vấn so với bảng băm, vd, tìm kiếm theo tiếp đầu ngữ  Nhược điểm:  Chậm hơn so với bảng băm Sec. 3.1 7 Nội dung chính  1. Tìm kiếm trong bộ từ vựng  2. Ngôn ngữ tìm kiếm  3. Đối sánh từ khóa 8 Truy vấn Boolean  Mô tả luật xuất hiện của từ trong văn bản  Các liên kết cơ bản:  OR  AND  AND NOT (hoặc BUT) 9 Ký tự đại diện  a*: Tìm tất cả từ bắt đầu với a  *a: Tìm tất cả từ kết thúc với a  a * b: Tìm tất cả từ bắt đầu với a, kết thúc với b Sec. 3.2 Xử lý ký tự đại diện trên cấu trúc cây 10 Trích đoạn  Thường được sử dụng trong trường hợp cần tìm văn bản khi đã biết một phần nội dung của văn bản  Cần phân biêt trích đoạn với một truy vấn thông thường, vd, có thể sử dụng dấu nháy kép:  “Công nghệ thông tin” 11 Giới hạn khoảng cách  Ví dụ: việc làm /4 lĩnh vực  Tìm tất cả văn bản chứa việc làm và lĩnh vực trong giới hạn khoảng cách 4 từ. 12 Tìm kiếm với giới hạn khoảng cách  Sử dụng chỉ mục có vị trí:  Từ: mã_văn_bản: ; mã_văn_bản: ; ... Ví dụ chỉ mục có vị trí: tìm_kiếm: 1: ; 2: ; 3: ; 4: . dữ_liệu: 1: ; 3: ; 4: ; 7: . thông_tin: 1: ; 2: ; 3: ; 5: Truy vấn: tìm_kiếm /2 dữ liệu Kết quả: {1, 3} 13 Nội dung chính  1. Tìm kiếm trong bộ từ vựng  2. Ngôn ngữ tìm kiếm  3. Đối sánh từ khóa 14 Làm mềm cách so sánh từ khóa  Trong so khớp như so sánh chuỗi ký tự, cùng một từ, nếu được viết dù với khác biệt rất nhỏ cũng sẽ được coi là các từ khác nhau.  Trong bộ dữ liệu và trong truy vấn có thể bắt gặp nhiều trường hợp như vậy. Ví dụ, do lỗi trong quá trình soạn thảo, do cách điền dấu, v.v.  Mục đích làm mềm là đánh giá mức độ khác biệt giữa các cặp từ để phát hiện các từ chỉ mục gần với từ truy vấn nhằm làm giảm độ nhạy đối với khác biệt trong cách viết. 15 Khoảng cách soạn thảo  Khoảng cách soạn thảo giữa chuỗi ký tự s1 và s2 là số thao tác soạn thảo cơ bản để biến s1 thành s2.  Các thao tác cơ bản trong khoảng cách Levenshtein là: chèn (insert), xóa (delete), và thay thế (replace)  Khoảng cách Damerau-Levenshtein: bổ xung thao tác hoán vị (transposition). 16 Tính khoảng cách Levenshtein theo phương pháp quy hoạch động 17 Ví dụ tính khoảng cách Levenshtein 18 Các giá trị trong ma trận Levenshtein s1[i] == s2[j] ? m[i – 1, j–1]: copy m[i – 1, j – 1] + 1 replace m[i – 1, j] + 1 delete m[i, j – 1] + 1 insert min 19 Bài tập  Tính ma trận khoảng cách Levenshtein cho OSLO –> SNOW;  Xác định các thao tác soạn thảo. 20 21 O S L O N W 22 23