Miglior algoritmo di compressione per una sequenza di numeri interi

Ho una grande matrice con un intervallo di interi che sono per lo più continui, ad es. 1-100, 110-160, ecc. Tutti gli interi sono positivi. Quale sarebbe il miglior algoritmo per comprimere questo?

Ho provato l’algoritmo di deflate ma questo mi dà solo il 50% di compressione. Si noti che l’algoritmo non può essere lossy.

Tutti i numeri sono unici e in progressivo aumento.

Inoltre, se puoi indicarmi l’implementazione java di tale algoritmo sarebbe fantastico.

Abbiamo scritto documenti di ricerca recenti che esaminano i migliori schemi per questo problema. Perfavore guarda:

Daniel Lemire e Leonid Boytsov, Decodificare miliardi di interi al secondo attraverso la vettorizzazione, Software: Practice & Experience 45 (1), 2015. http://arxiv.org/abs/1209.2137

Daniel Lemire, Nathan Kurz, Leonid Boytsov, SIMD Compression e Intersection of Sorted Integers, Software: Practice and Experience (per apparire) http://arxiv.org/abs/1401.6399

Includono un’ampia valutazione sperimentale.

Puoi trovare un’implementazione completa di tutte le tecniche in C ++ 11 online: https://github.com/lemire/FastPFor e https://github.com/lemire/SIMDCompressionAndIntersection

Ci sono anche librerie C: https://github.com/lemire/simdcomp e https://github.com/lemire/MaskedVByte

Se si preferisce Java, consultare https://github.com/lemire/JavaFastPFOR

Innanzitutto, preelaborare l’elenco di valori prendendo la differenza tra ciascun valore e quello precedente (per il primo valore, si supponga che il precedente fosse zero). Questo dovrebbe nel tuo caso dare una sequenza in gran parte, che può essere compressa molto più facilmente dalla maggior parte degli algoritmi di compressione.

Questo è il modo in cui il formato PNG migliora la compressione (fa uno dei tanti metodi diversi seguiti dallo stesso algoritmo di compressione usato da gzip).

Bene, sto votando per un modo più intelligente. Tutto ciò che devi memorizzare è [int: startnumber] [int / byte / whatever: numero di iterazioni] in questo caso, trasformsrai l’array di esempio in valore 4xInt. Dopo di esso puoi comprimere come vuoi 🙂

Sebbene sia ansible progettare un algoritmo personalizzato specifico per il stream di dati, è probabilmente più semplice utilizzare un algoritmo di codifica off-the-shelf. Ho eseguito alcuni test sugli algoritmi di compressione disponibili in Java e ho trovato i seguenti tassi di compressione per una sequenza di un milione di numeri interi consecutivi:

None 1.0 Deflate 0.50 Filtered 0.34 BZip2 0.11 Lzma 0.06 

Di che taglia sono i numeri? Oltre alle altre risposte, potresti prendere in considerazione la codifica in base alla variante 128 della base, che ti consente di memorizzare numeri più piccoli in byte singoli pur consentendo numeri più grandi. Il MSB significa “c’è un altro byte” – questo è descritto qui.

Combina questo con le altre tecniche in modo da memorizzare “salta dimensione”, “prendi taglia”, “salta dimensione”, “prendi taglia”, ma osservando che né “salta” né “prendi” saranno mai pari a zero, quindi faremo sottrarre uno da ciascuno (che consente di salvare un byte in più per una manciata di valori)

Così:

 1-100, 110-160 

è “salta 1” (assumere inizio a zero in quanto rende le cose più facili), “prendi 100”, “salta 9”, “prendi 51”; sottrarre 1 da ciascuno, dando (come decimale)

 0,99,8,50 

che codifica come (esadecimale):

 00 63 08 32 

Se volessimo saltare / prendere un numero maggiore – 300, ad esempio; sottraiamo 1 dando 299 – ma che supera i 7 bit; partendo dalla piccola parte, codifichiamo blocchi di 7 bit e un MSB per indicare la continuazione:

 299 = 100101100 = (in blocks of 7): 0000010 0101100 

quindi partendo dalla piccola parte:

 1 0101100 (leading one since continuation) 0 0000010 (leading zero as no more) 

dando:

 AC 02 

Così possiamo codificare grandi numeri facilmente, ma i numeri piccoli (che suonano tipici di skip / take) occupano meno spazio.

