Tous les défis
Moyen 0 résolus 0 % de réussite

Fusions de Byte Pair Encoding (BPE)

Apprenez des fusions de sous-mots comme les tokeniseurs GPT : fusionnez à répétition la paire de symboles voisins la plus fréquente.

Ce que vous allez apprendre

  • Compter les paires de symboles adjacents
  • Fusionner plusieurs fois la paire la plus fréquente
  • Comprendre comment sont construits les tokeniseurs de type GPT

Problème

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

Exemple 1
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"};

Explication

Paires : "l o" et "o w" apparaissent chacune 3 fois ; l'égalité est remportée par "l o" ("l" < "o"), ce qui donne "lo". Ensuite "lo w" apparaît 3 fois et donne "low". Résultat : ["lo", "low"].

Exemple 2
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"};

Explication

"aaa" contient la paire "a a" deux fois. Fusionnée de gauche à droite, cela donne "aa" + "a". Ensuite "aa a" fusionne en "aaa" et le mot n'a plus qu'un symbole, donc la troisième fusion n'a rien à faire. Résultat : ["aa", "aaa"].

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Suis la séquence de symboles courante pour chaque mot et compte à répétition les paires voisines sur tous les mots répétés.

Indice 2

Utilise le comptage des paires et un départage déterministe en comparant la paire comme deux chaînes, puis mets à jour chaque mot de gauche à droite.

Indice 3

Fais attention aux mots qui se réduisent à un seul symbole ; quand aucune paire adjacente n’existe nulle part, arrête-toi même s’il reste des fusions.

Complexité attendue

temps O(num_merges * total_symbols), espace supplémentaire O(total_symbols)

Références

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

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.