Bài giảng Thư viện số - Chương 3: Chỉ mục tài liệu văn bản - Đỗ Quang Vinh

Nội dung text: Bài giảng Thư viện số - Chương 3: Chỉ mục tài liệu văn bản - Đỗ Quang Vinh

1. BÀI GIẢNG THƯ VIỆN SỐ CHƯƠNG 3: CHỈ MỤC TÀI LIỆU VĂN BẢN TS. ĐỖ QUANG VINH HÀ NỘI - 2013
2. NỘI DUNG I. TỔNG QUAN VỀ THƯ VIỆN SỐ DL II. MÔ HÌNH HÌNH THỨC CHO THƯ VIỆN SỐ DL III. CHỈ MỤC TÀI LIỆU IV. TÌM KIẾM THÔNG TIN V. CÁC CHUẨN SỬ DỤNG TRONG THƯ VIỆN SỐ VI. THỰC HÀNH HỆ PHẦN MỀM THƯ VIỆN SỐ GREENSTONE 2
3. III. CHỈ MỤC TÀI LIỆU VĂN BẢN 3.1 MỞ ĐẦU ▪ Định nghĩa 3.1 (từ để nhận dạng đối với chỉ mục): là một dãy cực đại của các ký tự chữ và số, nhưng giới hạn tối đa 256 ký tự và tối đa 4 ký tự số ▪ Bảng 3.1 - CSDL TREC Số tài liệu N 741856 Số thuật ngữ F 333338738 Số thuật ngữ riêng biệt n 535346 Số con trỏ chỉ mục f 134994414 Kích thước tổng (MB) 2070.29 3
4. 3.2 CHỈ MỤC TỆP ĐẢO IFID ▪ Định nghĩa 3.2 (Đỗ Trung Tuấn): Chỉ mục là bảng dữ liệu hay cấu trúc dữ liệu dùng để xác định vị trí của các dòng trong tệp theo điều kiện nào đó ▪ Định nghĩa 3.3 (Folk M.J., Zoellick B., Riccardi G.): Chỉ mục là một cách tìm kiếm thông tin ▪ Định nghĩa 3.4: Chỉ mục là một cơ chế nhằm định vị thuật ngữ cho trước trong văn bản ▪ Định nghĩa 3.5 (chỉ mục tệp đảo IFID): Đối với mỗi một thuật ngữ trong từ điển, một IF chứa một danh sách đảo (IL) lưu trữ một danh sách con trỏ tới tất cả xuất hiện của thuật ngữ đó trong văn bản chính, trong đó mỗi một con trỏ trong thực tế là số tài liệu mà thuật ngữ đó xuất hiện. IL đôi khi được coi là một danh sách mục lục và các con trỏ là mục lục  Đây là phương pháp chỉ mục tự nhiên nhất, gần tương ứng với chỉ mục của một cuốn sách và với cách dùng mục lục truyền thống 4
5. Bảng 3.2 - Văn bản mẫu; mỗi dòng là một tài liệu TÀI LIỆU VĂN BẢN 1 Information retrieval is searching and indexing 2 Indexing is building an index 3 An inverted file is an index 4 Building an inverted file is indexing 5
6. Bảng 3.3 - IF đối với văn bản của bảng 3.2 Số Thuật ngữ IL(tài liệu; vị trí) 1 an (2;4), (3;1), (3;5), (4;2) 2 and (1;5) 3 building (2;3), (4;1) 4 file (3;3), (4;4) 5 index (2;5), (3;6) 6 indexing (1;6), (2;1), (4;6) 7 information (1;1) 8 inverted (3;2), (4;3) 9 is (1;3), (2;2), (3;4), (4;5) 10 retrieval (1;2) 11 searching (1;4) 6
7. ▪ Định nghĩa 3.6: Độ hạt (granularity) của một chỉ mục là tính chính xác để nhận dạng vị trí của thuật ngữ Bảng 3.4 - IF mức từ đối với văn bản của bảng 3.2 Số Thuật ngữ (Tài liệu; từ) 1 an 2 and 3 building 4 file 5 index 6 indexing 7 information 8 inverted 9 is 10 retrieval 11 searching 7
8. ▪ Xây dựng chỉ mục tệp đảo IFID ▪ Xây dựng chỉ mục là một trong những nhiệm vụ thách thức nhất phải đương đầu khi xây dựng một CSDL. Ở đây, ta đề cập đến bài toán xây dựng chỉ mục tệp đảo IFID, vì đây là dạng chỉ mục thiết thực nhất đối với cả hai truy vấn BQ và RQ. ▪ Quá trình xây dựng chỉ mục được coi là sự đảo văn bản. Từ điển The Concise Oxford Dictionary định nghĩa “sự đảo là đảo lộn trên dưới, đảo vị trí, trật tự hoặc quan hệ bình thường” và đây đúng là điều phải làm để tạo lập chỉ mục. 8
9. ▪ Xét văn bản mẫu ở bảng 3.2 Mỗi tài liệu của văn bản chứa một số thuật ngữ chỉ mục và mỗi một thuật ngữ chỉ mục xuất hiện ở một số dòng. Quan hệ có thể được biểu diễn với một ma trận tần suất, trong đó mỗi một cột tương ứng với một từ, mỗi một hàng tương ứng với một tài liệu và số chứa tại hàng và cột bất kỳ là tần suất của từ chỉ định bởi cột đó. Ma trận tần suất đối với văn bản của bảng 3.2 được trình bày ở bảng 5.1 9
10. Bảng 5.1 - Ma trận tần suất đối với văn bản của bảng 3.2 Thuật ngữ information retrieval searching indexing building index inverted file 1 1 1 - 1 - - - - 2 - - - 1 1 1 - - 3 - - - - - 1 1 1 4 - - - 1 1 - 1 1 10
11. Bảng 5.2 - Chuyển vị tương đương của ma trận tần suất của bảng 5.1 Tài liệu Số Thuật ngữ 1 2 3 4 1 information 1 - - - 2 retrieval 1 - - - 3 searching - - - - 4 indexing 1 1 - 1 5 building - 1 - 1 6 index - 1 1 - 7 inverted - - 1 1 8 file - - 1 1 11
12. ▪ GIẢI THUẬT 5.1 ĐẢO DANH SÁCH MÓC NỐI 1. Sản xuất một chỉ mục đảo đối với một CSDL tài liệu /* Khởi tạo */ 2. Tạo ra một cấu trúc từ điển rỗng S. /* Pha 1 - tập hợp các xuất hiện thuật ngữ */ Đối với mỗi một tài liệu Dd trong CSDL, 1 ≤ d ≤ N, a. Đọc Dd , phân tích cú pháp nó thành các thuật ngữ chỉ mục b. Đối với mỗi một thuật ngữ chỉ mục t Dd i. Cho fd,t là tần suất của thuật ngữ t trong Dd ii. Tìm kiếm S đối với t iii. Nếu t không có trong S, chèn nó iv. Thêm một nút lưu trữ vào danh sách tương ứng với thuật ngữ t 12
13. 3. /* Pha 2 - đầu ra của IF */ Đối với mỗi một thuật ngữ 1 ≤ t ≤ N a. Bắt đầu một mục vào IF mới b. Đối với mỗi một trong danh sách tương ứng với t, thêm vào mục vào IF này a. Nếu yêu cầu, nén mục vào IF b. Thêm mục vào IF này vào IF. ✓ Thời gian đảo T yêu cầu là: T = Btr + Ftp + (đọc và phân tích cú pháp văn bản) I(td + tr) (ghi IF nén) 13
14. Hình 5.1 - Cấu trúc dữ liệu biểu diễn IF đối với văn bản của bảng 3.2 information 1 1 retrieval 1 2 searching 1 4 indexing 1 6 2 1 4 6 buiding 2 3 4 1 index 2 5 3 6 inverted 3 2 4 3 file 3 3 4 4 14
15. 3.3 CHỈ MỤC TỆP KÝ SỐ SFID Bảng 3.5 – Mã hoá chồng lên của tài liệu 2 đối với SF Thuật ngữ Ký số thuật ngữ indexing 0001 0000 1100 0100 is 0100 0100 0001 0000 building 0101 0011 0000 0000 an 0000 0100 0100 1100 index 1100 1000 0010 0000 Ký số bloc 1101 1111 1111 1110 ▪ Tệp ký số SF: là một phương pháp xác suất để chỉ mục văn bản. Mỗi một tài liệu có một ký số liên kết, một xâu bit bắt nội dung tài liệu theo một nghĩa nào đó ▪ Tệp ký số bitslice: Sự truy cập SF có thể được tăng nhanh hơn bằng cách dùng kỹ thuật bitslicing, tức là kỹ thuật chuyển vị ma trận bit 15
16. 3.4 SO SÁNH CÁC PHƯƠNG PHÁP CHỈ MỤC ▪ Phương pháp chỉ mục tệp đảo IFID và chỉ mục tệp ký số SFID là hai phương pháp chỉ mục chính tài liệu trong thư viện số. ▪ Quy luật chỉ mục tài liệu trong DL: Ở hầu hết các ứng dụng, IF thực hiện tốt hơn SF trong phạm vi của cả hai kích thước chỉ mục và tốc độ truy vấn. IF nén là phương pháp chỉ mục hữu ích nhất một CSDL lớn các tài liệu văn bản có độ dài có thể thay đổi. 3.5 CÁC MÔ HÌNH NÉN IFID 3.5.1 Đặt vấn đề Khảo sát các mô hình và phương pháp mã hoá để nén IFID CSDL tài liệu trong thư viện số. Chìa khoá của bài toán nén là nhận xét mỗi một IL có thể được lưu trữ như một dãy số nguyên tăng dần. 16
17. 3.5.2 Mô hình nén toàn cục ▪ Mô hình không tham số ▪ Mô hình Bernoulli toàn cục 3.5.3 Các mô hình nén cục bộ ▪ Mô hình hyperbol cục bộ ▪ Mô hình Bernoulli cục bộ ▪ Mô hình Bernoulli lệch ▪ Mô hình nén nội suy 17
18. 3.5.4 Hiệu năng của các mô hình nén chỉ mục Bảng 3.9 - Nén IF bằng số bit/con trỏ đối với TREC Mô hình Số bit/con trỏ Mô hình toàn cục Đơn nguyên 1918 Nhị phân 20.00 Bernoulli 12.30  6.63  6.38 Mô hình cục bộ Hyperbol 5.89 Bernoulli 5.84 Bernoulli lệch 5.44 Nội suy 5.18 18
19.  NHẬN XÉT: Các mô hình cục bộ có xu hướng thực hiện nén tốt hơn mô hình toàn cục và không hiệu quả hơn về thời gian xử lý đòi hỏi trong khi giải mã, vì chúng có xu hướng cài đặt phức tạp hơn. Đối với mục đích thực hành, mô hình nén chỉ mục phù hợp nhất là phương pháp Bernoulli cục bộ, cài đặt dùng kỹ thuật mã hoá Golomb 3.6 CÁC HIỆU ỨNG ▪ Gộp dạng chữ (case folding) ▪ Truy gốc từ (stemming) ▪ Từ bỏ qua (stop word) 19
20. ❑ TÀI LIỆU THAM KHẢO 1. Đỗ Quang Vinh (2009), Thư viện số - Chỉ mục và Tìm kiếm, Nxb Đại học Quốc gia Hà Nội. 2. Lourdes T.D. (2006), Thư viện số và truy cập mở tài liệu lưu trữ, Nguyễn Xuân Bình và nnk biên dịch, UNESCO, Hà Nội. 3. Arms W.Y. (2003), Digital Libraries, MIT Press, Cambridge. 4. Fox E.A. (2000), Advanced Digital Libraries, Virginia Polytechnic Institue and State University. 5. Lesk M. (2005), Understanding Digital Libraries, 2nd Edition, Morgan Kaufmann, San Francisco. 6. Witten I.H., Bainbridge D. (2003), How to Build a Digital Library, Morgan Kaufmann, San Francisco. 20
21. KẾT THÚC ! TRÂN TRỌNG CÁM ƠN ! 21