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

BÀI GIẢNG THƯ VIỆN SỐCHƯƠNG 3: CHỈ MỤC TÀI LIỆU VĂN BẢN  TS. ĐỖ QUANG VINHHÀ NỘI - 2013 *NỘI DUNGTỔNG QUAN VỀ THƯ VIỆN SỐ DLMÔ HÌNH HÌNH THỨC CHO THƯ VIỆN SỐ DLCHỈ MỤC TÀI LIỆUTÌM KIẾM THÔNG TINCÁC CHUẨN SỬ DỤNG TRONG THƯ VIỆN SỐTHỰC HÀNH HỆ PHẦN MỀM THƯ VIỆN SỐ GREENSTONE*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 741856Số thuật ngữ F 333338738Số thuật ngữ riêng biệt n 535346Số con trỏ chỉ mục f 134994414Kích thước tổng (MB) 2070.29*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*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*Bảng 3.3 - IF đối với văn bản của bảng 3.2Số 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)*Đị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.2Số 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 *Xây dựng chỉ mục tệp đảo IFIDXâ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. *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*Bảng 5.1 - Ma trận tần suất đối với văn bản của bảng 3.2Thuật ngữinformationretrievalsearchingindexingbuildingindexinvertedfile111-1----2---111--3-----1114---11-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.1SốThuật ngữTài liệu12341information1---2retrieval1---3searching----4indexing11-15building-1-16index-11-7inverted--118file--11*GIẢI THUẬT 5.1 ĐẢO DANH SÁCH MÓC NỐI1. 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ụcb. Đối với mỗi một thuật ngữ chỉ mục t  Dd Cho fd,t là tần suất của thuật ngữ t trong Dd Tìm kiếm S đối với tNếu t không có trong S, chèn nóThêm một nút lưu trữ vào danh sách tương ứng với thuật ngữ t *3. /* Pha 2 - đầu ra của IF */Đối với mỗi một thuật ngữ 1 ≤ t ≤ NBắt đầu một mục vào IF mớiĐố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àyNếu yêu cầu, nén mục vào IFThê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)*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.2information11 retrieval12 searching14 indexing162146buiding2341 index2536 inverted3243 file3344 *3.3 CHỈ MỤC TỆP KÝ SỐ SFIDBả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 1110Tệ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 *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.* 3.5.2 Mô hình nén toàn cụcMô 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ệchMô hình nén nội suy *3.5.4 Hiệu năng của các mô hình nén chỉ mụcBảng 3.9 - Nén IF bằng số bit/con trỏ đối với TRECMô hình Số bit/con trỏMô hình toàn cụcĐơn nguyên 1918Nhị phân 20.00Bernoulli 12.30 6.63 6.38Mô hình cục bộHyperbol 5.89 Bernoulli 5.84Bernoulli lệch 5.44Nội suy 5.18*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á Golomb3.6 CÁC HIỆU ỨNGGộp dạng chữ (case folding)Truy gốc từ (stemming) Từ bỏ qua (stop word) *TÀI LIỆU THAM KHẢOĐỗ 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. 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.Arms W.Y. (2003), Digital Libraries, MIT Press, Cambridge.Fox E.A. (2000), Advanced Digital Libraries, Virginia Polytechnic Institue and State University.Lesk M. (2005), Understanding Digital Libraries, 2nd Edition, Morgan Kaufmann, San Francisco.Witten I.H., Bainbridge D. (2003), How to Build a Digital Library, Morgan Kaufmann, San Francisco.*KẾT THÚC !TRÂN TRỌNG CÁM ƠN !