Tokenisierung mit Byte Pair Encoding (BPE)

Die Tokenisierung ist ein entscheidender Schritt in vielen NLP-Anwendungen (Natural Language Processing). Sie bestimmt, wie Wörter (bzw. Text) in kleinere Einheiten – sogenannte Tokens – zerlegt werden. Diese Tokens können einzelne Buchstaben, Wortteile (Subwords) oder ganze Wörter sein. Besonders bei modernen Sprachmodellen und Anwendungen wie maschineller Übersetzung und Textklassifikation wird eine geschickte Tokenisierung immer wichtiger.

---
config:
  sankey:
    showValues: false
    linkColor: 'target'
    width: 450
    height: 300
---
%%{
init: {
    'theme': 'base',
    'themeVariables': {
    'primaryTextColor': '#888888'
    }
}
}%%
sankey-beta

Tokenisierung_,Token,10.0
Tokenisierung_,is,10.0
Tokenisierung_,ierung,10.0
mit_ Byte_,mit,10.0
mit_ Byte_,Byte,10.0
Pair_,P,10.0
Pair_,air,10.0
Encoding_,Enc,10.0
Encoding_,oding,10.0

Ein gängiges Verfahren dafür ist Byte Pair Encoding (BPE). Ursprünglich entstammt BPE einer Datenkompressionstechnik, hat jedoch Einzug in die NLP-Welt gefunden, um das Problem von seltenen Wörtern und unbekanntem Vokabular besser zu handhaben. Dieser Blog-Beitrag zeigt Schritt für Schritt, wie man einen BPE-Tokenizer aufbaut und wie ein solcher Tokenizer anschließend zum Einsatz kommt.

Warum Tokenisierung wichtig ist

Weniger Out-of-Vocabulary-Probleme (OOV): In der Praxis tauchen häufig Wörter auf, die nicht im Trainingsvokabular enthalten sind. Mit Subword-Tokenisierung (z.B. via BPE) lassen sich diese seltenen oder unbekannten Wörter aufteilen, sodass das Modell sie besser verarbeiten kann.
Effizientes Vokabular: Durch die Zerlegung in Subwords wird das Vokabular oft viel überschaubarer als bei reinen Wort-Tokenizern.
Mehr Flexibilität: Sprachen mit komplexer Morphologie (z.B. Deutsch, Finnisch, Türkisch) profitieren davon, weil viele Wortvarianten durch Präfixe, Suffixe oder Komposita entstehen. Eine Subword-Tokenisierung erfasst diese Wortbestandteile ohne dass jedes davon im Vokabular explizit enthalten sein muss.

Funktionsweise von BPE

Der Grundgedanke von BPE ist, Schritt für Schritt die häufigsten Zeichenpaare zu einem neuen Subword-Token zu verschmelzen. Im Gegensatz zur rein zeichenbasierten Tokenisierung kann BPE so sukzessive mehrteilige Token „lernen“, die einen häufigen Wortstamm oder Suffix repräsentieren.

Die Vorgehensweise lässt sich grob in folgende Schritte gliedern:

Zeichenbasiertes Startvokabular: Jedes Wort wird zunächst in einzelne Zeichen zerlegt und mit einem speziellen End-of-Word-Symbol (z.B. _) versehen.
Häufigste Paare zählen: Man ermittelt in allen Wörtern, welche benachbarten Zeichen am häufigsten gemeinsam vorkommen.
Mergen: Das häufigste Zeichenpaar wird in allen Vorkommen zusammengefasst. Beispielsweise wird aus o g → og.
Wiederholen: Nach jedem Merge werden die Statistiken aktualisiert und der Vorgang wird so lange wiederholt, bis eine vorgegebene Anzahl an Merges erreicht oder keine sinnvollen Paare mehr übrig sind.
BPE-Ränge speichern: Jedes zusammengeführte Paar bekommt eine Rangnummer. Damit kann man später im gleichen Merge-Schema neue Wörter tokenisieren.

Minimalbeispiel in Python

BPE-Verfahrentoken_utils.Corptoken_utils.bpe_encode

Der nachfolgende Code¹ illustriert ein vereinfachtes BPE-Verfahren. Für eine bessere Übersicht ist alles in einer Klasse namens Corp gekapselt. Diese kümmert sich um das Erstellen eines Zeichen-Vokabulars, das Zählen von Paaren und die schrittweise Zusammenführung. Anschließend demonstriert eine Hilfsfunktion, wie neue Wörter mithilfe der gelernten BPE-Ränge kodiert werden.

Beispielanwendung:

Ein kurzer Beispieldatensatz zeigt, wie dieser Code eingesetzt werden kann:

from token_utils import Corp, bpe_encode

CORPUS = "The quick brown fox jumps over the dog. The dog jumps over the frog."
VOCAB_SIZE = 15

# Korpus instanziieren und Zeichen-Vokabular aufbauen
corp = Corp(end_of_word="_")
corp.build_vocabulary(CORPUS, separate_punctuation=True)

