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)
Do you like this article?
Subscribe to the RSS feed of this blog or use the newsletter service in order to receive a notification every time there is something of new to read here.
Note: you'll not see this box again if you are a usual reader.
Subscribe to the RSS feed of this blog or use the newsletter service in order to receive a notification every time there is something of new to read here.
Note: you'll not see this box again if you are a usual reader.
Comments
1
24 Apr 07, 07:17:53
Interessante, fra le possibili codifiche ha la qualità di rimanere anche umanamente comprensibile.
24 Apr 07, 07:21:23
@neon: gia', e questa caratteristica e' di vitale importanza durante la programmazione, anche se una visione un po' ingegneristica potrebbe far credere che la codifica migliore e' sempre quella piu' compatta. Un compromesso che utilizza solo semplici algoritmi, semplice codice, rimane leggibile, e arriva quasi agli stessi risultati e' assolutamente preferibile nella pratica.
24 Apr 07, 07:59:56
Bello, questa codifica per comprimere mi è piaciuta, ma ho una domanda.
Se per caso si ha una corruzione dei dati e si perde un valore, è palese che tutto il resto sara' errato o illegibile.
Se si vuole rendere questa codifica più sicura come si potrebbe procedere?
bit di parità?
altro?
Se per caso si ha una corruzione dei dati e si perde un valore, è palese che tutto il resto sara' errato o illegibile.
Se si vuole rendere questa codifica più sicura come si potrebbe procedere?
bit di parità?
altro?
24 Apr 07, 09:19:03
Un'alternativa potrebbe essere quella di fare riferimento per le differenze solo al primo elemento
ad esempio
1000,1004,997,1033,821
diventa
1000,4,-3,33,179
in questo modo anche se si perde un elemento (a meno che non sia il primo) non tutto è perduto...
...vabbé è una scemenza...
ad esempio
1000,1004,997,1033,821
diventa
1000,4,-3,33,179
in questo modo anche se si perde un elemento (a meno che non sia il primo) non tutto è perduto...
...vabbé è una scemenza...
24 Apr 07, 09:45:14
@88High: E' una soluzione. In questo modo se devi calcolare l'elemento N non hai bisogno di conoscere l'N-1 ma solo il primo.
Solo che perdi la compressione. A meno che i valori non sono molto grandi e molto vicini.
es: 0-10000 non hai compressione.
es2: 10000-11000 hai una buona (relativamente) compressione.
Solo che perdi la compressione. A meno che i valori non sono molto grandi e molto vicini.
es: 0-10000 non hai compressione.
es2: 10000-11000 hai una buona (relativamente) compressione.
24 Apr 07, 11:46:47
@havana: il modo migliore e' emettere di tanto in tanto (dipende dalla percentuale di dati che e' accettabile perdere) un elemento codificato interamente. Ad esempio ogni 50 elementi si emette l'elemento intero. In una circostanza in cui c'e' corruzione e' difficile dire qual'era il cinquantesimo elemento per cui si puo' emettere come valore negativo per essere distinguibile, tanto tutti i delta sono positivi.
@88High: in questo modo distruggi i vantaggi della codifica :) Pensa di codificare da 1000 a 2000 col tuo metodo e col metodo originale. Passi da 1000,1,1,1,1,1,1,1..... a 1000,1,2,3,4,5,6,7,8...,1000!
Allo stesso modo l'algoritmo originale recupera ogni volta che c'e' un grosso salto: emette un grosso delta e poi altri delta piccoli.
Visto che c'e' la soluzione di emettere di tanto in tanto l'elemento intero non c'e' alcuna necessita' di perdere la compressione.
@88High: in questo modo distruggi i vantaggi della codifica :) Pensa di codificare da 1000 a 2000 col tuo metodo e col metodo originale. Passi da 1000,1,1,1,1,1,1,1..... a 1000,1,2,3,4,5,6,7,8...,1000!
Allo stesso modo l'algoritmo originale recupera ogni volta che c'e' un grosso salto: emette un grosso delta e poi altri delta piccoli.
Visto che c'e' la soluzione di emettere di tanto in tanto l'elemento intero non c'e' alcuna necessita' di perdere la compressione.
24 Apr 07, 11:49:28
Giusto una idea: in realta' la compressione delta non e' necessariamente legata alla sottrazione, il delta si puo' esprimere anche come prodotto, e in questo caso ogni elemento sara' il numero per cui bisogna moltiplicare il precedente per ottenere il nuovo. Ora una modifica a questa tecnica e' quella di usare un fattore moltiplicativo arrotondato per avere una precisione massima bassa: in questo modo abbiamo trasformato la codifica delta che e' un algoritmo di compressione senza perdite in una codifica di tipo "lossy" in cui si puo' comprimere quanto si vuole ma perdendo precisione. Mi sembrava interessante l'idea di generalizzare la tecnica, probabilmente questa cosa e' trattata in letteratura da qualche parte, se qualcuno avesse riferimenti li spari qui come commmento :)
24 Apr 07, 16:33:18
Molto interessante e, soprattutto, l'articolo è spiegato in modo eccezionalmente chiaro.
Una domanda: antirez hai già avuto modo di applicarla a qualche tuo progetto in modo utile da valutarne il reale vantaggio rispetto al tempo necessario per processare un algoritmo che codifichi/decodifichi l'informazione?
Una domanda: antirez hai già avuto modo di applicarla a qualche tuo progetto in modo utile da valutarne il reale vantaggio rispetto al tempo necessario per processare un algoritmo che codifichi/decodifichi l'informazione?
25 Apr 07, 14:38:11
@Simone Carletti: ciao Simone, grazie, come ho scritto nell'ultimo paragrafo su oknotizie e' usato proprio questo sistema nel caso dei voti anonimi che stanno in un cookie oltre che sul DB in modo da permettere un determinato meccanismo di caching.
29 Feb 08, 07:23:27
Ciao, io ho una domanda. Se ho un array di interi da 4 byte del tipo:
67497, 67376, 67173, 67235, ....
come faccio a comprimere questi dati su interi da 2 byte usando la compressione delta? Con 2 byte il valore massimo senza segno è 65535, mentre il mio primo elemento è 67497... La sequenza sarebbe:
67497 -121 -203 62
Inoltre avrei bisogno del segno per memorizzare i dati, quindi non potrei usare un unsigned int.
Forse nel mio caso dovrei definire un altro tipo di delta, boh, voi come fareste? Grazie
67497, 67376, 67173, 67235, ....
come faccio a comprimere questi dati su interi da 2 byte usando la compressione delta? Con 2 byte il valore massimo senza segno è 65535, mentre il mio primo elemento è 67497... La sequenza sarebbe:
67497 -121 -203 62
Inoltre avrei bisogno del segno per memorizzare i dati, quindi non potrei usare un unsigned int.
Forse nel mio caso dovrei definire un altro tipo di delta, boh, voi come fareste? Grazie
29 Feb 08, 07:36:58
Ciao Blumbo, secondo me una delle cose migliori che puoi fare e' riservare un valore di 2 byte, tipo il piu' alto o il piu' basso, da usare per indicare "il prossimo valore e' uno intero di 4 byte da leggere non come differenza ma come valore". In questo modo risolvi sia il problema della "partenza" che tutti gli incrementi in cui 16 bit signed non ti sarebbero bastati come nella sequenza di esempio -1233 400000 -38 e cosi' via.
29 Feb 08, 07:59:02
Se ho capito bene però così facendo non potrei avere un unico array che contiene tutti i dati compressi, perchè sarebbero interi misti da 2 e 4 byte (correggimi se sbaglio...). Invece vorrei continuare ad avere un unico array in uscita, una cosa a cui stavo pensando è di usare una sottrazione costante a tutti i valori, essendo compresi tutti tra 66000 e 67000. Potrei sottrarre 60000 a tutti i numeri e cosi otterrei una serie da 2 byte + un'altra variabile da 2 byte per memorizzare il delta costante 60000. Non so però quanto questa soluzione rientri in una codifica delta. In alternativa sapresti dirmi quali sono le definizioni dei delta che vengono usati comunemente? Su wikipedia ho trovato per esempio una strana definizione di un delta simmetrico, che non ho proprio capito. Grazie
04 Mar 08, 13:44:34
ciao, non ti posso essere utile sullo specifico ma solo sul delta simmetrico di wikipedia. la formula si legge: il delta degli insiemi v1 e v2 è dato dall'unione (U) degli elementi di v1 che non appartengono a v2 (v1-v2)e degli elementi di v2 che non appartengono a v1 (v2-v1). praticamente elimini tutti gli elementi in comune