Giải thuật khớp tiền tố dài nhất (MaxMatch / Longest Match First Subword Tokenization)

Mô tả bài toán

WordPiece (thuật toán tokenization trong Google BERT) phân rã một từ chưa biết thành các mẩu subword dựa trên chiến lược tham lam khớp đoạn dài nhất trước (MaxMatch / Greedy Longest-Match First):

Quy tắc thuật toán:

• Nếu toàn bộ từ word đã nằm trong vocab, trả về [word].
• Khởi tạo con trỏ i = 0.
• Tại vị trí i, tìm tiền tố dài nhất có thể w[i:j] (với j giảm dần từ len(w) về i+1) sao cho:
• Nếu i = 0: w[i:j] ∈ vocab.
• Nếu i > 0: "##" + w[i:j] ∈ vocab (tiền tố ## biểu thị phần tiếp nối của từ).
• Nếu tìm thấy đoạn con khớp dài nhất:
• Thêm subword vào danh sách kết quả.
• Nhảy con trỏ i ← j.
• Nếu tại bất kỳ bước nào không tìm được bất kỳ đoạn con hợp lệ nào, toàn bộ từ bị coi là không thể phân rã ⇒ lập tức trả về [unk_token] (mặc định "[UNK]").

Hãy viết hàm max_match_tokenize_word(word: str, vocab: set[str], unk_token: str = "[UNK]") -> list[str].

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ả.