Thuật toán Phân đoạn Từ BPE (Byte-Pair Encoding) từ Gốc

Mục tiêu kiến thức

• Hiểu cách thức hoạt động của Tokenizer Subword (nền tảng của GPT-2/3/4, LLaMA):
• Ban đầu, mỗi từ được biểu diễn dưới dạng danh sách các ký tự đơn lẻ kết thúc bằng ký tự đặc biệt </w>.
• Tại mỗi bước lặp, đếm tần suất xuất hiện của tất cả các cặp ký tự liền kề (bigram).
• Chọn cặp có tần suất cao nhất để gộp (merge) thành một token mới.
• Lặp lại quá trình này num_merges lần để xây dựng bảng quy tắc gộp merges: list[tuple[str, str]].
• Quá trình mã hóa (Tokenization):
• Áp dụng các quy tắc trong merges theo đúng thứ tự ưu tiên đã học lên từ mới để phân rã thành các subword.

Yêu cầu

Xây dựng lớp BPETokenizer:

class BPETokenizer:
    def __init__(self, num_merges: int = 10):
        pass

    def train(self, corpus: list[str]) -> list[tuple[str, str]]:
        pass

    def tokenize_word(self, word: str) -> list[str]:
        pass

• train(corpus):
• Tách văn bản thành các từ bằng khoảng trắng.
• Mỗi từ được tách ký tự và gắn thêm '</w>' vào cuối (ví dụ: "low" -> ('l', 'o', 'w</w>')).
• Thực hiện num_merges lần gộp cặp có tần suất lớn nhất. Nếu hòa tần suất (tie), chọn cặp nhỏ hơn theo thứ tự từ điển (lexicographical order) của tuple (p1, p2).
• Trả về danh sách các cặp đã gộp merges.
• tokenize_word(word):
• Phân rã word thành các token theo đúng các quy tắc merges đã học.

Ràng buộc

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