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

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

Thêm vào BST

Báo xấu

91
lượt xem 10
download

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

Cùng tìm hiểu bài 3 thuộc bộ bài giảng Tìm kiếm và trình diễn thông tin của TS.Nguyễn Bá Ngọc để nắm bắt một số thông tin về ngôn ngữ truy vấn với vấn đề chính về tìm kiếm trong bộ từ vựng như: Bộ từ vựng dạng mảng cấu trúc, cấu trúc dữ liệu tối ưu cho tìm kiếm,...

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 3 - TS.Nguyễn Bá Ngọc

(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: http://is.hust.edu.vn/~ngocnb 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
Sec. 3.1 Bộ từ vựng dạng mảng cấu trúc 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 ---> 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 4
Sec. 3.1 Cấu trúc dữ liệu tối ưu cho tìm kiếm  Bảng băm  Cây 5
Sec. 3.1 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 6
Sec. 3.1 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 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
Sec. 3.2 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 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 delete m[i – 1, j – 1] + 1 replace 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