Fusions de Byte Pair Encoding (BPE)

Les tokeniseurs de type GPT utilisent le Byte Pair Encoding : partez de caractères isolés et fusionnez à répétition la paire de voisins la plus fréquente en un nouveau symbole.

1. Découpez chaque mot de words en caractères. Les mots répétés comptent plusieurs fois.
2. Comptez chaque paire de symboles voisins sur l'ensemble des mots.
3. Choisissez la paire la plus fréquente. En cas d'égalité, prenez la paire la plus petite en comparant (premier symbole, second symbole) comme chaînes.
4. Remplacez chaque occurrence de cette paire, de gauche à droite, par le symbole fusionné, et notez le symbole fusionné.
5. Répétez num_merges fois, ou arrêtez plus tôt si plus aucun mot n'a deux symboles.

Implémentez bpe_merges(words, num_merges).

Entrée

words : Les mots d'entraînement (lettres minuscules).

num_merges : Le nombre de fusions à apprendre.

Sortie

Renvoyez les symboles fusionnés dans l'ordre où ils ont été appris.

Contraintes

1 ≤ nombre de mots ≤ 1 000, 1 ≤ longueur de chaque mot ≤ 30

0 ≤ num_merges ≤ 200

Exemples

Entrée :
words = ["low", "lower", "lowest"]
num_merges = 2

Sortie attendue :
expected = ["lo", "low"]

Entrée :
std::vector<std::string> words = {"low", "lower", "lowest"};
long long num_merges = 2;

Sortie attendue :
std::vector<std::string> expected = {"lo", "low"};

Entrée :
string[] words = new string[] {"low", "lower", "lowest"};
long num_merges = 2;

Sortie attendue :
string[] expected = new string[] {"lo", "low"};

Entrée :
words = ["aaa"]
num_merges = 3

Sortie attendue :
expected = ["aa", "aaa"]

Entrée :
std::vector<std::string> words = {"aaa"};
long long num_merges = 3;

Sortie attendue :
std::vector<std::string> expected = {"aa", "aaa"};

Entrée :
string[] words = new string[] {"aaa"};
long num_merges = 3;

Sortie attendue :
string[] expected = new string[] {"aa", "aaa"};

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

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