Byte Pair Encoding

Il Byte Pair Encoding è un algoritmo di compressione dati pubblicato nel 1994 da Philip Gage in un articolo per il C Users Journal. Trent'anni dopo, con una modifica, è diventato il tokenizzatore di GPT, LLaMA e di quasi tutti i modelli di linguaggio moderni.

Capire come funziona significa capire come i modelli trasformano il testo grezzo in qualcosa che possono elaborare. In questo articolo implementeremo BPE da zero in PHP — training e encoding compresi.

Il problema dei tokenizzatori

I modelli di linguaggio non leggono testo. Leggono sequenze di interi. Prima che un modello possa elaborare la frase "il gatto è sul tappeto", quella frase deve essere convertita in qualcosa del tipo [1037, 14287, 232, 519, 14920]. Questo è il compito del tokenizzatore: trasformare stringhe in sequenze di ID numerici, e riconvertirle in testo in fase di output.

La domanda è: come si definisce questa mappatura? Ci sono tre approcci fondamentali.

Character-level: ogni carattere è un token. Vocabolario minuscolo (26 lettere + punteggiatura), ma le sequenze diventano enormi. La parola "internazionalizzazione" è già 21 token. I modelli faticano a catturare pattern linguistici su sequenze così lunghe.

Word-level: ogni parola è un token. Sequenze corte, ma il vocabolario esplode: le lingue flessive hanno milioni di forme. Peggio, le parole mai viste durante il training non possono essere rappresentate affatto.

Subword: il compromesso. I token rappresentano frammenti di parola — suffissi, prefissi, radici. Un vocabolario ragionevole (32.000–100.000 token) che copre qualsiasi parola scomponendola nei suoi pezzi. BPE è l'algoritmo più diffuso per costruire questo vocabolario.

L'idea di fondo: compressione

Prima di parlare di NLP, vale la pena capire cosa fa BPE nella sua forma originale, perché il principio è identico.

BPE lavora su una sequenza di simboli. Trova la coppia di simboli adiacenti più frequente, la sostituisce ovunque con un nuovo simbolo, e salva la regola di sostituzione. Ripete finché non raggiunge il numero di regole desiderato.

Esempio su una sequenza di caratteri:

Input:    a a b c a a b d a a b c

Passo 1:  coppia più frequente → (a, a)  →  sostituisce con X
          X b c X b d X b c

Passo 2:  coppia più frequente → (X, b)  →  sostituisce con Y
          Y c Y d Y c

Passo 3:  coppia più frequente → (Y, c)  →  sostituisce con Z
          Z Y d Z

La sequenza originale di 12 simboli è diventata 4. Il dizionario delle regole — (a,a)→X, (X,b)→Y, (Y,c)→Z — è sufficiente per ricostruire l'originale. Questo è BPE come compressore.

L'adattamento per i modelli di linguaggio

Nel 2016, Rico Sennrich e colleghi pubblicarono Neural Machine Translation of Rare Words with Subword Units, che adattò BPE al problema della tokenizzazione. Le modifiche rispetto alla versione originale sono minime ma fondamentali.

Punto di partenza diverso. Invece di byte o caratteri arbitrari, BPE per NLP parte da parole del corpus scomposte nei loro caratteri — ogni parola è rappresentata come sequenza di caratteri separati da spazio.

Il marcatore di fine parola. Ogni parola riceve il suffisso </w> prima di essere scomposta. Senza questo marcatore, il token low estratto dalla parola "lower" sarebbe indistinguibile dal token low della parola "low" da sola. Il </w> preserva i confini tra parole e permette al modello di capire se un token è un suffisso, un prefisso, o una parola completa.

L'output sono regole, non simboli compressi. L'obiettivo non è comprimere il corpus: è imparare un insieme ordinato di merge rules — le regole di fusione — che definiscono il vocabolario del modello.

Il training passo per passo

Supponiamo di avere un corpus minimo: le parole nation, station e ration, ognuna con frequenza 1. Il primo passo è scomporre ogni parola in caratteri separati da spazio con </w> in fondo:

