Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Fusiones de Byte Pair Encoding (BPE)

Aprende fusiones de subpalabras como los tokenizadores de GPT: fusiona repetidamente el par de símbolos vecinos más frecuente.

Lo que aprenderás

  • Contar pares de símbolos adyacentes
  • Fusionar repetidamente el par más frecuente
  • Entender cómo se crean los tokenizadores tipo GPT

Problema

Ver original (inglés)

Los tokenizadores al estilo GPT usan Byte Pair Encoding: empieza con caracteres sueltos y fusiona repetidamente el par de vecinos más frecuente en un símbolo nuevo.

  1. Divide cada palabra de words en caracteres. Las palabras repetidas cuentan varias veces.
  2. Cuenta cada par de símbolos vecinos en todas las palabras.
  3. Elige el par más frecuente. En caso de empate, elige el par menor comparando (primer símbolo, segundo símbolo) como cadenas.
  4. Reemplaza cada aparición de ese par, de izquierda a derecha, por el símbolo fusionado y anota el símbolo fusionado.
  5. Repite num_merges veces, o detente antes si ninguna palabra tiene ya dos símbolos.

Implementa bpe_merges(words, num_merges).

Entrada

words: Las palabras de entrenamiento (letras minúsculas).

num_merges: Cuántas fusiones aprender.

Salida

Devuelve los símbolos fusionados en el orden en que se aprendieron.

Restricciones

1 ≤ número de palabras ≤ 1.000, 1 ≤ longitud de cada palabra ≤ 30

0 ≤ num_merges ≤ 200

Ejemplos

Ejemplo 1
Entrada:
words = ["low", "lower", "lowest"]
num_merges = 2

Salida esperada:
expected = ["lo", "low"]
Entrada:
std::vector<std::string> words = {"low", "lower", "lowest"};
long long num_merges = 2;

Salida esperada:
std::vector<std::string> expected = {"lo", "low"};
Entrada:
string[] words = new string[] {"low", "lower", "lowest"};
long num_merges = 2;

Salida esperada:
string[] expected = new string[] {"lo", "low"};

Explicación

Pares: "l o" y "o w" aparecen 3 veces cada uno; el empate lo gana "l o" ("l" < "o"), lo que da "lo". Después "lo w" aparece 3 veces y da "low". Resultado: ["lo", "low"].

Ejemplo 2
Entrada:
words = ["aaa"]
num_merges = 3

Salida esperada:
expected = ["aa", "aaa"]
Entrada:
std::vector<std::string> words = {"aaa"};
long long num_merges = 3;

Salida esperada:
std::vector<std::string> expected = {"aa", "aaa"};
Entrada:
string[] words = new string[] {"aaa"};
long num_merges = 3;

Salida esperada:
string[] expected = new string[] {"aa", "aaa"};

Explicación

"aaa" contiene el par "a a" dos veces. Fusionado de izquierda a derecha da "aa" + "a". Después "aa a" se fusiona en "aaa" y la palabra tiene un solo símbolo, así que la tercera fusión no tiene nada que hacer. Resultado: ["aa", "aaa"].

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Lleva la secuencia actual de símbolos de cada palabra y cuenta repetidamente los pares vecinos en todas las palabras repetidas.

Pista 2

Usa el conteo de pares más desempate determinista comparando el par como dos cadenas, y luego actualiza cada palabra de izquierda a derecha.

Pista 3

Ojo con las palabras que se reducen a un solo símbolo; cuando no exista ningún par adyacente en ninguna parte, deténte aunque queden fusiones.

Complejidad esperada

tiempo O(num_merges * total_symbols), espacio extra O(total_symbols)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.