Golomb Coding: l’algoritmo di compressione che rende i dati più leggeri senza sforzo

Golomb Coding: quando la matematica incontra la compressione

Non tutti i dati si comprimono allo stesso modo. Algoritmi come gzip o LZ4 funzionano bene nella maggior parte dei casi, ma perdono efficienza quando i valori seguono una distribuzione precisa. È qui che entra in gioco Golomb coding, una tecnica lossless sviluppata negli anni '60 da Solomon W. Golomb e ancora oggi sorprendentemente efficace.

Il suo punto di forza sta nella specializzazione. Non cerca di essere il migliore in assoluto. Eccelle solo quando i dati seguono una distribuzione geometrica, cioè quando i valori piccoli compaiono molto più spesso di quelli grandi.

Perché conta la distribuzione geometrica

Molti dataset reali mostrano questo comportamento. Nei protocolli di rete, la maggior parte delle connessioni riesce al primo tentativo. Nel video, le differenze tra frame sono di solito minime. Nei log, gli errori gravi sono rari rispetto a quelli banali.

Golomb coding sfrutta proprio questo squilibrio. Assegna codici brevi ai valori frequenti e codici più lunghi a quelli rari, ottenendo risultati che i metodi a lunghezza variabile faticano a eguagliare.

Il funzionamento in pratica

L'algoritmo usa un parametro M per dividere ogni numero in quoziente e resto. Il quoziente viene codificato in unario, il resto in binario. Questa combinazione permette di rappresentare i numeri con il minor numero possibile di bit.

Per chi sviluppa, il vantaggio è chiaro: se i valori piccoli dominano, Golomb coding può superare gli algoritmi generici riducendo anche il carico sulla CPU.

Rice coding: la variante ottimizzata

Robert F. Rice ha preso l'idea originale e l'ha resa più pratica. La sua versione, Rice coding, impone che M sia sempre una potenza di due. Questo vincolo trasforma divisioni e moduli in semplici operazioni bitwise.

Su hardware moderno, gli shift e le maschere di bit costano pochissimo. Il risultato è una compressione veloce senza sacrificare troppo l'efficienza.

Dove si usano ancora oggi

Nonostante l'età, questi metodi sono presenti in diversi contesti moderni:

• Nei codec video H.264 e H.265 per codificare elementi di sintassi
• Nella compressione audio per la voce
• Nell'analisi di sequenze genomiche, dove certe basi ricorrono più spesso
• Nei dispositivi IoT per ridurre il traffico dati
• Nei sistemi embedded dove ogni ciclo di CPU è prezioso

I vantaggi per gli sviluppatori

Golomb e Rice coding offrono alcuni benefici concreti:

• Semplicità: serve solo un parametro da configurare
• Velocità: operazioni O(1) sia in codifica che in decodifica
• Leggerezza: niente tabelle di lookup o strutture complesse
• Riproducibilità: il risultato è sempre identico a parità di input

Quando evitarli

Non sono adatti a tutto. Se i valori sono distribuiti in modo uniforme o normale, questi algoritmi possono peggiorare le dimensioni. Funzionano solo quando l'ipotesi geometrica è valida.

Per dati arbitrari, gli algoritmi adattivi spesso ottengono rapporti di compressione migliori. Se invece serve il massimo risparmio possibile, LZMA o Zstandard restano scelte più adatte.

Un approccio mirato

Golomb coding dimostra un principio semplice: capire la natura dei propri dati permette di costruire soluzioni più leggere e veloci. In un periodo dominato dall'intelligenza artificiale, è interessante vedere come un algoritmo degli anni '60 resti utile proprio perché alcuni problemi non sono cambiati.

La prossima volta che noti che i valori piccoli dominano nel tuo dataset, chiediti se Golomb o Rice coding possano offrirti un vantaggio senza complicazioni inutili. A volte le soluzioni più vecchie sono ancora quelle giuste.