n a t i o n </w>   frequenza: 1
s t a t i o n </w>   frequenza: 1
r a t i o n </w>   frequenza: 1

Contiamo tutte le coppie di simboli adiacenti nell'intero corpus, pesando per la frequenza della parola che le contiene:

Coppia	Frequenza
`a, t`	3
`t, i`	3
`i, o`	3
`o, n`	3
`n, </w>`	3
`n, a`	1
`s, t`	1
`t, a`	1
`r, a`	1

Cinque coppie a pari merito con frequenza 3. Prendiamo (a, t) e la fondiamo in at:

n at i o n </w>
s t at i o n </w>
r at i o n </w>

La coppia (at, i) è ora la più frequente, con 3. Fondiamo in ati:

n ati o n </w>
s t ati o n </w>
r ati o n </w>

Poi (ati, o) → atio, poi (atio, n) → ation, poi (ation, </w>) → ation</w>:

n ation</w>
s t ation</w>
r ation</w>

In cinque merge, BPE ha scoperto da solo che -ation è un elemento condiviso e lo ha trasformato in un token atomico. Nessuno glielo ha detto: è emerso dalle frequenze del corpus.

La proprietà più importante si vede quando codifichiamo parole mai viste durante il training:

'nation'   → ['nation</w>']
'station'  → ['s', 't', 'ation</w>']
'ration'   → ['r', 'ation</w>']
'creation' → ['c', 'r', 'e', 'ation</w>']
'fashion'  → ['f', 'a', 's', 'h', 'i', 'o', 'n', '</w>']

"Creation" non era nel corpus di training, eppure viene gestita correttamente: il modello vede un prefisso c r e e il token già noto ation</w>. "Fashion" non condivide nessun subword appreso — ricade interamente a livello di carattere. Il modello non si blocca mai davanti a parole fuori vocabolario: le gestisce per decomposizione, ricadendo ai caratteri nel caso peggiore.

L'implementazione in PHP

L'implementazione si articola in quattro funzioni: costruzione del vocabolario iniziale, conteggio delle coppie, applicazione di un merge, e il loop principale di training.

`buildVocab()`

Prende il testo grezzo e restituisce un array associativo in cui le chiavi sono le rappresentazioni a caratteri separati da spazio (con </w>) e i valori sono le frequenze.

function buildVocab(string $text): array
{
    $words = preg_split('/\s+/', strtolower(trim($text)));
    $vocab = [];

    foreach ($words as $word) {
        if ($word === '') continue;
        // "cane" diventa "c a n e </w>"
        $key = implode(' ', str_split($word)) . ' </w>';
        $vocab[$key] = ($vocab[$key] ?? 0) + 1;
    }

    return $vocab;
}

`getPairFrequencies()`

Scansiona il vocabolario corrente e conta ogni coppia di simboli adiacenti, pesata per la frequenza della parola che la contiene. Usiamo | come separatore interno per non confonderci con lo spazio che divide i simboli nella rappresentazione del vocabolario.

function getPairFrequencies(array $vocab): array
{
    $pairs = [];

    foreach ($vocab as $word => $freq) {
        $symbols = explode(' ', $word);
        $n = count($symbols);

        for ($i = 0; $i < $n - 1; $i++) {
            $key = $symbols[$i] . '|' . $symbols[$i + 1];
            $pairs[$key] = ($pairs[$key] ?? 0) + $freq;
        }
    }

    return $pairs;
}

`mergePair()`

Applica una singola regola di merge all'intero vocabolario. Scansiona ogni parola simbolo per simbolo e fonde la coppia ($a, $b) ogni volta che la trova, scorrendo verso destra senza tornare indietro.

function mergePair(string $a, string $b, array $vocab): array
{
    $merged   = $a . $b;
    $newVocab = [];

    foreach ($vocab as $word => $freq) {
        $symbols = explode(' ', $word);
        $result  = [];
        $i       = 0;

        while ($i < count($symbols)) {
            if (
                $i < count($symbols) - 1
                && $symbols[$i]     === $a
                && $symbols[$i + 1] === $b
            ) {
                $result[] = $merged;
                $i += 2;
            } else {
                $result[] = $symbols[$i];
                $i++;
            }
        }

        $newWord            = implode(' ', $result);
        $newVocab[$newWord] = ($newVocab[$newWord] ?? 0) + $freq;
    }

    return $newVocab;
}

