Các lần gộp Byte Pair Encoding (BPE)

Các tokenizer kiểu GPT dùng Byte Pair Encoding: bắt đầu từ từng ký tự và liên tục gộp cặp ký hiệu liền kề phổ biến nhất thành một ký hiệu mới.

1. Tách mỗi từ trong words thành các ký tự. Từ lặp lại được tính nhiều lần.
2. Đếm mọi cặp ký hiệu liền kề trên tất cả các từ.
3. Chọn cặp xuất hiện nhiều nhất. Nếu bằng nhau, chọn cặp nhỏ nhất khi so sánh (ký hiệu đầu, ký hiệu sau) như chuỗi.
4. Thay mọi lần xuất hiện của cặp đó, từ trái sang phải, bằng ký hiệu đã gộp, và ghi lại ký hiệu đã gộp.
5. Lặp lại num_merges lần, hoặc dừng sớm khi không còn từ nào có từ hai ký hiệu trở lên.

Hãy cài đặt bpe_merges(words, num_merges).

Đầu vào

words: Các từ huấn luyện (chữ thường).

num_merges: Số lần gộp cần học.

Đầu ra

Trả về các ký hiệu đã gộp theo thứ tự được học.

Ràng buộc

1 ≤ số từ ≤ 1.000, 1 ≤ độ dài mỗi từ ≤ 30

0 ≤ num_merges ≤ 200

Ví dụ

Đầu vào:
words = ["low", "lower", "lowest"]
num_merges = 2

Kết quả mong đợi:
expected = ["lo", "low"]

Đầu vào:
std::vector<std::string> words = {"low", "lower", "lowest"};
long long num_merges = 2;

Kết quả mong đợi:
std::vector<std::string> expected = {"lo", "low"};

Đầu vào:
string[] words = new string[] {"low", "lower", "lowest"};
long num_merges = 2;

Kết quả mong đợi:
string[] expected = new string[] {"lo", "low"};

Đầu vào:
words = ["aaa"]
num_merges = 3

Kết quả mong đợi:
expected = ["aa", "aaa"]

Đầu vào:
std::vector<std::string> words = {"aaa"};
long long num_merges = 3;

Kết quả mong đợi:
std::vector<std::string> expected = {"aa", "aaa"};

Đầu vào:
string[] words = new string[] {"aaa"};
long num_merges = 3;

Kết quả mong đợi:
string[] expected = new string[] {"aa", "aaa"};

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

• Sennrich, Haddow and Birch, Neural Machine Translation of Rare Words with Subword Units
• Hugging Face course, Byte-Pair Encoding tokenization