Tokens und Tokenisierung (BPE) in JavaScript

Problem

Ein Wörterbuch aus Wörtern

Der Support-Bot soll Nachrichten von Kunden lesen. Ein Modell arbeitet mit Zahlen, also baut ein Kollege ein Wörterbuch: Jedes Wort in den Shop-Texten bekommt eine Nummer. Das sind die Texte: Support-Antworten, Lieferhinweise und Bewertungen.

// der Shop-Text: Support-Antworten, Lieferhinweise, Bewertungen
const TEXT = [
  "deine bestellung wurde heute per kurier versendet",
  "die bestellung trifft morgen per kurier an deiner adresse ein",
  "die bestellung trifft innerhalb von drei tagen ein",
  "deine bestellung ist in der filiale des kuriers angekommen",
  "dein paket wurde an einen kurier übergeben",
  "das paket trifft innerhalb von zwei tagen ein",
  "das paket ist morgen bei dir",
  "das paket hat einen tag verspätung",
  "ein kurier kommt morgen zu deiner adresse",
  "ein kurier ruft dich vor der lieferung an",
  "die lieferung an eine adresse kostet 5 euro",
  "die lieferung an eine filiale des kuriers kostet 3 euro",
  "die lieferung ist ab 50 euro kostenlos",
  "die lieferung dauert bis zu zwei tagen",
  "die ware kommt in der originalverpackung an",
  "du kannst die ware innerhalb von 14 tagen zurückgeben",
  "gib die ware in der originalverpackung zurück",
  "die rückgabe der ware ist kostenlos",
  "das geld wird innerhalb von fünf tagen erstattet",
  "nach der rückgabe der ware bekommst du das geld",
  "das geld geht zurück auf deine karte",
  "du kannst mit karte oder per nachnahme bezahlen",
  "die zahlung mit karte ist sicher",
  "die bank hat die zahlung mit deiner karte abgelehnt",
  "versuche die zahlung mit einer anderen karte",
  "deine zahlung wird von der bank bestätigt",
  "die lieferung kam schnell an und ist sehr gut",
  "ich bin mit der bestellung sehr zufrieden",
  "die lieferung war schnell und der kurier freundlich",
  "die ware ist gut aber sie kam zu spät",
];

Dann wird jede Nachricht zu einer Reihe von Zahlen:

// das Wörterbuch: Jedes Wort des Textes bekommt eine Nummer
const vocab = [];
for (const line of TEXT)
  for (const word of line.split(" "))
    if (!vocab.includes(word)) vocab.push(word);
console.log(`Wörterbuch: ${vocab.length} Wörter`);
for (const message of ["die bestellung kommt morgen an", "meine bestellungen kommen morgen an"]) {
  const ids = message.split(" ").map((word) => (vocab.includes(word) ? String(vocab.indexOf(word)) : "?"));
  console.log(`${message} → ${ids.join(" ")}`);
}

Wörterbuch: 95 Wörter
die bestellung kommt morgen an → 7 1 36 9 10
meine bestellungen kommen morgen an → ? ? ? 9 10

Die erste Nachricht geht durch. In der zweiten stehen „meine“ und „kommen“ nicht im Text, und „bestellungen“ ist ein anderes Wort als „bestellung“. Das Modell bekommt an drei Stellen von fünf ein „?“.

Ein Wörterbuch aller Wörter funktioniert nicht. Jedes Wort hat mehrere Formen (Bestellung, Bestellungen, bestellen, bestellt), und jeden Tag kommen neue dazu: Produktnamen, Zahlen, Tippfehler. Und wenn du Buchstabe für Buchstabe liest, geht zwar jeder Text durch, aber er wird sehr lang: 26 Zeichen für fünf Wörter.

Die Idee

Stücke zwischen Buchstabe und Wort

Zwischen Buchstaben und Wörtern liegen die häufigen Stücke: „er“, „ung“, „lieferung“. Ein Modell liest Text als Reihe solcher Stücke. Jedes Stück heißt Token, und Text in Tokens zu schneiden heißt Tokenisierung.

Welche Stücke zu Tokens werden, schreibt niemand von Hand. Sie werden aus Text gelernt, mit dem Algorithmus BPE (Byte Pair Encoding):

Jedes Wort ist eine Liste von Buchstaben.
Zähle alle Paare von Nachbarn in allen Wörtern. Ein Wort, das 7-mal vorkommt, zählt seine Paare 7-mal.
Das häufigste Paar wird zu einem Stück: Das ist eine Regel. Verschmilz es überall.
Wiederhole ab Schritt 2, so viele Regeln, wie du willst.