`train()`

Il loop principale. Ad ogni iterazione trova la coppia più frequente con arsort(), la salva come regola di merge nell'ordine di scoperta, aggiorna il vocabolario e ripete.

function train(string $text, int $numMerges): array
{
    $vocab  = buildVocab($text);
    $merges = [];

    for ($i = 0; $i < $numMerges; $i++) {
        $pairs = getPairFrequencies($vocab);
        if (empty($pairs)) break;

        arsort($pairs);
        $bestKey = array_key_first($pairs);
        [$a, $b] = explode('|', $bestKey);

        $vocab    = mergePair($a, $b, $vocab);
        $merges[] = [$a, $b];
    }

    return $merges;
}

Encoding

Dati i merge appresi dal training, encode() li applica — nell'ordine esatto in cui sono stati scoperti — a una singola parola. L'ordine è critico: ogni regola è stata appresa nel contesto delle regole precedenti, quindi applicarle in sequenza diversa produce token sbagliati.

function encode(string $word, array $merges): array
{
    // Partiamo dalla rappresentazione a caratteri + </w>
    $symbols = array_merge(str_split($word), ['</w>']);

    foreach ($merges as [$a, $b]) {
        $merged = $a . $b;
        $i      = 0;

        while ($i < count($symbols) - 1) {
            if ($symbols[$i] === $a && $symbols[$i + 1] === $b) {
                array_splice($symbols, $i, 2, [$merged]);
            } else {
                $i++;
            }
        }
    }

    return $symbols;
}

function encodeText(string $text, array $merges): array
{
    $words  = preg_split('/\s+/', strtolower(trim($text)));
    $tokens = [];

    foreach ($words as $word) {
        if ($word === '') continue;
        $tokens = array_merge($tokens, encode($word, $merges));
    }

    return $tokens;
}

Un esempio completo

<?php

$corpus = <<<TEXT
the dog barks the cat meows the cat runs the dog runs
the dog eats the cat eats the cat drinks the dog drinks
TEXT;

$merges = train($corpus, 20);

echo "Merge rules apprese:\n";
foreach ($merges as $i => [$a, $b]) {
    printf("  %2d. %-14s + %-14s → %s\n", $i + 1, "'$a'", "'$b'", "'$a$b'");
}

echo "\nEncoding:\n";
$words = ['dog', 'cat', 'meows', 'barks', 'runs', 'eats', 'drinks', 'wolf'];
foreach ($words as $word) {
    $tokens = encode($word, $merges);
    $fmt    = implode(', ', array_map(fn($t) => "'$t'", $tokens));
    echo "  '$word' → [$fmt]\n";
}

Output:

Merge rules apprese:
   1. 't'            + 'h'            → 'th'
   2. 'th'           + 'e'            → 'the'
   3. 'the'          + '</w>'         → 'the</w>'
   4. 's'            + '</w>'         → 's</w>'
   5. 'a'            + 't'            → 'at'
   6. 'd'            + 'o'            → 'do'
   7. 'do'           + 'g'            → 'dog'
   8. 'dog'          + '</w>'         → 'dog</w>'
   9. 'c'            + 'at'           → 'cat'
  10. 'cat'          + '</w>'         → 'cat</w>'
  11. 'k'            + 's</w>'        → 'ks</w>'
  12. 'r'            + 'u'            → 'ru'
  13. 'ru'           + 'n'            → 'run'
  14. 'run'          + 's</w>'        → 'runs</w>'
  15. 'e'            + 'at'           → 'eat'
  16. 'eat'          + 's</w>'        → 'eats</w>'
  17. 'd'            + 'r'            → 'dr'
  18. 'dr'           + 'i'            → 'dri'
  19. 'dri'          + 'n'            → 'drin'
  20. 'drin'         + 'ks</w>'       → 'drinks</w>'

