Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

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

Học cách gộp từ con như tokenizer của GPT: liên tục gộp cặp ký hiệu liền kề xuất hiện nhiều nhất.

Bạn sẽ học được gì

  • Đếm các cặp ký hiệu liền kề
  • Gộp cặp phổ biến nhất nhiều lần
  • Hiểu cách tokenizer kiểu GPT được xây dựng

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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"};

Giải thích

Các cặp: "l o" và "o w" đều xuất hiện 3 lần; khi hòa, chọn "l o" ("l" < "o"), được "lo". Giờ "lo w" xuất hiện 3 lần, được "low". Kết quả: ["lo", "low"].

Ví dụ 2
Đầ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"};

Giải thích

"aaa" có cặp "a a" hai lần. Gộp từ trái sang phải được "aa" + "a". Sau đó "aa a" gộp thành "aaa", từ chỉ còn một ký hiệu, nên lần gộp thứ ba không có gì để làm. Kết quả: ["aa", "aaa"].

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Theo dõi chuỗi symbol hiện tại cho mỗi từ và lặp lại việc đếm các cặp láng giềng trên tất cả các từ lặp.

Gợi ý 2

Dùng đếm pair cộng với quy tắc phá hòa xác định bằng cách so sánh pair như hai string, rồi cập nhật từng từ từ trái sang phải.

Gợi ý 3

Chú ý những từ co lại còn một symbol; khi không còn cặp kề nhau nào ở bất kỳ đâu, hãy dừng lại dù vẫn còn merge.

Độ phức tạp mong đợi

thời gian O(num_merges * total_symbols), bộ nhớ phụ O(total_symbols)

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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.