Die Regeln bleiben in ihrer Reihenfolge. Neuer Text wird mit denselben Regeln in derselben Reihenfolge geschnitten. Ein Wort, das nicht im Text steht, geht trotzdem durch: Im schlimmsten Fall bleibt es bei Buchstaben. Es gibt kein „?“.

Sieh es dir an

60 Regeln aus dem Shop-Text

Eine Regel ist ein Paar von Tokens und die Zahl, wie oft es gesehen wurde. Ein Wort beginnt als Buchstaben:

// das Wort als Liste von Buchstaben
const letters = (word) => [...word];

Das Verschmelzen läuft über die Tokens eines Wortes von links nach rechts. Wo left und right nebeneinanderstehen, setzt es ein Token an ihre Stelle und überspringt beide:

// verschmilz jedes left, right, die nebeneinander stehen
function merge(tokens, left, right) {
  const glued = [];
  let i = 0;
  while (i < tokens.length) {
    if (tokens[i] === left && tokens[i + 1] === right) {
      glued.push(left + right);
      i += 2;
    } else {
      glued.push(tokens[i]);
      i += 1;
    }
  }
  return glued;
}

Das Lernen sind die vier Schritte der vorigen Karte. Map behält die Reihenfolge des Einfügens, also gewinnt bei Gleichstand das Paar, das zuerst gesehen wurde, und die Ausgabe ist in allen vier Sprachen gleich.

// lerne count Regeln: verschmilz jedes Mal das häufigste Paar
function learn(text, count) {
  const freq = new Map(); // wie oft jedes Wort im Text vorkommt
  for (const line of text)
    for (const word of line.split(" ")) freq.set(word, (freq.get(word) ?? 0) + 1);
  const split = new Map([...freq.keys()].map((word) => [word, letters(word)])); // vorerst ist jedes Wort nur eine Reihe von Buchstaben
  const rules = [];
  for (let r = 0; r < count; r++) {
    const pairs = new Map(); // die Nachbarpaare, gezählt mit der Häufigkeit des Wortes
    for (const [word, t] of split)
      for (let i = 0; i + 1 < t.length; i++) {
        const key = `${t[i]} ${t[i + 1]}`;
        pairs.set(key, (pairs.get(key) ?? 0) + freq.get(word));
      }
    let best = "", most = 0;
    for (const [key, n] of pairs)
      if (n > most) [best, most] = [key, n]; // das häufigste Paar (bei Gleichstand das zuerst gesehene)
    const [left, right] = best.split(" ");
    rules.push({ left, right, count: most });
    for (const [word, t] of split) split.set(word, merge(t, left, right)); // die neue Regel gilt für alle Wörter
  }
  return rules;
}

const rules = learn(TEXT, 60);
rules.forEach((r, k) => {
  const cell = `${k + 1}. ${r.left}+${r.right} (${r.count})`;
  process.stdout.write(k % 4 === 3 ? cell + "\n" : cell.padEnd(22));
});

1. e+r (48)           2. i+n (28)           3. i+e (26)           4. u+n (22)
5. s+t (21)           6. un+g (19)          7. e+n (19)           8. e+in (18)
9. d+ie (17)          10. u+r (16)          11. a+n (13)          12. d+er (12)
13. a+r (12)          14. b+e (11)          15. e+l (11)          16. l+ung (9)
17. c+h (9)           18. d+ein (8)         19. k+ur (8)          20. kur+i (8)
21. kuri+er (8)       22. e+t (8)           23. g+en (8)          24. a+l (8)
25. k+o (8)           26. i+st (7)          27. d+a (7)           28. l+ie (7)
29. lie+f (7)         30. lief+er (7)       31. liefer+ung (7)    32. w+ar (7)
33. c+k (7)           34. be+st (6)         35. t+e (6)           36. o+r (6)
37. t+a (6)           38. p+a (6)           39. da+s (6)          40. war+e (6)
41. a+h (6)           42. best+el (5)       43. bestel+lung (5)   44. v+er (5)
45. r+e (5)           46. s+e (5)           47. v+o (5)           48. vo+n (5)
49. ta+gen (5)        50. ü+ck (5)          51. k+ar (5)          52. kar+te (5)
53. m+i (5)           54. mi+t (5)          55. z+ah (5)          56. dein+e (4)
57. d+e (4)           58. f+t (4)           59. d+re (4)          60. in+n (4)