Encoding:
  'dog'     → ['dog</w>']
  'cat'     → ['cat</w>']
  'meows'   → ['m', 'e', 'o', 'w', 's</w>']
  'barks'   → ['b', 'a', 'r', 'ks</w>']
  'runs'    → ['runs</w>']
  'eats'    → ['eats</w>']
  'drinks'  → ['drinks</w>']
  'wolf'    → ['w', 'o', 'l', 'f', '</w>']

Le parole frequenti nel corpus — dog, cat, runs, eats, drinks — diventano token singoli. Le parole rare — meows, barks — vengono parzialmente scomposte, riutilizzando token già appresi come s</w> e ks</w>. La parola mai vista — wolf — ricade completamente a livello di carattere. Nessuna eccezione, nessun token sconosciuto: BPE garantisce che qualsiasi testo sia rappresentabile, al peggio un carattere alla volta.

Dal token alla stringa, dalla stringa al numero

I token prodotti da encode() sono ancora stringhe. In produzione, ogni token viene mappato a un intero — il suo ID — tramite un vocabolario costruito al termine del training. Il vocabolario contiene i caratteri base del corpus (il punto di partenza dell'algoritmo) più ogni token generato da una merge rule.

// Costruisce il vocabolario e assegna un ID a ogni token
function buildTokenizer(array $merges, string $corpus): array
{
    // Caratteri base: tutti i caratteri unici nel corpus + </w>
    preg_match_all('/./u', strtolower($corpus), $m);
    $base = array_values(array_unique(array_filter($m[0], fn($c) => trim($c) !== '')));
    $base[] = '</w>';
    sort($base);

    // Token generati dalle merge rules
    $mergeTokens = array_map(fn([$a, $b]) => $a . $b, $merges);

    $vocab = array_values(array_unique(array_merge($base, $mergeTokens)));
    return array_flip($vocab); // token → id
}

$tokenizer = buildTokenizer($merges, $corpus);

$tokens = encode('dog', $merges);
$ids    = array_map(fn($t) => $tokenizer[$t], $tokens);

echo implode(', ', $ids); // 19

Decodificare è il processo inverso: dato un array di ID, mappa ognuno al token corrispondente con array_flip($tokenizer), poi rimuovi i </w> e ricongiungi le parole. La complessità sta tutta nella fase di training — encoding e decoding sono operazioni di lookup.

La dimensione del vocabolario nei modelli di produzione

Il vocabolario finale è la somma dei caratteri base più il numero di merge rules apprese. Con 300 caratteri base e 10.000 merge, ottieni ~10.300 token. I modelli reali usano dimensioni molto più grandi:

Modello	Token nel vocabolario
GPT-2	50.257
LLaMA 2	32.000
LLaMA 3	128.256
GPT-4	~100.000

Un vocabolario più grande significa sequenze più corte — "internazionalizzazione" diventa forse 3 token invece di 21 — il che riduce la quantità di contesto che il modello deve processare per capire una frase. Ma significa anche una matrice di embedding più grande in memoria. Il numero di merge rules è un iperparametro che bilancia questi due fattori.

Un dettaglio importante: i modelli di produzione usano byte-level BPE, dove il vocabolario base non sono i caratteri Unicode ma i 256 byte possibili. Questo garantisce che qualsiasi stringa — qualsiasi lingua, qualsiasi emoji, qualsiasi sequenza di byte — sia sempre rappresentabile senza </w> e senza fallback a caratteri sconosciuti.

Conclusione

BPE ha risolto in modo elegante uno dei problemi fondamentali dell'NLP: come rappresentare un vocabolario aperto con un insieme finito e gestibile di token. La soluzione non viene da una formula matematica sofisticata, ma da un algoritmo greedy su frequenze, applicato iterativamente.

La cosa affascinante è che nessuno ha insegnato all'algoritmo cosa sono i morfemi, i prefissi, i suffissi. Li ha scoperti da solo, contando le coppie. La linguistica è emersa dalla statistica.