Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Byte-Pair-Encoding-Merges (BPE)

Lerne Subwort-Merges wie GPT-Tokenizer: Verschmelze wiederholt das häufigste Paar benachbarter Symbole.

Das lernst du

  • Paare benachbarter Symbole zählen
  • Das häufigste Paar wiederholt verschmelzen
  • Verstehen, wie Tokenizer im GPT-Stil entstehen

Problem

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

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

Erläuterung

Paare: "l o" und "o w" kommen je 3-mal vor; bei Gleichstand gewinnt "l o" ("l" < "o") und ergibt "lo". Jetzt kommt "lo w" 3-mal vor und ergibt "low". Ergebnis: ["lo", "low"].

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

Erläuterung

"aaa" enthält das Paar "a a" zweimal. Von links nach rechts verschmolzen ergibt das "aa" + "a". Dann verschmilzt "aa a" zu "aaa", und das Wort besteht nur noch aus einem Symbol, also hat der dritte Merge nichts zu tun. Ergebnis: ["aa", "aaa"].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Verfolge die aktuelle Symbolfolge für jedes Wort und zähle wiederholt benachbarte Paare über alle wiederholten Wörter hinweg.

Hinweis 2

Nutze Paarzählung plus deterministisches Tie-Breaking, indem du das Paar als zwei Strings vergleichst, und aktualisiere dann jedes Wort von links nach rechts.

Hinweis 3

Beobachte Wörter, die auf ein Symbol schrumpfen; wenn nirgendwo mehr ein benachbartes Paar existiert, stoppe auch dann, wenn noch Merges übrig sind.

Erwartete Komplexität

Zeit O(num_merges * total_symbols), zusätzlicher Speicher O(total_symbols)

Referenzen

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

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.