Die erste Regel ist „e“ + „r“: Das Paar wurde 48-mal gesehen. Die zweite verschmilzt „i“ mit „n“ zu „in“. Regeln bauen auf früheren auf: „k“ + „ur“ (wobei „ur“ Regel 10 ist), dann „kuri“, dann „kurier“ sind die Regeln 19 bis 21, und danach ist „kurier“ ein Token. Nach Regel 31 ist auch „lieferung“ ein Token, nach Regel 43 „bestellung“.

Probier es aus

Sag die Ausgabe voraus

Hier sind die ersten drei Regeln aus der Ausgabe oben. Was gibt das Programm aus?

const rules = [
  { left: "e", right: "r", count: 48 },
  { left: "i", right: "n", count: 28 },
  { left: "i", right: "e", count: 26 },
];
console.log(encode("lieferung", rules).join("|"));

Antwort

l|i|e|f|er|u|n|g

l|ie|f|er|u|n|g

lie|f|er|u|n|g

Sieh es dir an

Neuer Text als Tokens

Einen Satz schneiden: Jedes Wort wird zu Buchstaben, dann kommt jede Regel der Reihe nach. show gibt nur die Tokens jedes Wortes mit | dazwischen aus.

// ein Satz → Tokens: Buchstaben, dann die Regeln der Reihe nach
function encode(sentence, rules) {
  const tokens = [];
  for (const word of sentence.split(" ")) {
    let t = letters(word);
    for (const r of rules) t = merge(t, r.left, r.right);
    tokens.push(...t);
  }
  return tokens;
}

// die Tokens jedes Wortes, mit | dazwischen
const show = (sentence, rules) =>
  sentence.split(" ").map((word) => encode(word, rules).join("|")).join("  ");

So geht ein Satz durch die Regeln. Der Zähler unten sagt, wie viele Buchstaben und wie viele Tokens es sind:

// verschmilz jedes left, right, die nebeneinander stehen
function merge(tokens, left, right) {
  const glued = [];
  let i = 0;
  while (i < tokens.length) {
    if (tokens[i] === left && tokens[i + 1] === right) {
      glued.push(left + right);
      i += 2;
    } else {
      glued.push(tokens[i]);
      i += 1;
    }
  }
  return glued;
}

// ein Satz → Tokens: Buchstaben, dann die Regeln der Reihe nach
function encode(sentence, rules) {
  const tokens = [];
  for (const word of sentence.split(" ")) {
    let t = letters(word);
    for (const r of rules) t = merge(t, r.left, r.right);
    tokens.push(...t);
  }
  return tokens;
}

Schritt für Schritt, in Worten

Jedes Wort beginnt als Buchstaben: 26 Plättchen, 26 Tokens.
Regel 3: i + e. Wo die beiden nebeneinander stehen, werden sie zu einem Token, in jedem Wort.
Regel 4: u + n. Jede Regel läuft über den ganzen Satz, in der Reihenfolge, in der sie gelernt wurde.
Regeln 12 und 13 haben hier nichts zu verschmelzen, deshalb springt die Nummer auf 14.
Regel 43: bestel + lung. „bestellung“ ist jetzt ein Token.
Alle 60 Regeln: 26 Buchstaben, 10 Tokens. „kommt“ bleibt in 4 Teilen: Das Wort ist selten im Text.

const rules = learn(TEXT, 60);
const sentences = ["die bestellung kommt morgen an", "meine bestellungen kommen morgen an", "beschwerde über einen kaputten fernseher"];
for (const s of sentences) {
  console.log(show(s, rules));
  console.log(`  Buchstaben ${s.replaceAll(" ", "").length}, Tokens ${encode(s, rules).length}`);
}

die  bestellung  ko|m|m|t  m|or|gen  an
  Buchstaben 26, Tokens 10
m|ein|e  bestellung|en  ko|m|m|en  m|or|gen  an
  Buchstaben 31, Tokens 13
be|s|ch|w|er|de  ü|b|er  ein|en  k|a|p|u|t|t|en  f|er|n|se|h|er
  Buchstaben 36, Tokens 24

Der bekannte Satz sind 10 Tokens statt 26 Buchstaben. „kommt“ bleibt in vier Stücke geschnitten: Das Wort steht nur zweimal im Text, und die Regeln gehen an häufigere Paare. Im zweiten Satz wird „bestellungen“ zu „bestellung|en“, und „meine“ und „kommen“ bleiben kleine Stücke, aber keins davon ist ein „?“.

Der dritte Satz handelt von einer Beschwerde, und die meisten seiner Wörter fehlen im Shop-Text. 36 Buchstaben werden 24 Tokens: Es wird deutlich weniger verschmolzen als beim bekannten Satz (26 Buchstaben, 10 Tokens). Neuer Text lässt sich lesen, kostet aber mehr Tokens.