# BPE-Ränge lernen
corp.fit(num_merges=VOCAB_SIZE)

# Neue Wörter encodieren
test_words = ["bulldog", "overload", "frog"]
for word in test_words:
    tokens = bpe_encode(word, corp)
    print(f"{word} -> {tokens}")

    # bulldog -> ['b', 'u', 'l', 'l', 'dog', '_']
    # overload -> ['over', 'l', 'o', 'a', 'd', '_']
    # frog -> ['f', 'r', 'og', '_']

In der Regel tauchen nach diesen Merges Subwords wie dog, over, frog auf, wenn genügend Häufigkeit im Ausgangskorpus vorhanden war. Seltene oder unbekannte Teile verbleiben in einzelne Zeichen zerlegt.

# https://github.com/eugen-hoppe/ds_portfolio/blob/main/bpe/token_utils.py

@dataclass
class Corp:
    end_of_word: str = "_"
    inf: float = float("inf")
    vocabulary: dict[str, int] = field(default_factory=dict)
    pairs: dict[tuple[str, str], int] = field(default_factory=dict)
    merged: dict[str, int] = field(default_factory=dict)
    bpe_ranks: dict[tuple[str, str], int] = field(default_factory=dict)

    def build_vocabulary(self, corpus: str, separate_punctuation: bool = False) -> None:
        if separate_punctuation:
            corpus = re.sub(r"([.,!?])", r" \1 ", corpus)

        word_counts = Counter(corpus.split())
        for word, count in word_counts.items():
            tokenized_word = " ".join(list(word)) + " " + self.end_of_word
            self.vocabulary[tokenized_word] = count

    def statistics(self) -> None:
        self.pairs.clear()
        for word, freq in self.vocabulary.items():
            symbols = word.split()
            for i in range(len(symbols) - 1):  # Count each adjacent pair
                pair = (symbols[i], symbols[i + 1])
                self.pairs[pair] = self.pairs.get(pair, 0) + freq

    def merge(self, pair: tuple[str, str]) -> None:
        pair_str = " ".join(pair)
        pair_merged = "".join(pair)
        self.merged.clear()
        for word, freq in self.vocabulary.items():
            merged_word = word.replace(pair_str, pair_merged)
            self.merged[merged_word] = freq

    def fit(self, num_merges: int) -> None:
        for i in range(num_merges):
            self.statistics()
            if not self.pairs:
                break
            valid_pairs = {
                p: freq for p, freq in self.pairs.items() if self.end_of_word not in p
            }
            if not valid_pairs:
                break
            best_pair = max(valid_pairs, key=valid_pairs.get)
            self.bpe_ranks[best_pair] = i
            self.merge(best_pair)
            self.vocabulary = self.merged.copy()

    @staticmethod
    def get_pairs_from_tokens(tokens: list[str]) -> set[tuple[str, str]]:
        return {(tokens[i], tokens[i + 1]) for i in range(len(tokens) - 1)}

# https://github.com/eugen-hoppe/ds_portfolio/blob/main/bpe/token_utils.py

def bpe_encode(word: str, corp: Corp) -> list[str]:
    tokens = list(word) + [corp.end_of_word]

    while True:
        pairs = Corp.get_pairs_from_tokens(tokens)
        if not pairs:
            break

        best_pair = min(pairs, key=lambda p: corp.bpe_ranks.get(p, corp.inf))

        if corp.bpe_ranks.get(best_pair, corp.inf) == corp.inf:
            break

        merged_tokens = []
        i = 0
        while i < len(tokens):
            if (
                i < len(tokens) - 1
                and tokens[i] == best_pair[0]
                and tokens[i + 1] == best_pair[1]
            ):
                merged_tokens.append(tokens[i] + tokens[i + 1])
                i += 2
            else:
                merged_tokens.append(tokens[i])
                i += 1

        tokens = merged_tokens

    return tokens

Zusammenfassung

BPE (Byte Pair Encoding) bietet eine effiziente Möglichkeit, ein Subword-Vokabular zu erstellen.
Reduzierung von Out-of-Vocabulary-Token: Unbekannte Wörter werden auf bekannte Subword-Einheiten zerlegt.
Kompakteres und flexibleres Vokabular: Häufige Wortbestandteile werden als eigenständige Tokens genutzt.
Leichte Übertragbarkeit: BPE-Ränge lassen sich einfach abspeichern und auf neue Wörter anwenden.

Hinweis

BPE basiert auf rein statistischen Häufigkeiten und kann daher komplexe sprachliche Strukturen nur eingeschränkt abbilden. In agglutinierenden Sprachen oder stark variierenden Schreibweisen kann die starre Merging-Logik zu suboptimalen Segmentierungen führen. Alternativen wie WordPiece oder das Unigram Language Model verwenden probabilistische Methoden und erzielen in solchen Fällen oft robustere Ergebnisse.

Bei größeren Projekten oder umfangreichen Korpora existieren zudem fertige Tokenizer-Bibliotheken wie Hugging Face Tokenizers.

Notebook mit vollständigem Beispiel und ausführlichem Code ↩