Comments for post Codifica delta (delta encoding)

motrini writes: 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
Blumbo writes: 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
antirez writes: 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.
Blumbo writes: 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
antirez writes: @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.
Simone Carletti writes: 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?
antirez writes: 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 :)
antirez writes: @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.
neon writes: @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.
88High writes: 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...
havana writes: 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?
antirez writes: @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.
neon writes: Interessante, fra le possibili codifiche ha la qualità di rimanere anche umanamente comprensibile.
home