Giải thuật mã hóa BPE khi suy luận (BPE Inference Encoding Algorithm)

Mô tả bài toán

Sau khi huấn luyện, ta thu được danh sách các quy tắc gộp merges: list[tuple[str, str]]. Mỗi quy tắc gộp được gán một mức độ ưu tiên (rank), quy tắc nào được học sớm hơn sẽ có rank nhỏ hơn (ưu tiên gộp trước): bpe_ranks = {pair: i for i, pair in enumerate(merges)}

Giải thuật mã hóa BPE cho một từ mới khi suy luận:

• Tách từ thành tuple các ký hiệu ban đầu: w = (c₁, c₂, …, c_n).
• Vòng lặp:
• Liệt kê tất cả các cặp liền kề trong w: P = {(w_i, w_i+1) | i = 0 … |w|-2}.
• Tìm trong P cặp có rank nhỏ nhất trong bpe_ranks:

p^* = argmin_{p ∈ P ∩ bpe_ranks} bpe_ranks[p]

• Nếu không có bất kỳ cặp nào nằm trong bpe_ranks, dừng lại.
• Thực hiện gộp tất cả các lần xuất hiện của p^* trong w thành ký hiệu mới p^*₀ + p^*₁.
• Trả về tuple các subword cuối cùng.

Hãy viết hàm bpe_encode_word(word_symbols: tuple[str, ...], bpe_ranks: dict[tuple[str, str], int]) -> tuple[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ả.