> golomb | compressione | ottimale <
// Codifica Golomb - Compressione ottimale degli interi con divisore flessibile
>> funzionalità
Divisore flessibile
Scegli qualsiasi valore M per la massima efficienza di compressione.
Binario troncato
Utilizza il numero minimo di bit per codificare il resto.
Uso generico
Funziona con qualsiasi distribuzione di interi non negativi.
>> informazioni tecniche
Come funziona la codifica Golomb
La codifica Golomb divide ogni intero n per un divisore M per ottenere quoziente q e resto r. Il quoziente viene codificato in modo unario e il resto con binario troncato, usando il numero minimo di bit necessario per rappresentare i valori di M. Questo produce un codice ottimale per distribuzioni geometriche con parametro p = 1/M.
Esempio di codifica Golomb (M=5)
M=5, b=⌈log₂(5)⌉=3, c=2³-5=3 0 → q=0, r=0 → 0|00 → 000 (2 bit per r<3) 1 → q=0, r=1 → 0|01 → 001 (2 bit per r<3) 2 → q=0, r=2 → 0|10 → 010 (2 bit per r<3) 3 → q=0, r=3 → 0|110 → 0110 (3 bit per r≥3) 4 → q=0, r=4 → 0|111 → 0111 (3 bit per r≥3) 5 → q=1, r=0 → 10|00 → 1000 6 → q=1, r=1 → 10|01 → 1001 7 → q=1, r=2 → 10|10 → 1010 Binario troncato: r<3 usa 2 bit, r≥3 usa 3 bit
Perché usare la codifica Golomb
- Ottimale per distribuzioni geometriche
- Parametro M flessibile
- Uso minimo di bit
- Implementazione semplice
- Ottimalità dimostrata
>> domande frequenti
Che cos'è la codifica Golomb?
La codifica Golomb è un codice ottimale, a lunghezza variabile e privo di prefisso per distribuzioni geometriche. Divide gli interi tramite un parametro regolabile M, codificando il quoziente in unario e il resto in binario troncato, ottenendo una compressione ottimale per dati che seguono P(n) = (1-p)^n × p.
Come scegliere il parametro M?
Il valore ottimale di M dipende dal parametro geometrico p dei dati. Per dati con media μ, M ottimale ≈ μ + 1. Per probabilità che decrescono esponenzialmente con parametro p, il valore ottimale è M = ⌈-1/log₂(1-p)⌉. Usa la funzione di analisi per trovare il miglior M per i tuoi dati.
Che cos'è il binario troncato?
Il binario troncato minimizza i bit necessari per codificare uno dei M valori possibili. Se M è una potenza di 2 si usa il binario standard. Altrimenti alcuni valori usano ⌊log₂M⌋ bit e altri ⌈log₂M⌉ bit, garantendo decodifica univoca con lunghezza media minima.
Dove viene usata la codifica Golomb?
La codifica Golomb viene utilizzata nella compressione di immagini JPEG-LS, nella codifica video H.264 (come Exp-Golomb) e in formati audio lossless. È ideale per la codifica delle lunghezze di run, per i residui dopo la predizione e per qualunque dato con distribuzioni geometriche o esponenziali.