Bài 5 · Danh sách khác biệt và tập tối đại

dGenMax — tập tối đại bằng danh sách khác biệt

dGenMax chính là GenMax, chỉ thay danh sách giao dịch bằng danh sách khác biệt. Khung dò quay lui và phép cắt tỉa bằng kiểm tra bao trùm giữ nguyên; chỗ khác duy nhất là khi tính độ phổ biến của phần mở rộng, ta dùng phép trừ trên danh sách khác biệt thay cho việc lấy phần chung. Kết quả vẫn là đúng hai tập tối đại.

1. Hai quy tắc cần nhớ

Tính độ phổ biến của phần mở rộng

Giống dEclat: lấy danh sách khác biệt của thành viên đứng sau bỏ đi phần của thành viên đứng trước, rồi lấy độ phổ biến của thành viên trước trừ đi số giao dịch còn lại. Mặt hàng nào sau khi tính vẫn còn đạt ngưỡng thì giữ trong danh sách mở rộng.

Cắt tỉa bằng kiểm tra bao trùm

Giống hệt GenMax: nếu phần đầu nối với toàn bộ phần còn lại của danh sách mở rộng mà đã là tập con của một tập tối đại đã có, thì bỏ cả nhánh. Khi danh sách mở rộng cạn sạch mà phần đầu chưa bị bao trùm, thì phần đầu là một tập tối đại mới.

2. Giải mẫu từng bước

Vẫn bảng dữ liệu quen thuộc, ngưỡng phổ biến bằng ba, thứ tự xét là A, D, T, W rồi C.

Bước một — lập danh sách mở rộng cho phần đầu A bằng danh sách khác biệt.

Với AD, những giao dịch có A mà vắng D là 1 và 3, nên độ phổ biến bằng bốn trừ hai, còn hai, không đạt ngưỡng nên loại. Với AT, chỉ giao dịch 4 khác biệt, độ phổ biến bốn trừ một còn ba, giữ. Với AW, danh sách khác biệt rỗng, độ phổ biến bốn, giữ. Với AC, danh sách khác biệt rỗng, độ phổ biến bốn, giữ. Vậy danh sách mở rộng của A gồm T, W và C.

Bước hai — đi sâu theo AT, rồi ATW, rồi ATWC.

Từ AT, ghép thêm W cho ATW: danh sách khác biệt rỗng, độ phổ biến ba. Ghép thêm C cho ATC: cũng rỗng, độ phổ biến ba. Vậy danh sách mở rộng của AT gồm W và C. Đi tiếp theo ATW, ghép thêm C cho ATWC: danh sách khác biệt rỗng, độ phổ biến ba; đến đây danh sách mở rộng cạn, nên ATWC là một tập tối đại, viết gọn là ACTW, độ phổ biến ba. Quay lui, các nhánh ATC, AW, AC đều nằm gọn trong ACTW nên bị cắt.

Bước ba — nhánh D cho ra CDW; các nhánh T, W, C bị cắt.

Danh sách mở rộng của D: cặp DT có độ phổ biến hai nên loại; cặp DW có danh sách khác biệt gồm giao dịch 6, độ phổ biến ba, giữ; cặp DC có danh sách khác biệt rỗng, độ phổ biến bốn, giữ. Đi sâu theo DW, ghép thêm C cho DWC: lấy phần khác biệt của DC (rỗng) bỏ đi phần của DW, vẫn rỗng, độ phổ biến ba; danh sách mở rộng cạn, nên DWC là một tập tối đại, viết gọn là CDW, độ phổ biến ba. Nhánh DC nằm gọn trong CDW nên bị cắt. Cuối cùng, các nhánh T, W, C đều là con của ACTW nên cũng bị cắt.
Kết quả: hai tập tối đại, giống hệt GenMax

ACTW và CDW, cả hai cùng có độ phổ biến ba.

3. Bài tập tự luyện

Dùng bảng P, ngưỡng phổ biến bằng hai. Năm giao dịch: giao dịch một có B, C, M; giao dịch hai có B, E; giao dịch ba có B, C, E, M; giao dịch bốn có C, E, O; giao dịch năm có B, C, E, M. Sau khi loại O, thứ tự xét là M, B, C, E.

Bài một. Dùng danh sách khác biệt, đi sâu theo M, rồi MB, MBC, MBCE và tính độ phổ biến từng bước.

M có ở các giao dịch 1, 3, 5, độ phổ biến ba. Ghép M với B: danh sách khác biệt rỗng, độ phổ biến ba. Ghép M với C: cũng rỗng, độ phổ biến ba. Ghép M với E: khác biệt gồm giao dịch 1, độ phổ biến hai. Đi sâu theo MB rồi ghép C cho MBC: lấy phần của MC (rỗng) bỏ đi phần của MB (rỗng), vẫn rỗng, độ phổ biến ba. Ghép E cho MBE: lấy phần của ME (gồm giao dịch 1) bỏ đi phần của MB (rỗng), vẫn là giao dịch 1, độ phổ biến hai. Lên mức bốn, ghép cho MBCE: phần khác biệt vẫn là giao dịch 1, độ phổ biến hai. Danh sách mở rộng cạn, nên ta được một tập tối đại là BCEM, độ phổ biến hai.

Bài hai. Bảng P có mấy tập tối đại?

Chỉ có một tập tối đại duy nhất là BCEM, độ phổ biến hai. Mọi tập phổ biến khác đều là con của BCEM.