Vòng lặp huấn luyện BPE hoàn chỉnh (BPE Training Loop & Merge Tables)

Mô tả bài toán

Thuật toán huấn luyện BPE hoàn chỉnh kết hợp việc đếm cặp và gộp lặp đi lặp lại qua M bước (num_merges):

Quy trình:

• Chuẩn bị ngữ liệu: Nhận danh sách các từ thô kèm tần suất (ví dụ: {"low": 5, "lower": 2, "newest": 6, "widest": 3}).

Tách từng từ thành tuple các ký tự và thêm ký hiệu kết thúc từ </w>: "low" -> ('l', 'o', 'w', '</w>').

• Khởi tạo danh sách quy tắc gộp merges: list[tuple[str, str]] = [].
• Lặp lại tối đa num_merges lần:
• Đếm tần suất tất cả các cặp ký hiệu liền kề.
• Nếu không còn cặp nào (tất cả các từ đã co thành 1 ký hiệu duy nhất), dừng sớm.
• Chọn cặp có tần suất lớn nhất. Nếu có nhiều cặp hòa tần suất, chọn theo thứ tự từ điển tăng dần (p0, p1) để đảm bảo tính tất định.
• Lưu cặp được chọn vào merges.
• Thực hiện gộp cặp này trên toàn bộ ngữ liệu.
• Trích xuất tập từ vựng cuối cùng vocab: set[str] gồm tất cả các ký hiệu xuất hiện trong ngữ liệu sau M bước gộp.

Hãy viết hàm train_bpe(word_freqs: dict[str, int], num_merges: int) -> tuple[list[tuple[str, str]], set[str]]:

• Trả về tuple (merges, vocab).

Ràng buộc

• Thời gian chạy tối đa: 6000ms.
• Giới hạn bộ nhớ: 512MB.
• Dữ liệu đầu vào hợp lệ theo đúng kiểu dữ liệu và miền giá trị được mô tả.