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

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

Thêm vào BST

Báo xấu

172
lượt xem 16
download

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

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;...

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 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 2
Phầ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ản Ký hiệu Đặc trưng Giá trị s Thời gian định vị đầu đọc 5 ms = 5 x 10−3 s b 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 s p Thời gian thực hiện một lệnh cơ 0.01 μs = 10−8 s bản 4
Mở 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 6
Giả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. 7
Hợp nhất danh sách thẻ định vị 1 1 2 Kết quả 2 hợp nhất 3 4 3 4 Các danh sách thẻ Ổ đĩa định vị. 8
Giải thuật BSBI 9
Sec. 4.2 Hợp nhất chỉ mục  Sơ đồ hợp nhất theo cặp: 10
Sec. 4.2 Hợ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ác tệ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.3 Giả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.4 Phân tán quá trình xây dựng chỉ mục  Các bước cần được phân tán:  Đọc dữ liệu  Nghịch đảo 18
Sec. 4.4 Đọc dữ liệu  Nốt điều khiển thực hiện phân chia công việc đọc dữ liệu:  Chia bộ dữ liệu thành nhiêu khối và phân chia cho các nốt đọc dữ liệu;  Nốt đọc xử lý tuần tự từng văn bản và sinh thẻ định vị, vd, theo dạng cặp  Sau đó chép thẻ định vị vào j phân vùng: Mỗi phân vùng ứng với một khoảng từ (ví dụ, j = 3, từ bắt đầu với, a-f, g-p, q-z). 19
Sec. 4.4 Nghịch đảo  Số lượng nốt nghịch đảo bẳng số lượng phân đoạn, j;  Nhiệm vụ của nốt nghịch đảo:  Tiếp nhận tất cả các phân đoạn tương ứng thu được sau khi đọc dữ liệu;  Sắp xếp và thiết lập danh sách thẻ định vị. 20