Potresti provare a farlo attraverso “deflate”, ma potrebbe non essere di aiuto molto di più …


Se non vuoi gestire tutta questa codifica disordinata … se riesci a creare l’array intero dei valori (0,99,8,60), potresti utilizzare i buffer di protocollo con un uint32 ripetuto / uint64 – e farà tutto il lavoro per te ;-p

Io non “faccio” Java, ma qui c’è un’implementazione completa di C # (prendendo in prestito alcuni dei bit di codifica dal mio progetto protobuf-net ):

 using System; using System.Collections.Generic; using System.IO; using System.Linq; static class Program { static void Main() { var data = new List(); data.AddRange(Enumerable.Range(1, 100)); data.AddRange(Enumerable.Range(110, 51)); int[] arr = data.ToArray(), arr2; using (MemoryStream ms = new MemoryStream()) { Encode(ms, arr); ShowRaw(ms.GetBuffer(), (int)ms.Length); ms.Position = 0; // rewind to read it... arr2 = Decode(ms); } } static void ShowRaw(byte[] buffer, int len) { for (int i = 0; i < len; i++) { Console.Write(buffer[i].ToString("X2")); } Console.WriteLine(); } static int[] Decode(Stream stream) { var list = new List(); uint skip, take; int last = 0; while (TryDecodeUInt32(stream, out skip) && TryDecodeUInt32(stream, out take)) { last += (int)skip+1; for(uint i = 0 ; i <= take ; i++) { list.Add(last++); } } return list.ToArray(); } static int Encode(Stream stream, int[] data) { if (data.Length == 0) return 0; byte[] buffer = new byte[10]; int last = -1, len = 0; for (int i = 0; i < data.Length; ) { int gap = data[i] - 2 - last, size = 0; while (++i < data.Length && data[i] == data[i - 1] + 1) size++; last = data[i - 1]; len += EncodeUInt32((uint)gap, buffer, stream) + EncodeUInt32((uint)size, buffer, stream); } return len; } public static int EncodeUInt32(uint value, byte[] buffer, Stream stream) { int count = 0, index = 0; do { buffer[index++] = (byte)((value & 0x7F) | 0x80); value >>= 7; count++; } while (value != 0); buffer[index - 1] &= 0x7F; stream.Write(buffer, 0, count); return count; } public static bool TryDecodeUInt32(Stream source, out uint value) { int b = source.ReadByte(); if (b < 0) { value = 0; return false; } if ((b & 0x80) == 0) { // single-byte value = (uint)b; return true; } int shift = 7; value = (uint)(b & 0x7F); bool keepGoing; int i = 0; do { b = source.ReadByte(); if (b < 0) throw new EndOfStreamException(); i++; keepGoing = (b & 0x80) != 0; value |= ((uint)(b & 0x7F)) << shift; shift += 7; } while (keepGoing && i < 4); if (keepGoing && i == 4) { throw new OverflowException(); } return true; } } 

comprimere la stringa “1-100, 110-160” o memorizzare la stringa in una rappresentazione binaria e analizzarla per ripristinare la matrice

Oltre alle altre soluzioni:

È ansible trovare aree “dense” e utilizzare una bitmap per memorizzarle.

Quindi per esempio:

Se hai 1000 numeri in 400 intervalli tra 1000-3000, potresti usare un singolo bit per denotare l’esistenza di un numero e due inte per denotare l’intervallo. La memoria totale per questo intervallo è di 2000 bit + 2 pollici, quindi è ansible archiviare tali informazioni in 254 byte, il che è davvero fantastico poiché anche gli interi brevi occuperanno due byte ciascuno, quindi per questo esempio si ottiene un risparmio di 7 volte.

Più densa sono le aree, migliore sarà l’algoritmo, ma a un certo punto la semplice memorizzazione di inizio e fine sarà più economica.

Combinerei le risposte fornite da CesarB e Fernando Miguélez.

Per prima cosa, memorizza le differenze tra ogni valore e quello precedente. Come ha sottolineato CesarB, questo ti darà una sequenza per lo più di una.

Quindi, utilizzare un algoritmo di compressione Codifica lunghezza esecuzione in questa sequenza. Si comprimerà molto bene a causa del gran numero di valori ripetuti.

Suggerirei di dare un’occhiata a Huffman Coding , un caso speciale di Arithmetic Coding . In entrambi i casi si analizza la sequenza di partenza per determinare le frequenze relative di valori diversi. I valori più frequenti si codificano con meno bit di quelli meno frequenti.

L’idea di base che dovresti probabilmente usare è, per ogni intervallo di interi consecutivi (chiamerò questi intervalli), per memorizzare il numero iniziale e la dimensione dell’intervallo. Ad esempio, se si ha una lista di 1000 numeri interi, ma ci sono solo 10 intervalli separati, è ansible memorizzare solo 20 numeri interi (1 numero iniziale e 1 dimensione per ciascun intervallo) per rappresentare questi dati che sarebbero un tasso di compressione di 98 %. Fortunatamente, sono disponibili altre ottimizzazioni che possono essere utili nei casi in cui il numero di intervalli è maggiore.

  1. Memorizza l’offset del numero iniziale rispetto al numero iniziale precedente, piuttosto che il numero iniziale stesso. Il vantaggio qui è che i numeri che immagazzini generalmente richiedono meno bit (questo può tornare utile nei suggerimenti di ottimizzazione successivi). Inoltre, se si memorizzano solo i numeri iniziali, questi numeri saranno tutti unici, mentre la memorizzazione dell’offset dà la possibilità che i numeri siano vicini o addirittura ripetuti, il che potrebbe consentire un’ulteriore compressione con un altro metodo applicato successivamente.

  2. Utilizza il numero minimo di bit ansible per entrambi i tipi di numeri interi. È ansible scorrere i numeri per ottenere l’offset più grande di un numero intero iniziale nonché le dimensioni dell’intervallo più grande. È quindi ansible utilizzare un tipo di dati che memorizza in modo più efficiente questi numeri interi e specificare semplicemente il tipo di dati o il numero di bit all’inizio dei dati compressi. Ad esempio, se l’offset maggiore di un numero intero iniziale è solo 12.000 e l’intervallo più lungo è 9.000, è ansible utilizzare un numero intero senza segno a 2 byte per tutti questi valori. Si potrebbe quindi racchiudere la coppia 2,2 all’inizio dei dati compressi per mostrare che 2 byte vengono utilizzati per entrambi i numeri interi. Ovviamente è ansible inserire queste informazioni in un singolo byte usando un po ‘di manipolazione dei bit. Se si ha familiarità con l’esecuzione di molte manipolazioni di bit pesanti, è ansible memorizzare ciascun numero come la quantità minima ansible di bit anziché conformarsi a rappresentazioni a 1, 2, 4 o 8 byte.

Con queste due ottimizzazioni vediamo un paio di esempi (ognuno è di 4.000 byte):

  1. 1.000 interi, l’offset maggiore è di 500, 10 intervalli
  2. 1.000 interi, l’offset maggiore è di 100, 50 intervalli
  3. 1.000 interi, l’offset maggiore è 50, 100 intervalli

SENZA OTTIMIZZAZIONI

  1. 20 numeri interi, 4 byte ciascuno = 80 byte. COMPRESSIONE = 98%
  2. 100 interi, 4 byte ciascuno = 400 byte. COMPRESSIONE = 90%
  3. 200 numeri interi, 4 byte ciascuno = 800 byte. COMPRESSIONE = 80%

CON OTTIMIZZAZIONI

  1. Intestazione 1 byte + 20 numeri, 1 byte ciascuno = 21 byte. COMPRESSIONE = 99,475%
  2. Intestazione 1 byte + 100 numeri, 1 byte ciascuno = 101 byte. COMPRESSIONE = 97,475%
  3. Intestazione 1 byte + 200 numeri, 1 byte ciascuno = 201 byte. COMPRESSIONE = 94,975%

Il tuo caso è molto simile alla compressione degli indici nei motori di ricerca. Il famoso algoritmo di compressione utilizzato è l’algoritmo PForDelta e l’algoritmo Simple16. Puoi usare la libreria kamikaze per le tue esigenze di compressione.

Se hai serie di valori ripetuti, RLE è il più facile da implementare e potrebbe darti un buon risultato. Tuttavia altri algoritmi più avanzati che prendono in considerazione l’entrophy come LZW, che ora è privo di brevetti, possono solitamente ottenere una compressione molto migliore.

Puoi dare un’occhiata a questi e altri algoritmi senza perdita qui .

So che questa è una vecchia discussione di messaggi, ma sto includendo il mio test PHP personale dell’idea SKIP / TAKE che ho trovato qui. Sto chiamando il mio STEP (+) / SPAN (-). Forse qualcuno potrebbe trovarlo utile.

NOTA: ho implementato la capacità di consentire interi duplicati e interi negativi anche se la domanda originale riguardava numeri interi positivi e non duplicati. Sentiti libero di modificarlo se vuoi provare a radere un paio di byte.

CODICE:

  // $integers_array can contain any integers; no floating point, please. Duplicates okay. $integers_array = [118, 68, -9, 82, 67, -36, 15, 27, 26, 138, 45, 121, 72, 63, 73, -35, 68, 46, 37, -28, -12, 42, 101, 21, 35, 100, 44, 13, 125, 142, 36, 88, 113, -40, 40, -25, 116, -21, 123, -10, 43, 130, 7, 39, 69, 102, 24, 75, 64, 127, 109, 38, 41, -23, 21, -21, 101, 138, 51, 4, 93, -29, -13]; // Order from least to greatest... This routine does NOT save original order of integers. sort($integers_array, SORT_NUMERIC); // Start with the least value... NOTE: This removes the first value from the array. $start = $current = array_shift($integers_array); // This caps the end of the array, so we can easily get the last step or span value. array_push($integers_array, $start - 1); // Create the compressed array... $compressed_array = [$start]; foreach ($integers_array as $next_value) { // Range of $current to $next_value is our "skip" range. I call it a "step" instead. $step = $next_value - $current; if ($step == 1) { // Took a single step, wait to find the end of a series of seqential numbers. $current = $next_value; } else { // Range of $start to $current is our "take" range. I call it a "span" instead. $span = $current - $start; // If $span is positive, use "negative" to identify these as sequential numbers. if ($span > 0) array_push($compressed_array, -$span); // If $step is positive, move forward. If $step is zero, the number is duplicate. if ($step >= 0) array_push($compressed_array, $step); // In any case, we are resetting our start of potentialy sequential numbers. $start = $current = $next_value; } } // OPTIONAL: The following code attempts to compress things further in a variety of ways. // A quick check to see what pack size we can use. $largest_integer = max(max($compressed_array),-min($compressed_array)); if ($largest_integer < pow(2,7)) $pack_size = 'c'; elseif ($largest_integer < pow(2,15)) $pack_size = 's'; elseif ($largest_integer < pow(2,31)) $pack_size = 'l'; elseif ($largest_integer < pow(2,63)) $pack_size = 'q'; else die('Too freaking large, try something else!'); // NOTE: I did not implement the MSB feature mentioned by Marc Gravell. // I'm just pre-pending the $pack_size as the first byte, so I know how to unpack it. $packed_string = $pack_size; // Save compressed array to compressed string and binary packed string. $compressed_string = ''; foreach ($compressed_array as $value) { $compressed_string .= ($value < 0) ? $value : '+'.$value; $packed_string .= pack($pack_size, $value); } // We can possibly compress it more with gzip if there are lots of similar values. $gz_string = gzcompress($packed_string); // These were all just size tests I left in for you. $base64_string = base64_encode($packed_string); $gz64_string = base64_encode($gz_string); $compressed_string = trim($compressed_string,'+'); // Don't need leading '+'. echo "
\nOriginal Array has " .count($integers_array) .' elements: {not showing, since I modified the original array directly}'; echo "
\nCompressed Array has " .count($compressed_array).' elements: ' .implode(', ',$compressed_array); echo "
\nCompressed String has " .strlen($compressed_string).' characters: ' .$compressed_string; echo "
\nPacked String has " .strlen($packed_string).' (some probably not printable) characters: ' .$packed_string; echo "
\nBase64 String has " .strlen($base64_string).' (all printable) characters: ' .$base64_string; echo "
\nGZipped String has " .strlen($gz_string).' (some probably not printable) characters: ' .$gz_string; echo "
\nBase64 of GZipped String has " .strlen($gz64_string).' (all printable) characters: ' .$gz64_string; // NOTICE: The following code reverses the process, starting form the $compressed_array. // The first value is always the starting value. $current_value = array_shift($compressed_array); $uncompressed_array = [$current_value]; foreach ($compressed_array as $val) { if ($val < -1) { // For ranges that span more than two values, we have to fill in the values. $range = range($current_value + 1, $current_value - $val - 1); $uncompressed_array = array_merge($uncompressed_array, $range); } // Add the step value to the $current_value $current_value += abs($val); // Add the newly-determined $current_value to our list. If $val==0, it is a repeat! array_push($uncompressed_array, $current_value); } // Display the uncompressed array. echo "
Reconstituted Array has " .count($uncompressed_array).' elements: ' .implode(', ',$uncompressed_array). '
';

PRODUZIONE:

 -------------------------------------------------------------------------------- Original Array has 63 elements: {not showing, since I modified the original array directly} Compressed Array has 53 elements: -40, 4, -1, 6, -1, 3, 2, 2, 0, 8, -1, 2, -1, 13, 3, 6, 2, 6, 0, 3, 2, -1, 8, -11, 5, 12, -1, 3, -1, 0, -1, 3, -1, 2, 7, 6, 5, 7, -1, 0, -1, 7, 4, 3, 2, 3, 2, 2, 2, 3, 8, 0, 4 Compressed String has 110 characters: -40+4-1+6-1+3+2+2+0+8-1+2-1+13+3+6+2+6+0+3+2-1+8-11+5+12-1+3-1+0-1+3-1+2+7+6+5+7-1+0-1+7+4+3+2+3+2+2+2+3+8+0+4 Packed String has 54 (some probably not printable) characters: cØÿÿÿÿ ÿõ ÿÿÿÿÿÿ Base64 String has 72 (all printable) characters: Y9gE/wb/AwICAAj/Av8NAwYCBgADAv8I9QUM/wP/AP8D/wIHBgUH/wD/BwQDAgMCAgIDCAAE GZipped String has 53 (some probably not printable) characters: xœ Ê» ÑÈί€)YšE¨MŠ“^qçºR¬m&Òõ‹%Ê&TFʉùÀ6ÿÁÁ Æ Base64 of GZipped String has 72 (all printable) characters: eJwNyrsNACAMA9HIzq+AKVmaRahNipNecee6UgSsBW0m0gj1iyXKJlRGjcqJ+cA2/8HBDcY= -------------------------------------------------------------------------------- Reconstituted Array has 63 elements: -40, -36, -35, -29, -28, -25, -23, -21, -21, -13, -12, -10, -9, 4, 7, 13, 15, 21, 21, 24, 26, 27, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 51, 63, 64, 67, 68, 68, 69, 72, 73, 75, 82, 88, 93, 100, 101, 101, 102, 109, 113, 116, 118, 121, 123, 125, 127, 130, 138, 138, 142 -------------------------------------------------------------------------------- 

TurboPFor: compressione intera più veloce

  • per C / C ++ incluso Java Critical Natives / JNI Interface
  • SIMD ha accelerato la compressione dei numeri interi
  • Differenziale scalare + integrato (SIMD) / codifica / decodifica a zigzag per elenchi di interi ordinati / non ordinati
  • Elenchi di interger a 8/16/32/64 bit dell’intera gamma
  • Accesso diretto
  • Applicazione di riferimento

Non riuscivo a ottenere una compressione migliore di circa .11 per questo. Ho generato i miei dati di test tramite interprete python ed è una lista delimitata da numeri interi di numeri interi da 1 a 100 e da 110 a 160. Io uso il programma attuale come una rappresentazione compressa dei dati. Il mio file compresso è il seguente:

 main=mapM_ print [x|x<-[1..160],x`notElem`[101..109]] 

È solo uno script Haskell che genera il file che puoi eseguire tramite:

 $ runhaskell generator.hs >> data 

La dimensione del file g.hs è di 54 byte e i dati generati da python sono 496 byte. Questo dà 0.10887096774193548 come rapporto di compressione. Penso che con più tempo si potrebbe ridurre il programma, o si potrebbe comprimere il file compresso (cioè il file haskell).

Un altro approccio potrebbe essere quello di salvare 4 byte di dati. Il minimo e il massimo di ogni sequenza, quindi assegnarli a una funzione generatrice. Anche se il caricamento dei file aggiungerà più caratteri al decompressore aggiungendo più complessità e più byte al decompressore. Di nuovo, ho rappresentato questa sequenza molto specifica tramite un programma e non generalizza, è una compressione specifica per i dati. Inoltre, l'aggiunta di generalità rende il decompressore più grande.

Un'altra preoccupazione è che uno deve avere l'interprete Haskell per eseguire questo. Quando ho compilato il programma lo ha reso molto più grande. Non so davvero perché. C'è lo stesso problema con Python, quindi forse l'approccio migliore è dare gli intervalli, in modo che un programma possa decomprimere il file.