Fusiones de Byte Pair Encoding (BPE)

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

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

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

Referencias

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

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