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

Giải thuật xây dựng chỉ mục ngược là vấn đề chính mà bài giảng Tìm kiếm và trình diễn thông tin: Bài 5 hướng đến trình bày với nội dung trọng tâm phần cứng căn bản; các đặc trưng phần cứng cơ bản; mở rộng quy mô chỉ mục; các giải thuật xây dựng chỉ mục ngược;...
Nội dung trích xuất từ tài liệu:
Bài giảng Tìm kiếm và trình diễn thông tin: Bài 5 - TS.Nguyễn Bá Ngọc(IT4853) Tìm kiếm và trình diễn thông tin Giải thuật xây dựng chỉ mục ngược Nội dung chính Phần cứng căn bản Các giải thuật xây dựng chỉ mục ngược:  BSBI  SPIMI  MapReduce Quản lý bộ dữ liệu động 2Phần cứng căn bản Tốc độ truy cập dữ liệu trong bộ nhớ nhanh hơn nhiều so với ổ đĩa; Không thể đọc/ghi dữ liệu với ổ đĩa khi đang định vị đầu đọc; Thời gian đọc/ghi ngyên một khối dữ liệu hoặc một lượng nhỏ hơn là như nhau;  Kích thước khối được xác định trong quá trình định dạng ổ đĩa. Trao đổi dữ liệu giữa ổ đĩa và bộ nhớ được điều khiển bởi BUS hệ thống. 3 Các đặc trưng phần cứng cơ bảnKý hiệu Đặc trưng Giá trịs Thời gian định vị đầu đọc 5 ms = 5 x 10−3 sb Thời gian trung bình đọc/ghi 1 byte 0.02 μs = 2 x 10−8 s Chu kỳ đồng hồ bộ vi xử lý 10-9 sp Thời gian thực hiện một lệnh cơ 0.01 μs = 10−8 s bản 4Mở rộng quy mô chỉ mục Phương pháp xây dựng chỉ mục trong bộ nhớ chỉ phù hợp với những bộ dữ liệu nhỏ. Đối với những bộ dữ liệu lớn  Cần sử dụng ổ đĩa,  Phân tán chỉ mục trên nhiều máy. 5 Nội dung chính Phần cứng căn bản Các giải thuật xây dựng chỉ mục ngược:  BSBI  SPIMI  MapReduce Quản lý bộ dữ liệu động 6Giải thuật BSBI Blocked sort-based Indexing (BSBI) Đọc dữ liệu, tách từ và sinh thẻ định vị Các thao tác cơ bản:  Tích lũy thẻ định vị thành khối không quá lớn, đảm bảo có thể xử lý trong bộ nhớ;  Thực hiện sắp xếp khối và lưu tạm thời trên ổ đĩa;  Hợp nhất chỉ mục ngược của những khối đơn lẻ thành chỉ mục ngược duy nhất của bộ dữ liệu. 7Hợp nhất danh sách thẻ định vị 1 1 2 Kết quả 2 hợp nhất 3 4 3 4Các danhsách thẻ Ổ đĩađịnh vị. 8Giải thuật BSBI 9 Sec. 4.2Hợp nhất chỉ mục Sơ đồ hợp nhất theo cặp: 10 Sec. 4.2Hợp nhất chỉ mục Phương pháp hợp nhất đồng thời:  Sử dụng bộ nhớ đệm;  Đọc đồng thời theo khối từ các chỉ mục nhỏ;  Hợp nhất các khối nhỏ trong bộ nhớ;  Ghi lên đĩa theo khối. 11 Sec. 4.3 Nhược điểm của BSBI Cần nhiều bộ nhớ:  Cần lưu toàn bộ từ điển trong bộ nhớ;  Sử dụng từ điển kích thước động để chuyển đổi từ thành mã từ.Nếu sử dụng danh sách từ - mã văn bản thì cáctệp trung gian sẽ rất lớn, ảnh hưởng tới tốc độxây dựng chỉ mục. 12 Nội dung chính Phần cứng căn bản Các giải thuật xây dựng chỉ mục ngược:  BSBI  SPIMI  MapReduce Quản lý bộ dữ liệu động 13 Sec. 4.3Giải thuật SPIMI Single-pass in-memory indexing (SPIMI); Sinh từ điển cục bộ cho từng khối; Không sắp xếp thẻ định vị, lưu thẻ định vị theo thứ tự xuất hiện; Tạo chỉ mục ngược hoàn chỉnh cho mỗi khối; Có thể hợp nhất những chỉ mục nhỏ này thành một chỉ mục lớn. 14 Sec. 4.3 Thuật toán SPIMI Hợp nhất các khối được thực hiện tương tự BSBI. 15 Nội dung chính Phần cứng căn bản Các giải thuật xây dựng chỉ mục ngược:  BSBI  SPIMI  MapReduce Quản lý bộ dữ liệu động 16 Sec. 4.4 MapReduce MapReduce (Dean and Ghemawat 2004) là một kiến trúc tính toán phân tán:  Đơn gian: Không cần viết code đảm bảo tương tác giữa các nốt như phân chia công việc, trao đổi dữ liệu, v.v.  Độ tin cậy cao: Đảm bảo tính kết thúc trên hệ thống máy tính sử dụng phần cứng phổ thông. 17 Sec. 4.4Phân tán quá trình xây dựng chỉ mục Các bước cần đư ...