Codifica delta (delta encoding)
Tuesday, 24 April 07
La codifica delta, assieme a quella run length, rappresenta sicuramente uno dei piu' semplici metodi di compressione disponibili. E' interessante nella pratica perche' funziona abbastanza bene per comprimere liste di numeri che potrebbero essere agevolmente memorizzate in formato testo, ad esempio in un cookie.
La codifica delta e' affascinante perche' in alcuni contesti funziona bene nonostante l'estrema semplicita' dell'algoritmo. L'idea e' la seguente: si immagini di dover registrare in un cookie o da qualunque altra parte una lista di numeri interi. Ad esempio potremmo voler segnare in un cookie gli ID (numeri interi che identificano una data risorsa) di tutti gli articoli che un lettore ha visitato sul nostro blog.
Questi ID potrebbero ad esempio essere i seguenti:
1000,1004,997,1033,821Il modo piu' ovvio di registrarli e' quello di separarli uno dall'altro tramite una virgola proprio come ho fatto io scrivendoli in questo articolo e registrarli cosi' come sono. Nella pratica lo spazio e' finito e tanto piu' i numeri sono grandi tanto maggiore e' lo spazio necessario per registrarli. Eppure le loro differenze relative potrebbero essere piccole proprio come nel nostro esempio: la differenza tra 1004 e 1000 e' 4, tra 997 e 1004 e' -7, e cosi' via.
Il delta encoding sfrutta proprio questa osservazione, e registra la differenza tra i dati invece che registrare ogni singolo dato.
Tramite la codifica per differenza la precedente lista sarebbe scritta cosi':
1000,4,-7,36,-212Ovviamente il primo elemento non puo' essere encodato perche' non esiste il suo precedente (per chi si sente male se non generalizza diciamo che l'elemento a sinistra si assume abbia valore zero ;).
La nuova codifica ci fa risparmiare la bellezza di 5 caratteri! Ma possiamo fare di piu'. La miglioria da introdurre sorge spontanea se ragioniamo cosi':
Tanto piu' la differenza tra un dato e il suo successivo e' piccola, tanto piu' la codifica per differenza ci fa risparmiare spazio. Possiamo applicare una trasformazione alla lista originale per minimizzare la differenza tra i suoi elementi adiacenti?
Ovviamente si! basta ordinare gli elementi dal piu' piccolo al piu' grande.
Dopo l'ordinamento la lista diventa:
821,997,1000,1004,1033La cui codifica per differenza e':
821,3,4,29Che richiede meno della meta' dello spazio, e tutto quello che c'e' voluto sono state un paio di sottrazioni!
Nella pratica
La necessita' di segnare in un cookie una serie di identificativi numerici e' molto comune. Spesso questi ID sono molto grandi ma hanno differenze relative piccole (perche' frutto di una tabella auto-incrementale di un database che contiene molti dati), come nel caso dei post di oknotizie e della memorizzazione degli ID delle notizie votate dai visitatori anonimi: viene usato proprio questo metodo per codificare le informazioni nel cookie, e il guadagno ottenuto e' molto sensibile.Per approfondire
- La codifica delta secondo wikipedia (italiano)
- Codifica incrementale, una variazione del delta encoding molto scaltra utile per comprimere elenchi ordinati di parole. (inglese)