indexing - que - Comprimir enteros ordenados
programas para comprimir archivos (9)
Estoy construyendo un índice que es solo 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.
¿Los números enteros están agrupados de una manera densa o escasa?
Por denso me refiero a:
[1, 2, 3, 4, 42, 43, 78, 79, 80, 81]
Por escaso me refiero a:
[1, 4, 7, 9, 19, 42, 53, 55, 78, 80]
Si los números enteros se agrupan de manera densa, podrías comprimir el primer vector para 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 ocuparían un 100% más de espacio que los datos originales.
Me imagino que la codificación Huffman sería bastante apropiada para este propósito (y relativamente rápida 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 no está ordenada 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 muy bueno .)
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.) puede hacer una cosa:
Encuentra las diferencias entre los números adyacentes que serían como 2,1,1,4,1 ... etc. (en nuestro ejemplo) y luego Huffman codifica estos 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 obtenga una relación de compresión muy buena 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.
Tal vez podría almacenar las diferencias entre enteros consecutivos de 32 bits como enteros de 16 bits.
Utilizaría algo estándar de pantano antes de invertir en tu propio plan.
En Java, por ejemplo, puede usar GZIPOutputStream para aplicar compresión gzip.
Como ha 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 aprovechas 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.
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 decodifica la mitad del archivo antes de poder encontrar el número que buscaba. 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.
La respuesta de MSalters es interesante, pero puede distraerte si no analizas adecuadamente. Solo hay 47 números de Fibonacci que caben en 32 bits.
Pero él es muy acertado en la forma de resolver el problema de manera adecuada mediante el análisis de la serie de incrementos para encontrar patrones que 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.
Las condiciones en las listas de enteros son ligeramente diferentes, pero la pregunta Compresión para un flujo único de datos sugiere varios enfoques que podrían ayudarlo.
Sugeriría prefiltrar los datos en un start y una serie de s offset . 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.