Comprimir enteros ordenados

Question

Estoy construyendo un índice que es simplemente varios conjuntos de enteros de 32 bits ordenados almacenados continuamente en un archivo binario. El problema es que este archivo crece bastante grande. He estado pensando en agregar algunos esquemas de compresiones, pero eso está un poco fuera de mi experiencia. Entonces, me pregunto, ¿qué algoritmo de compresión funcionaría mejor en este caso? Además, la descompresión tiene que ser rápida ya que este índice se usará para realizar búsquedas.

Answer 1

Si está almacenando enteros que están muy juntos (por ejemplo: 1, 3, 4, 5, 9, 10 etc.) en lugar de algunos enteros aleatorios de 32 bits (982346 ..., 3487623412 .., etc.) se puede hacer una cosa:

Encuentra las diferencias entre los números adyacentes que sería como 2,1,1,4,1 ... etc (en nuestro ejemplo) y luego Huffman codificar esta números.

No creo que la codificación Huffman funcione si las aplicas directamente a la lista original de números que tienes.

Pero si tiene una lista ordenada de números cercanos, las probabilidades son buenas de que obtendrá una muy buena relación de compresión al hacer la codificación Huffman de las diferencias numéricas, puede ser una proporción mejor que usar el algoritmo LZW utilizado en las bibliotecas Zip.

De todos modos, gracias por publicar esta interesante pregunta.

Answer 2

Me imagino que Huffman coding sería bastante apropiado para este propósito (y relativamente rápido en comparación con otros algoritmos con relaciones de compresión similares).

EDITAR: Mi respuesta fue solo un puntero general. La sugerencia de Niyaz de codificar las diferencias entre números consecutivos es buena. (Sin embargo, si la lista es no ordenó o el espaciado de números es muy irregular, creo que no sería menos efectivo usar la codificación simple de Huffman. De hecho, LZW o similar probablemente sería mejor en este caso, aunque posiblemente no sea así. muy bueno.)

Answer 3

¿Están los números enteros agrupados de una manera densa o escasa?

Por densa que me refiero:

[1, 2, 3, 4, 42, 43, 78, 79, 80, 81]

Por escasa que me refiero:

[1, 4, 7, 9, 19, 42, 53, 55, 78, 80]

Si los números enteros se agrupan de una manera densa que podría comprimir el primer vector en mantener tres rangos:

[(1, 4), (42, 43), (78, 81)]

Que es una compresión del 40%. Por supuesto, este algoritmo no funciona bien en datos dispersos, ya que los datos comprimidos tomarían un espacio 100% mayor que los datos originales.

Answer 4

Usaría algo pantano estándar de la plataforma antes de invertir en su propio esquema.

En Java, por ejemplo, puede usar GZIPOutputStream para aplicar compresión gzip.

Answer 5

Las condiciones en las listas de enteros son ligeramente diferentes, pero la pregunta Compression for a unique stream of data sugiere varios enfoques que podrían ayudarlo.

Sugeriría prefiltrar los datos en un start y una serie de offset s. Si sabe que las compensaciones serán relativamente pequeñas, podría incluso codificarlas como cantidades de 1 o 2 bytes en lugar de 4 bytes. Si no lo sabe, cada desplazamiento puede ser de 4 bytes, pero dado que serán pequeños diffs, obtendrá muchas más repeticiones de las que almacenaría en los enteros originales.

Después del prefiltrado, ejecute su salida a través del esquema de compresión de su elección; algo que funcione en un nivel de bytes, como gzip o zlib, probablemente sea un buen trabajo.

Answer 6

Quizás podría almacenar las diferencias entre enteros consecutivos de 32 bits como enteros de 16 bits.

Answer 7

Como has descubierto, una secuencia ordenada de enteros de N 32 bits no tiene 32 * N bits de datos. Esto no es sorpresa. Suponiendo que no hay duplicados, ¡para cada secuencia ordenada hay N! Secuencias no clasificadas que contienen los mismos números enteros.

Ahora, ¿cómo se aprovecha la información limitada en la secuencia ordenada? Muchos algoritmos de compresión basan su compresión en el uso de cadenas de bits más cortas para valores de entrada comunes (Huffman usa solo este truco). Varios carteles ya han sugerido calcular las diferencias entre los números y comprimir esas diferencias. Suponen que será una serie de números pequeños, muchos de los cuales serán idénticos. En ese caso, la mayoría de los algoritmos comprimirán bien la secuencia de diferencia.

Sin embargo, tome la secuencia de Fibonacci. Eso definitivamente es enteros enteros. La diferencia entre F (n) y F (n + 1) es F (n-1). Por lo tanto, comprimir la secuencia de diferencias equivale a comprimir la secuencia en sí, ¡no ayuda en absoluto!

Entonces, lo que realmente necesitamos es un modelo estadístico de sus datos de entrada. Dada la secuencia N [0] ... N [x], ¿cuál es la distribución de probabilidad de N [x + 1]? Sabemos que P (N [x + 1] < N [x]) = 0, ya que la secuencia está ordenada. Las soluciones diferenciales/basadas en Huffman presentadas funcionan porque suponen que P (N [x + 1] - N [x] = d) es bastante alta para d positiva pequeña e independiente de x, por lo que pueden usar algunos bits para el pequeñas diferencias. Si puede dar otro modelo, puede optimizarlo para eso.

Answer 8

Si necesita una búsqueda rápida de acceso aleatorio, una codificación Huffman de las diferencias (como lo sugiere Niyaz) es solo la mitad de la historia. Probablemente también necesite algún tipo de esquema de paginación/indexación para que sea fácil extraer el enésimo número.

Si no hace esto, entonces extraer el enésimo número es una operación O (n), ya que tiene que leer y Huffman descodifica la mitad del archivo antes de poder encontrar el número que estaba buscando. Debe elegir el tamaño de página cuidadosamente para equilibrar la sobrecarga de almacenar desplazamientos de página con la velocidad de búsqueda.

Answer 9

La respuesta de MSalters es interesante, pero podría distraerte si no se analiza correctamente. Solo hay 47 números de Fibonacci que caben en 32 bits.

Pero él no ve la manera correcta de resolver el problema mediante el análisis de la serie de incrementos para encontrar patrones para comprimir.

Cosas que importan: a) ¿Hay valores repetidos? Si es así, ¿con qué frecuencia? (si es importante, hágalo parte de la compresión, si no lo hace una excepción). b) ¿Parece casi aleatorio?Esto también puede ser bueno ya que es probable encontrar un incremento promedio adecuado.