การรวมแบบ Byte Pair Encoding (BPE)

Tokenizer แบบ GPT ใช้ Byte Pair Encoding: เริ่มจากอักขระเดี่ยว แล้วรวมคู่ข้างเคียงที่พบบ่อยที่สุดเป็นสัญลักษณ์ใหม่ซ้ำ ๆ

1. แยกแต่ละคำใน words เป็นอักขระ คำที่ซ้ำนับหลายครั้ง
2. นับทุกคู่สัญลักษณ์ข้างเคียงในทุกคำ
3. เลือกคู่ที่พบบ่อยที่สุด ถ้าเท่ากัน ให้เลือกคู่ที่น้อยที่สุดเมื่อเปรียบเทียบ (สัญลักษณ์แรก, สัญลักษณ์ที่สอง) เป็นสตริง
4. แทนที่ทุกครั้งที่พบคู่นั้น จากซ้ายไปขวา ด้วยสัญลักษณ์ที่รวมแล้ว และบันทึกสัญลักษณ์ที่รวมแล้ว
5. ทำซ้ำ num_merges ครั้ง หรือหยุดก่อนถ้าไม่มีคำใดเหลือสองสัญลักษณ์แล้ว

จง implement bpe_merges(words, num_merges)

อินพุต

words: คำสำหรับฝึก (ตัวพิมพ์เล็ก)

num_merges: จำนวนการรวมที่ต้องเรียนรู้

เอาต์พุต

คืนค่าสัญลักษณ์ที่รวมแล้วตามลำดับที่เรียนรู้

เงื่อนไข

1 ≤ จำนวนคำ ≤ 1,000, 1 ≤ ความยาวแต่ละคำ ≤ 30

0 ≤ num_merges ≤ 200

ตัวอย่าง

อินพุต:
words = ["low", "lower", "lowest"]
num_merges = 2

ผลลัพธ์ที่คาดหวัง:
expected = ["lo", "low"]

อินพุต:
std::vector<std::string> words = {"low", "lower", "lowest"};
long long num_merges = 2;

ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"lo", "low"};

อินพุต:
string[] words = new string[] {"low", "lower", "lowest"};
long num_merges = 2;

ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"lo", "low"};

อินพุต:
words = ["aaa"]
num_merges = 3

ผลลัพธ์ที่คาดหวัง:
expected = ["aa", "aaa"]

อินพุต:
std::vector<std::string> words = {"aaa"};
long long num_merges = 3;

ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"aa", "aaa"};

อินพุต:
string[] words = new string[] {"aaa"};
long num_merges = 3;

ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"aa", "aaa"};

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

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