Frequency-Ordered Tokenization for Better Text Compression

1. Il Problema

La compressione lossless del testo è fondamentale nell'informatica moderna. Sebbene esistano compressori statistici avanzati (come cmix o NNCP) che raggiungono rapporti di compressione eccezionali, il loro costo computazionale è proibitivo (100-1000 volte superiore a quello dei compressori pratici).
I compressori standard basati su dizionari (famiglia LZ77 come zlib, zstd, LZMA) funzionano identificando pattern ripetuti di byte tramite riferimenti a finestre scorrevoli. Tuttavia, questi algoritmi non modellano esplicitamente le frequenze dei byte. Poiché il linguaggio naturale segue la Legge di Zipf (una distribuzione di potenza dove poche parole/token sono estremamente frequenti e molte sono rare), i compressori LZ standard non sfruttano appieno questa concentrazione statistica, lasciando spazio per miglioramenti tramite pre-elaborazione.

2. Metodologia: Tokenizzazione Ordinata per Frequenza

Gli autori propongono una tecnica di pre-elaborazione semplice ma efficace che trasforma il testo in una rappresentazione più adatta alla compressione LZ. Il processo si articola in tre fasi principali:

1. Tokenizzazione BPE (Byte Pair Encoding): Il testo viene suddiviso in sottoparole (token) utilizzando un tokenizzatore BPE standard (adottato dai grandi modelli linguistici). Questo gestisce le variazioni morfologiche e i caratteri non latini senza regole specifiche per lingua.
2. Ordinamento per Frequenza: Viene calcolata la frequenza di ogni token nel corpus. Il vocabolario viene riordinato in modo che i token più frequenti ricevano ID interi piccoli (es. 0, 1, 2...), mentre quelli rari ricevano ID più grandi.
3. Codifica Varint (LEB128): Gli ID dei token vengono codificati utilizzando una codifica a lunghezza variabile (Variable-Length Integer).
   • Gli ID piccoli (0-127) occupano 1 byte.
   • Gli ID medi (128-16.383) occupano 2 byte.
   • Gli ID grandi occupano 3+ byte.

Risultato del pre-processing: Poiché la maggior parte dei token in un testo naturale è frequente (grazie alla Legge di Zipf), la maggior parte del flusso di dati in uscita consiste in byte singoli (0-127). Questo crea un flusso di byte altamente ripetitivo e concentrato su valori bassi, che i compressori LZ possono comprimere molto più efficientemente rispetto al testo UTF-8 grezzo.

3. Contributi Chiave

1. Miglioramento dei Rapporti di Compressione: La tecnica migliora i compressori della famiglia LZ da 1 a 7 punti percentuali (pp) su benchmark standard (enwik8/enwik9), superando le trasformazioni classiche come il Word Replacing Transform (WRT).
2. Pareto Improvement (Velocità/Rapporto): Per compressori computazionalmente costosi (zstd-22 e LZMA), il pre-processing accelera il processo di compressione totale. Sebbene il pre-processing aggiunga un overhead, la riduzione delle dimensioni dell'input (da 100 MB di testo a ~41 MB di stream varint) riduce drasticamente il tempo di compressione, offrendo sia un rapporto migliore che una velocità superiore.
3. Generalizzazione Cross-Lingua: Il metodo funziona efficacemente su testi in inglese, cinese e arabo, dimostrando che la tokenizzazione BPE gestisce bene le variazioni morfologiche e gli script non latini senza regole specifiche.
4. Semplicità Implementativa: L'algoritmo richiede meno di 50 righe di codice, non necessita di reti neurali o parametri appresi oltre al vocabolario del tokenizzatore, e non modifica gli algoritmi di compressione esistenti.

4. Risultati Sperimentali

I test sono stati condotti su enwik8 (100 MB di Wikipedia) e enwik9 (1 GB).

• Miglioramenti sul rapporto di compressione (incluso l'overhead del vocabolario):

  • zlib-9: +7.08 pp (da 36.48% a 29.40%).
  • LZMA: +1.69 pp (da 26.38% a 24.69%).
  • zstd-22: +0.76 pp (da 25.27% a 24.51%).
  • Nota: I compressori statistici come PPMd e BWT (bz2) non beneficiano o peggiorano leggermente, poiché modellano già le frequenze o le strutture contestuali in modo diverso.

• Velocità di Compressione:

  • Per zstd-22, il tempo totale scende da 95.5s a 30.5s (3.1x più veloce).
  • Per LZMA, il tempo scende da 89.8s a 37.6s (2.4x più veloce).
  • Questo accade perché l'input pre-processato è più piccolo e ha una struttura statistica più semplice, riducendo il tempo di ricerca delle corrispondenze (match-finding) per l'algoritmo LZ.

• Analisi Teorica:

  • L'analisi informa-teorica conferma che, con un esponente di Zipf $\alpha \approx 1.04$, circa il 45.7% dei token richiede solo 1 byte dopo la riordinazione, contro il 13.6% del testo grezzo.

5. Significato e Implicazioni

Il paper dimostra che l'ordinamento intelligente dei token basato sulla frequenza è un metodo potente per colmare il divario tra i compressori pratici (LZ) e quelli statistici avanzati, senza il costo computazionale di questi ultimi.

• Efficienza Scalabile: Il metodo è particolarmente vantaggioso per carichi di lavoro di archiviazione (write-heavy) dove il rapporto di compressione e la velocità di scrittura sono critici.
• Limiti: Il metodo richiede una passata completa sui dati per calcolare le frequenze (non adatto allo streaming in tempo reale singolo passaggio) e l'overhead del vocabolario (circa 0.2% su enwik8), sebbene questo sia ammortizzabile su grandi dataset o vocabolari condivisi.
• Futuro: Apre la strada a tokenizzatori "consapevoli della compressione" e all'adattamento dei parametri dei compressori alle statistiche del flusso pre-processato.

In sintesi, la Frequency-Ordered Tokenization è una tecnica di pre-elaborazione a basso costo che sfrutta le proprietà universali del linguaggio naturale per potenziare significativamente i compressori standard, offrendo miglioramenti sia nella dimensione che nella velocità per gli algoritmi più pesanti.