algorithm - data - Mejor algoritmo de compresión para una secuencia de enteros
lossless compression (15)
Tengo una gran matriz con un rango de enteros que son en su mayoría continuos, por ejemplo, 1-100, 110-160, etc. Todos los enteros son positivos. ¿Cuál sería el mejor algoritmo para comprimir esto?
Probé el algoritmo de desinflado, pero eso me da solo un 50% de compresión. Tenga en cuenta que el algoritmo no puede ser con pérdida.
Todos los números son únicos y progresivamente crecientes.
Además, si me puedes indicar la implementación java de dicho algoritmo, sería genial.
Combinaría las respuestas dadas por CesarB y Fernando Miguélez.
Primero, almacene las diferencias entre cada valor y el anterior. Como señaló CesarB, esto te dará una secuencia de la mayoría.
Luego, use un algoritmo de compresión de Codificación de Longitud de Ejecución en esta secuencia. Se comprimirá muy bien debido a la gran cantidad de valores repetidos.
Bueno, estoy votando por una forma más inteligente. Todo lo que tiene que almacenar es [int: número de inicio] [int / byte / whatever: número de iteraciones] en este caso, convertirá su matriz de ejemplo en el valor 4xInt. Después de eso puedes comprimir como quieras :)
Comprima la cadena "1-100, 110-160" o almacene la cadena en alguna representación binaria y analícela para restaurar la matriz
Primero, preprocese su lista de valores tomando la diferencia entre cada valor y el anterior (para el primer valor, suponga que el anterior era cero). En su caso, esto debería dar principalmente una secuencia de unos, que la mayoría de los algoritmos de compresión pueden comprimir mucho más fácilmente.
Así es como hace el formato PNG para mejorar su compresión (hace uno de varios métodos de diferencia seguidos por el mismo algoritmo de compresión utilizado por gzip).
Si tiene series de valores repetidos, RLE es el más fácil de implementar y podría darle un buen resultado. No obstante, otros algoritmos más avanzados que tienen en cuenta la entropía como LZW, que ahora no tiene patente, generalmente pueden lograr una compresión mucho mejor.
Puede echar un vistazo a estos y otros algoritmos sin pérdida aquí .
Sugiero echarle un vistazo a Huffman Coding , un caso especial de codificación aritmética . En ambos casos, analiza la secuencia de inicio para determinar las frecuencias relativas de diferentes valores. Los valores que ocurren con mayor frecuencia se codifican con menos bits que los que ocurren menos frecuentemente.
¿De qué tamaño son los números? Además de las otras respuestas, podría considerar la codificación de longitud de variante base-128, que le permite almacenar números más pequeños en bytes individuales al mismo tiempo que permite números más grandes. El MSB significa "hay otro byte", esto se describe aquí.
Combine esto con las otras técnicas para que esté almacenando "tamaño de omisión", "tamaño de toma", "tamaño de omisión", "tamaño de toma", pero señalando que ni "saltar" ni "tomar" nunca serán cero, así que lo haremos resta uno de cada uno (lo que te permite guardar un byte extra para un puñado de valores)
Asi que:
1-100, 110-160
es "skip 1" (supongamos que comienza en cero ya que facilita las cosas), "take 100", "skip 9", "take 51"; resta 1 de cada uno, dando (como decimales)
0,99,8,50
que codifica como (hex):
00 63 08 32
Si quisiéramos omitir / tomar un número mayor - 300, por ejemplo; restamos 1 dando 299, pero eso supera los 7 bits; empezando por el final pequeño, codificamos bloques de 7 bits y un MSB para indicar la continuación:
299 = 100101100 = (in blocks of 7): 0000010 0101100
así que comenzando con el pequeño final:
1 0101100 (leading one since continuation)
0 0000010 (leading zero as no more)
dando:
AC 02
Así que podemos codificar números grandes fácilmente, pero los números pequeños (que suenan típicos para omitir / tomar) ocupan menos espacio.
Podría intentar ejecutar esto a través de "desinflar", pero podría no ser de mucha ayuda ...
Si no quiere lidiar con todo ese engorroso código de codificación usted mismo ... si puede crear el conjunto entero de los valores (0,99,8,60), podría usar los búferes de protocolo con un uint32 repetido empaquetado / uint64 - y hará todo el trabajo por usted ;-p
No "hago" Java, pero aquí hay una implementación completa de C # (tomando prestados algunos de los bits de codificación de mi proyecto protobuf-net ):
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
static class Program
{
static void Main()
{
var data = new List<int>();
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<int>();
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;
}
}
Además de las otras soluciones:
Puede encontrar áreas "densas" y usar un mapa de bits para almacenarlas.
Así por ejemplo:
Si tiene 1000 números en 400 rangos entre 1000-3000, podría usar un solo bit para denotar la existencia de un número y dos ints para denotar el rango. El almacenamiento total para este rango es de 2000 bits + 2 ints, por lo que puedes almacenar esa información en 254bytes, lo cual es bastante sorprendente ya que incluso los enteros cortos ocuparán dos bytes cada uno, por lo que para este ejemplo obtienes un ahorro de 7X.
Cuanto más densas sean las áreas, mejor funcionará este algoritmo, pero en algún momento solo será más barato almacenar y comenzar.
La idea básica que probablemente deba usar es, para cada rango de enteros consecutivos (llamaré a estos rangos), almacenar el número inicial y el tamaño del rango. Por ejemplo, si tiene una lista de 1000 enteros, pero solo hay 10 rangos separados, puede almacenar solo 20 enteros (1 número de inicio y 1 tamaño para cada rango) para representar estos datos, lo que sería una tasa de compresión de 98 % Afortunadamente, hay algunas optimizaciones más que puede hacer que ayudarán con los casos donde el número de rangos es más grande.
Almacene el desplazamiento del número inicial relativo al número inicial anterior, en lugar del número inicial. La ventaja aquí es que los números que almacena generalmente requerirán menos bits (esto puede ser útil en posteriores sugerencias de optimización). Además, si solo almacenó los números iniciales, estos números serían únicos, mientras que almacenar el desplazamiento da la posibilidad de que los números estén cerca o incluso repiten lo que puede permitir una compresión aún mayor con otro método aplicado después.
Use la cantidad mínima de bits posible para ambos tipos de números enteros. Puede iterar sobre los números para obtener el desplazamiento más grande de un número entero inicial así como también el tamaño del rango más grande. A continuación, puede usar un tipo de datos que almacene de manera más eficiente estos enteros y simplemente especifique el tipo de datos o la cantidad de bits al comienzo de los datos comprimidos. Por ejemplo, si el desplazamiento más grande de un número entero inicial es solo 12,000, y el rango más grande es 9,000, entonces puede usar un entero sin signo de 2 bytes para todos estos. A continuación, puede agrupar el par 2,2 al comienzo de los datos comprimidos para mostrar que se utilizan 2 bytes para ambos enteros. Por supuesto, puede ajustar esta información en un solo byte usando un poco de manipulación. Si te sientes cómodo haciendo mucha manipulación de bits pesados, puedes almacenar cada número como la cantidad mínima posible de bits en lugar de conformar representaciones de 1, 2, 4 u 8 bytes.
Con esas dos optimizaciones, veamos un par de ejemplos (cada uno tiene 4.000 bytes):
- 1,000 enteros, el mayor offset es 500, 10 rangos
- 1,000 enteros, el mayor desplazamiento es de 100, 50 rangos
- 1,000 enteros, el mayor desplazamiento es 50, 100 rangos
SIN OPTIMIZACIONES
- 20 enteros, 4 bytes cada uno = 80 bytes. COMPRESIÓN = 98%
- 100 enteros, 4 bytes cada uno = 400 bytes. COMPRESIÓN = 90%
- 200 enteros, 4 bytes cada uno = 800 bytes. COMPRESIÓN = 80%
CON OPTIMIZACIONES
- Encabezado de 1 byte + 20 números, 1 byte cada uno = 21 bytes. COMPRESIÓN = 99.475%
- Encabezado de 1 byte + 100 números, 1 byte cada uno = 101 bytes. COMPRESIÓN = 97.475%
- Encabezado de 1 byte + 200 números, 1 byte cada uno = 201 bytes. COMPRESIÓN = 94.975%
Si bien podría diseñar un algoritmo personalizado específico para su flujo de datos, probablemente sea más fácil usar un algoritmo de codificación disponible. Ejecuté algunas pruebas de algoritmos de compresión disponibles en Java y encontré las siguientes tasas de compresión para una secuencia de un millón de enteros consecutivos:
None 1.0
Deflate 0.50
Filtered 0.34
BZip2 0.11
Lzma 0.06
Su caso es muy similar a la compresión de índices en los motores de búsqueda. El popular algoritmo de compresión utilizado es el algoritmo PForDelta y el algoritmo Simple16. Puede usar la biblioteca kamikaze para sus necesidades de compresión.
Hemos escrito trabajos de investigación recientes que estudian los mejores esquemas para este problema. Por favor mira:
Daniel Lemire y Leonid Boytsov, descodificando miles de millones de enteros por segundo mediante vectorización, 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 (para aparecer) http://arxiv.org/abs/1401.6399
Incluyen una extensa evaluación experimental.
Puede encontrar una implementación completa de todas las técnicas en C ++ 11 en línea: https://github.com/lemire/FastPFor y https://github.com/lemire/SIMDCompressionAndIntersection
También hay bibliotecas C: https://github.com/lemire/simdcomp y https://github.com/lemire/MaskedVByte
Si prefiere Java, consulte https://github.com/lemire/JavaFastPFOR
Sé que este es un hilo de mensajes antiguos, pero incluyo mi prueba personal PHP de la idea SKIP / TAKE que encontré aquí. Estoy llamando al mío STEP (+) / SPAN (-). Quizás alguien lo encuentre útil.
NOTA: Implementé la capacidad de permitir números enteros duplicados así como números enteros negativos, aunque la pregunta original incluía números enteros positivos no duplicados. Siéntete libre de ajustarlo si quieres intentar afeitar un byte o dos.
CÓDIGO:
// $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 "<hr>/nOriginal Array has "
.count($integers_array)
.'' elements: {not showing, since I modified the original array directly}'';
echo "<br>/nCompressed Array has "
.count($compressed_array).'' elements: ''
.implode('', '',$compressed_array);
echo "<br>/nCompressed String has "
.strlen($compressed_string).'' characters: ''
.$compressed_string;
echo "<br>/nPacked String has "
.strlen($packed_string).'' (some probably not printable) characters: ''
.$packed_string;
echo "<br>/nBase64 String has "
.strlen($base64_string).'' (all printable) characters: ''
.$base64_string;
echo "<br>/nGZipped String has "
.strlen($gz_string).'' (some probably not printable) characters: ''
.$gz_string;
echo "<br>/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 "<hr>Reconstituted Array has "
.count($uncompressed_array).'' elements: ''
.implode('', '',$uncompressed_array).
''<hr>'';
SALIDA:
--------------------------------------------------------------------------------
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
--------------------------------------------------------------------------------
TurboP para: Compresión de entero más rápido
- para C / C ++, incluida Java Critical Natives / JNI Interface
- Compresión entera acelerada SIMD
- Diferencial Scalar + Integrated (SIMD) / codificación / decodificación en zigzag para listas enteras ordenadas / no ordenadas
- Rango completo de 8/16/32/64 bits listas de interger
- Acceso directo
- Aplicación de referencia
No pude conseguir que mi compresión fuera mucho mejor que .11 para esto. Genere mis datos de prueba a través del intérprete de Python y es una lista de enteros delimitados por la nueva línea de 1-100 y 110-160. Uso el programa real como una representación comprimida de los datos. Mi archivo comprimido es el siguiente:
main=mapM_ print [x|x<-[1..160],x`notElem`[101..109]]
Es solo un script de Haskell que genera el archivo que puede ejecutar a través de:
$ runhaskell generator.hs >> data
El tamaño del archivo g.hs es de 54 bytes, y los datos generados por python son 496 bytes. Esto da 0.10887096774193548 como la relación de compresión. Creo que con más tiempo uno podría achicar el programa, o podría comprimir el archivo comprimido (es decir, el archivo haskell).
Otro enfoque podría ser guardar 4 bytes de datos. El mínimo y el máximo de cada secuencia, luego déles a una función generadora. Sin embargo, la carga de archivos agregará más caracteres al descompresor agregando más complejidad y más bytes al descompresor. Una vez más, representé esta secuencia muy específica a través de un programa y no se generaliza, es una compresión que es específica de los datos. Además, agregar generalidad hace que el descompresor sea más grande.
Otra preocupación es que uno debe tener el intérprete de Haskell para ejecutar esto. Cuando compilé el programa, lo hice mucho más grande. Realmente no sé por qué. Existe el mismo problema con python, así que tal vez el mejor enfoque es dar los rangos, de modo que un programa pueda descomprimir el archivo.