Fusioni Byte Pair Encoding (BPE)

I tokenizzatori in stile GPT usano il Byte Pair Encoding: parti da singoli caratteri e fondi ripetutamente la coppia di vicini più frequente in un nuovo simbolo.

1. Dividi ogni parola di words in caratteri. Le parole ripetute contano più volte.
2. Conta ogni coppia di simboli vicini in tutte le parole.
3. Scegli la coppia più frequente. In caso di pareggio, scegli la coppia minore confrontando (primo simbolo, secondo simbolo) come stringhe.
4. Sostituisci ogni occorrenza di quella coppia, da sinistra a destra, con il simbolo fuso e annota il simbolo fuso.
5. Ripeti num_merges volte, oppure fermati prima se nessuna parola ha più due simboli.

Implementa bpe_merges(words, num_merges).

Input

words: Le parole di addestramento (lettere minuscole).

num_merges: Quante fusioni imparare.

Output

Restituisci i simboli fusi nell'ordine in cui sono stati imparati.

Vincoli

1 ≤ numero di parole ≤ 1.000, 1 ≤ lunghezza di ogni parola ≤ 30

0 ≤ num_merges ≤ 200

Esempi

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

Output atteso:
expected = ["lo", "low"]

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

Output atteso:
std::vector<std::string> expected = {"lo", "low"};

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

Output atteso:
string[] expected = new string[] {"lo", "low"};

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

Output atteso:
expected = ["aa", "aaa"]

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

Output atteso:
std::vector<std::string> expected = {"aa", "aaa"};

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

Output atteso:
string[] expected = new string[] {"aa", "aaa"};

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

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