Das Modell sieht die Nummern der Tokens, genau wie beim Wörterbuch aus Wörtern: Jedes Token hat eine Nummer in der Liste aller Tokens, und diese Liste ist das Vokabular des Modells.

Probier es aus

Ergänze

Um wie viel rückt i vor, wenn left und right zu einem Token verschmolzen werden?

// verschmilz jedes left, right, die nebeneinander stehen
function merge(tokens, left, right) {
  const glued = [];
  let i = 0;
  while (i < tokens.length) {
    if (tokens[i] === left && tokens[i + 1] === right) {
      glued.push(left + right);
      i += ;
    } else {
      glued.push(tokens[i]);
      i += 1;
    }
  }
  return glued;
}

Die Idee

Preis und Limit gelten in Tokens

Ein Modell liest und schreibt Tokens. Darum wird alles, was man über es misst, in Tokens gemessen:

der Preis: Anbieter rechnen pro Million Tokens ab, getrennt für die Eingabe und die Antwort;
das Eingabelimit: wie viel Text das Modell auf einmal nimmt (das ist das Kontextfenster);
das Antwortlimit: wie viele Tokens es schreiben kann, bevor es aufhört.

Ein Kollege schätzt den Preis nach Wörtern. So weit liegt das daneben, bei denselben drei Nachrichten, 200.000 Nachrichten im Monat und einem Beispielpreis von 3,00 € pro Million Tokens:

const rules = learn(TEXT, 60);
const messages = ["die bestellung kommt morgen an", "meine bestellungen kommen morgen an", "beschwerde über einen kaputten fernseher"];
let words = 0, tokens = 0;
for (const m of messages) {
  const w = m.split(" ").length, t = encode(m, rules).length;
  words += w;
  tokens += t;
  console.log(`${m}: ${w} Wörter, ${t} Tokens`);
}
console.log(`Tokens pro Wort: ${(tokens / words).toFixed(2)}`);
const price = 3; // € pro Million Tokens, ein Beispielpreis
const month = 200000;
console.log(`${month} Nachrichten pro Monat, 3.00 € pro Million Tokens (ein Beispielpreis):`);
console.log("  nach Wörtern: " + (month * (words / messages.length) * price / 1e6).toFixed(2) + " €");
console.log("  nach Tokens: " + (month * (tokens / messages.length) * price / 1e6).toFixed(2) + " €");

die bestellung kommt morgen an: 5 Wörter, 10 Tokens
meine bestellungen kommen morgen an: 5 Wörter, 13 Tokens
beschwerde über einen kaputten fernseher: 5 Wörter, 24 Tokens
Tokens pro Wort: 3.13
200000 Nachrichten pro Monat, 3.00 € pro Million Tokens (ein Beispielpreis):
  nach Wörtern: 3.00 €
  nach Tokens: 9.40 €

Die Schätzung nach Wörtern ist 3,00 €, nach Tokens 9,40 €: mehr als das Dreifache. Im Schnitt sind es 3,13 Tokens pro Wort. Die seltene Nachricht wiegt am meisten: 5 Wörter, 24 Tokens. Der Preis ist ein Beispiel, die genauen Zahlen kommen vom Anbieter: Die Antwort der API sagt, wie viele Tokens hineingingen und herauskamen. Wie du ein Budget einhältst, steht in der Lektion über Kosten.

Probier es aus

Finde den Fehler

Ein Kollege schreibt sein eigenes BPE und bekommt andere Regeln: „lieferung“ wird nie ein Token. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Wann es wehtut

Das Seltene kostet mehr. Produktnamen, Bestellnummern, Tippfehler und Wörter aus einer anderen Sprache werden in kleine Stücke geschnitten. Echte Tokenizer sind vor allem mit englischem Text trainiert, darum braucht derselbe Text auf Deutsch oft mehr Tokens als auf Englisch, auf Bulgarisch oder Griechisch meist noch mehr.
Das Modell sieht keine Buchstaben. „lieferung“ ist für es ein Stück oder wenige Stücke, nicht neun Buchstaben. Darum gehen das Zählen von Buchstaben, das Umdrehen eines Wortes und Rechnen mit langen Zahlen schlecht: „1042“ sind hier vier Tokens, und bei einem anderen Modell können es zwei sein.
Jedes Modell hat seinen eigenen Tokenizer. Dieselbe Nachricht sind bei verschiedenen Modellen verschieden viele Tokens. Schätze den Preis nicht nach Wörtern und übertrage ihn nicht von einem Modell auf ein anderes: Zähle mit dem Tokenizer des Modells oder lies, wie viele Tokens die API gemeldet hat.
Die Antwort kann mittendrin abbrechen. Wenn das Modell das Antwortlimit erreicht, hört es bei dem Token auf, bei dem es angekommen ist, auch mitten im Wort. Siehe die Übung.

