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

(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 2Nộ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 3Phầ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. 4Cá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ơ bản 0.01 μs = 10−8 s 5Mở 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. 6Nộ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 7Giả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. 8Hợp nhất danh sách thẻ định vị Ổ đĩa 1 3 4 2 2 1 4 3 Các danh sách thẻ định vị. Kết quả hợp nhất 9Giải thuật BSBI 10 Hợp nhất chỉ mục  Sơ đồ hợp nhất theo cặp: Sec. 4.2 11 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. Sec. 4.2 12 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. Sec. 4.3 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 14 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. Sec. 4.3 15 Thuật toán SPIMI  Hợp nhất các khối được thực hiện tương tự BSBI. Sec. 4.3 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 17 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. Sec. 4.4 18 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 Sec. 4.4 19 Đọ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). Sec. 4.4 20 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ị. Sec. 4.4 21 Sơ đồ luồng dữ liệu Khối Parser Parser Parser Master a-f g-p q-z a-f g-p q-z a-f g-p q-z Inverter Inverter Inverter Danh sách a-f g-p q-z gán gán Map phase Tệp phân đoạn Reduce phase Sec. 4.4 22 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. Sec. 4.4 23 Ví dụ xây dựng chỉ mục phân tán  Map:  d1 : C ca, C ce.  d2 : C d. →  , , , , ,  Reduce:  (, , , ) → (, , , ) 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 25 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ị. Sec. 4.5 Cần giải pháp khác đối với những bộ dữ liệu thay đổi thường xuyên 26 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. Sec. 4.5 27 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. Sec. 4.5 28 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. Sec. 4.5 29 Sec. 4.5 30