Byte-Pair-Encoding-Merges (BPE)

Tokenizer im Stil von GPT verwenden Byte Pair Encoding: Beginne mit einzelnen Zeichen und verschmelze wiederholt das häufigste Nachbarpaar zu einem neuen Symbol.

1. Zerlege jedes Wort in words in Zeichen. Wiederholte Wörter zählen mehrfach.
2. Zähle jedes Paar benachbarter Symbole über alle Wörter.
3. Wähle das häufigste Paar. Bei Gleichstand das Paar, das beim Vergleich von (erstes Symbol, zweites Symbol) als Zeichenketten am kleinsten ist.
4. Ersetze jedes Vorkommen dieses Paars, von links nach rechts, durch das verschmolzene Symbol und notiere das verschmolzene Symbol.
5. Wiederhole das num_merges-mal oder höre früher auf, wenn kein Wort mehr zwei Symbole hat.

Implementiere bpe_merges(words, num_merges).

Eingabe

words: Die Trainingswörter (Kleinbuchstaben).

num_merges: Wie viele Merges gelernt werden sollen.

Ausgabe

Gib die verschmolzenen Symbole in der Reihenfolge zurück, in der sie gelernt wurden.

Einschränkungen

1 ≤ Anzahl der Wörter ≤ 1.000, 1 ≤ Länge jedes Worts ≤ 30

0 ≤ num_merges ≤ 200

Beispiele

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

Erwartete Ausgabe:
expected = ["lo", "low"]

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

Erwartete Ausgabe:
std::vector<std::string> expected = {"lo", "low"};

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

Erwartete Ausgabe:
string[] expected = new string[] {"lo", "low"};

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

Erwartete Ausgabe:
expected = ["aa", "aaa"]

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

Erwartete Ausgabe:
std::vector<std::string> expected = {"aa", "aaa"};

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

Erwartete Ausgabe:
string[] expected = new string[] {"aa", "aaa"};

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

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