Todos os desafios
Médio 0 resolvidos 0% de aceitação

Fusões de Byte Pair Encoding (BPE)

Aprenda fusões de subpalavras como os tokenizadores do GPT: funda repetidamente o par de símbolos vizinhos mais frequente.

O que você vai aprender

  • Contar pares de símbolos adjacentes
  • Mesclar repetidamente o par mais frequente
  • Entender como os tokenizadores no estilo GPT são criados

Problema

Ver original (inglês)

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

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

Explicação

Pares: "l o" e "o w" aparecem 3 vezes cada; o empate fica com "l o" ("l" < "o"), o que dá "lo". Depois "lo w" aparece 3 vezes e dá "low". Resultado: ["lo", "low"].

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

Explicação

"aaa" contém o par "a a" duas vezes. Fundido da esquerda para a direita, dá "aa" + "a". Depois "aa a" se funde em "aaa" e a palavra tem um único símbolo, então a terceira fusão não tem nada a fazer. Resultado: ["aa", "aaa"].

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Acompanhe a sequência atual de símbolos de cada palavra e conte repetidamente os pares vizinhos em todas as palavras repetidas.

Dica 2

Use contagem de pares mais desempate determinístico comparando o par como duas strings e depois atualize cada palavra da esquerda para a direita.

Dica 3

Observe palavras que encolhem para um único símbolo; quando nenhum par adjacente existir em lugar nenhum, pare mesmo que ainda restem merges.

Complexidade esperada

tempo O(num_merges * total_symbols), espaço extra O(total_symbols)

Referências

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

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.