Genauer, für Neugierige

Bytes statt Buchstaben. Die Tokenizer echter Modelle sind meist BPE über die Bytes von UTF-8, nicht über Buchstaben. So geht jeder Text durch, auch Emoji und Alphabete, die sie nie gesehen haben. Ein Umlaut wie „ü“ ist 2 Bytes und ein kyrillischer Buchstabe auch, darum kann ein seltenes Wort in einer anderen Schrift mehr Tokens ergeben, als es Buchstaben hat.

Das Leerzeichen gehört zum Token. Hier wird jedes Wort einzeln geschnitten, und Leerzeichen zählen nicht. Echte Tokenizer kleben das Leerzeichen an das Wort danach: „ ist“ mit dem Leerzeichen davor ist ein Token. Darum sind „ist“ am Textanfang und „ ist“ mittendrin verschiedene Tokens.

Wie viele Tokens es gibt. Das Vokabular eines echten Modells hat zum Beispiel 50.000 bis 200.000 Tokens, gelernt aus einer riesigen Menge Text. Für Englisch gilt als grobe Regel ein Token pro etwa 4 Zeichen. Es gibt auch besondere Tokens, die kein Text sind, etwa „Textende“.

Die echten Werkzeuge. Fertige Tokenizer sind Bibliotheken: tiktoken und Hugging Face Tokenizers in Python und ihre Versionen für JavaScript, Java und C#. Die Arbeit mit Modellen läuft meist in Python, aber ein Tokenizer ist nur eine Tabelle von Regeln, und die Regeln sind in jeder Sprache dieselben. Die SDKs der Anbieter haben auch einen Aufruf, der die Tokens einer Nachricht zählt, bevor du sie abschickst.

Übung

Die am Limit abgeschnittene Antwort

Löse es in deinem Editor.

Ein Modell schreibt die Antwort Token für Token und hört auf, wenn es das Antwortlimit erreicht. Mach dasselbe: Nimm die Antwort, schneide sie Wort für Wort in Tokens und höre nach 6 Tokens auf. Vom Wort, das abgeschnitten wird, behältst du nur die Tokens, die noch passen. Gib aus, wie viele Tokens die ganze Antwort hat und was bis zum Limit übrig bleibt.

die Antwort: 14 Tokens
Limit 6, bis zum Limit: die ware ist in zw

„zwei“ sind vier Tokens, „z|w|e|i“, und im Limit ist nur Platz für die ersten beiden. Der Kunde sieht „die ware ist in zw“ und erfährt nicht, in wie vielen Tagen die Ware ankommt. Darum prüft das Programm, ob die Antwort am Limit abgebrochen ist, und gibt entweder mehr Platz oder bittet das Modell um eine kürzere Antwort.

Weitere Aufgaben

Mehr Regeln. Lerne 100 und 200 Regeln. Wie viele Tokens werden die drei Sätze der Lektion? Ab wann hilft es nicht mehr?
Das teuerste Wort. Finde das Wort im Shop-Text, das nach 60 Regeln die meisten Tokens hat.

Test

Teste dich

1. Das Wörterbuch aus ganzen Wörtern hat „bestellung“ gesehen, aber nicht „bestellungen“. Was macht BPE mit „bestellungen“?Es nimmt das Wort als neues Wort ins Wörterbuch aufEs gibt „?“ zurück, wie das Wörterbuch aus WörternEs schneidet das Wort in bekannte Stücke: „bestellung“ und „en“

2. Warum werden die Regeln auf neuen Text in der Reihenfolge angewendet, in der sie gelernt wurden?Weil es so schneller gehtDie Reihenfolge ist egal, das Ergebnis ist dasselbeWeil eine spätere Regel Tokens verschmilzt, die frühere Regeln gebildet haben

3. Ein Kollege schätzt den Preis des Bots nach Wörtern. Warum liegt die Schätzung unter der Rechnung?Weil auch die Leerzeichen bezahlt werdenDas Modell zählt Tokens, und ein Wort sind oft mehrere TokensWeil das Modell Buchstaben zählt

4. Das Modell sagt, „lieferung“ habe ein „e“, aber es sind zwei. Was ist der wahrscheinlichste Grund?Das Modell sieht Tokens, keine einzelnen BuchstabenDas Modell kennt das Alphabet nichtDie Temperatur ist zu hoch

Text in Stücken: Tokens

Cookies