Bài giảng Tìm kiếm và trình diễn thông tin - Bài 5: Giải thuật xây dựng chỉ mục ngược - Nguyễn Bá Ngọc

Nội dung text: Bài giảng Tìm kiếm và trình diễn thông tin - Bài 5: Giải thuật xây dựng chỉ mục ngược - Nguyễn Bá Ngọc

1. (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
2. 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
3. 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
4. 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
5. 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
6. 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
7. 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
8. 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
9. Giải thuật BSBI 9
10. Sec. 4.2 Hợp nhất chỉ mục  Sơ đồ hợp nhất theo cặp: 10
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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
17. 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
18. 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
19. 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
20. 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
21. Sec. 4.4 Sơ đồ luồng dữ liệu gán Master gán Danh sách Parser a-f g-p q-z Inverter a-f Parser a-f g-p q-z Inverter g-p Khối Inverter q-z Parser a-f g-p q-z Map Tệp phân đoạn Reduce phase phase 21
22. Sec. 4.4 Các phương pháp phân đoạn chỉ mục  Phân đoạn theo từ: mỗi máy xử lý một khoảng từ  Phân đoạn theo văn bản: mỗi máy xử lý một tập con của bộ văn bản văn bản  Cần thực hiện chuyển đổi giữa các dạng phân đoạn.  Hầu hết công cụ tìm kiếm sử dụng chỉ mục phân đoạn theo văn bản. 22
23. Ví dụ xây dựng chỉ mục phân tán  Map:  d1 : C ca, C ce.  d2 : C d. →  , , , , ,  Reduce:  ( , , , ) → ( , , , ) 23
24. 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 24
25. Sec. 4.5 Bộ dữ liệu động  Đối với chỉ mục tĩnh:  Phải xây dựng lại chỉ mục mỗi khi có sự thay đổi trong bộ dữ liệu;  cập nhật lại bộ từ vựng;  cập nhật lại danh sách thẻ định vị. Cần giải pháp khác đối với những bộ dữ liệu thay đổi thường xuyên 25
26. Sec. 4.5 Chỉ mục chính phụ  Sử dụng chỉ mục chính và chỉ mục phụ  Thêm văn bản mới vào chỉ mục phụ;  Chỉ đánh dấu văn bản cần xóa trong chỉ mục.  Thực hiện truy vấn trên cả hai chỉ mục và tổng hợp kết quả.  Cần lọc các văn bản đã đánh dấu xóa.  Định kỳ xây dựng lại toàn bộ chỉ mục. 26
27. Sec. 4.5 Nhược điểm của chỉ mục chính phụ  Thay đổi thường xuyên làm kích thước chỉ mục phụ tăng nhanh  Cần nhiều thời gian để hợp nhất chỉ mục chính và chỉ mục phụ  Giải pháp: Sử dụng nhiều chỉ mục có thể giảm thời gian hợp nhất, tuy nhiên thực hiện truy vấn sẽ phức tạp hơn. 27
28. Sec. 4.5 Hợp nhất độ phức tạp Logarith  Sử dụng nhiều cấp chỉ mục:  Lưu chỉ mục nhỏ nhất (Z0) trong bộ nhớ  Những chỉ mục lớn hơn (I0, I1, I2, ) trên ổ đĩa  Khi Z0 trở nên quá lớn, sẽ ghi Z0 lên đĩa và thực hiện hợp nhất với những chỉ mục đã tồn tại. 28
29. Sec. 4.5 29