Fusões de Byte Pair Encoding (BPE)

Tokenizadores no estilo GPT usam Byte Pair Encoding: comece com caracteres individuais e funda repetidamente o par de vizinhos mais frequente em um novo símbolo.

1. Divida cada palavra de words em caracteres. Palavras repetidas contam várias vezes.
2. Conte cada par de símbolos vizinhos em todas as palavras.
3. Escolha o par mais frequente. Em caso de empate, escolha o menor par comparando (primeiro símbolo, segundo símbolo) como strings.
4. Substitua cada ocorrência desse par, da esquerda para a direita, pelo símbolo fundido e registre o símbolo fundido.
5. Repita num_merges vezes, ou pare antes se nenhuma palavra tiver mais dois símbolos.

Implemente bpe_merges(words, num_merges).

Entrada

words: As palavras de treinamento (letras minúsculas).

num_merges: Quantas fusões aprender.

Saída

Retorne os símbolos fundidos na ordem em que foram aprendidos.

Restrições

1 ≤ número de palavras ≤ 1.000, 1 ≤ comprimento de cada palavra ≤ 30

0 ≤ num_merges ≤ 200

Exemplos

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

Saída esperada:
expected = ["lo", "low"]

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

Saída esperada:
std::vector<std::string> expected = {"lo", "low"};

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

Saída esperada:
string[] expected = new string[] {"lo", "low"};

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

Saída esperada:
expected = ["aa", "aaa"]

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

Saída esperada:
std::vector<std::string> expected = {"aa", "aaa"};

Entrada:
string[] words = new string[] {"aaa"};
long num_merges = 3;

Saída esperada:
string[] expected = new string[] {"aa", "aaa"};

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

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