Algoritmo de compresión para datos IEEE-754

Question

¿Alguien tiene una recomendación sobre un buen algoritmo de compresión que funciona bien con valores de punto flotante de doble precisión? Hemos encontrado que la representación binaria de valores de punto flotante da como resultado tasas de compresión muy bajas con programas de compresión comunes (por ejemplo, Zip, RAR, 7-Zip, etc.).

Los datos que necesitamos comprimir son una matriz unidimensional de valores de 8 bytes ordenados en orden creciente monótonamente. Los valores representan las temperaturas en Kelvin con un intervalo típicamente inferior a 100 grados. El número de valores varía desde unos pocos cientos hasta un máximo de 64K.

Aclaraciones

• Todos los valores de la matriz son distintos, aunque la repetición existe a nivel de byte, debido a la forma en que los valores de punto flotante se representan.

• Se desea un algoritmo sin pérdidas debido a que se trata de datos científicos. La conversión a una representación de punto fijo con suficiente precisión (~ 5 decimales) podría ser aceptable siempre que haya una mejora significativa en la eficiencia del almacenamiento.

actualización

encontrado un interesante artículo sobre este tema. No estoy seguro de qué tan aplicable es el enfoque para mis requisitos.

http://users.ices.utexas.edu/~burtscher/papers/dcc06.pdf

Answer 1

¿Puede usted hacer un delta entre los valores adyacentes?
¿Existe un límite de cuánto puede cambiar un valor entre mediciones? ¿Es aceptable limitar este cambio a algún valor de velocidad máxima (a cambio de introducir un suavizado?)

Obviamente hay un límite para la precisión real de los valores del sensor térmico, ¿necesita almacenar 64 bits de precisión? o ¿es mejor almacenar un número entero de unidades de 0.01-Kelvin?

Si puede vivir con un poco más de error y el aumento es relativamente suave, es mejor que ajuste una función a los datos y almacene solo unos pocos términos de la función.

EDIT:
Eche un vistazo a un conjunto de datos típico y observe el rango de diferencias entre valores adyacentes. Luego mira qué precisión necesitas para representar esto.

por ejemplo. Si tiene una diferencia máxima de 1 dígito entre lecturas, puede almacenar cambios de 1/256 de esto en un byte. Si necesita almacenar un rango mayor o más precisión, use un corto dividido por algún factor.
Así que la próxima lectura sería ULTIMA_LECTURA = + (float) de incremento/256,0

Answer 2

Se podría pensar en volver a la codificación de los datos mediante un codificador de entropía (Huffman, Shannon-Fano, codificación aritmética). Pero esto solo proporcionará buenos resultados si tiene muchas repeticiones de los puntos de datos y si sabe qué símbolos aparecerán con qué probabilidad.

Answer 3

Los algoritmos de compresión se basan en repeticiones y regularidades, y los números en coma flotante no funcionan bien en eso.

La primera pregunta es si puede usar valores de coma flotante de precisión simple, lo que le dará una compresión del 50% inmediatamente. Pocos termómetros tienen una precisión de siete dígitos, y el exponente representará temperaturas considerablemente inferiores a cualquier cosa que me digan que realmente se puede obtener.

Si no, ¿puede filtrar sus temperaturas, redondeándolas al equivalente de N dígitos (más probablemente N/.301 bits)? Eso puede introducir suficientes regularidades para ser útil.

Si realmente tiene que almacenar 64 bits de información para cada lectura de temperatura, y todos los bits son significativos y no predecibles de los otros bits, entonces efectivamente no puede comprimirlo.

Answer 4

Lo primero a tener en cuenta: intente comprimir los datos antes de lo convierte en doble precisión. Reje su comentario a David Thornley, a menos que sus ADC de imágenes IR tengan 24 bits significativos, los flotadores de 32 bits deberían tener una precisión más que suficiente; solo es su requisito preservar exactamente el ruido generado por el procesamiento posterior que es un problema. De lo contrario, podría ser práctico realizar una ingeniería inversa de su procesamiento, determinando una tabla de valores que genera y, en su lugar, almacenando un índice en esta tabla.

Segundo: si su algoritmo de compresión sabe que sus datos están en trozos de 8 bytes, será mucho más efectivo; esto es porque no arrojará sus bytes más significativos con los bytes menos significativos. Como un método de preprocesamiento crudo, podrías intentar prefijar cada doble con un byte distintivo (¿coma ASCII, quizás?) Antes de pasarlo a través de un compresor basado en bytes como gzip; esto debería dar como resultado una mejor compresión total a pesar de que la corriente intermedia es un 12% más grande. Menos crudo pero más esfuerzo sería escribir su propia compresión adaptada a esta tarea, quizás usando un árbol de 8 niveles para representar los valores esperados de cada byte en su doble.

Tercero: como los datos de imagen son altamente redundantes, alguna forma de codificación delta u otra compresión relacionada con la imagen debería ahorrar algo de espacio. Sin embargo, no obtendrá una cantidad terriblemente grande si exige una compresión sin pérdida, ya que el ruido de la imagen es inherentemente incompresible. Además, no te ayudará a lidiar con el hash pseudoaleatorio en los bits menos significativos de tus dobles, como se explicó anteriormente.

Answer 5

Todos los codificadores que enumera están orientados a bytes, y son expulsados ​​por algunas propiedades de dobles. Para uno, existe el diseño en el que el exponente/signo de 12 bits no funciona bien con los límites de los bytes, para otros está el ruido de su entrada. La primera parte es fácil de tratar de muchas maneras, la segunda limitará la efectividad de cualquier compresión sin pérdidas que le apliques. Creo que incluso el mejor resultado será menos que sorprendente, no conozco sus datos, pero sospecho que puede contar con un ahorro del 25%, más o menos.

Desde lo alto de la cabeza, y tal vez inútil, ya que han pensado en todo en esta lista ...

1. Tratar la corriente como enteros de 64 bits y valores adyacentes delta-codificar. Si tiene corridas de valores con el mismo exponente, efectivamente lo pondrá a cero, así como posiblemente algunos bits de mantisa alta. Habrá desbordamientos, pero los datos aún necesitan solo 64 bits y la operación puede respetarse.

2. En esta etapa, opcionalmente puede probar algunas predicciones crudas de enteros y guardar las diferencias.

3. Si ha seguido la sugerencia antes, tendrá casi la mitad de los valores comenzando con 000 ... y casi la mitad con FFF ...Para eliminar eso, gire el valor a la izquierda (ROL) en 1 bit y XOR con todos los Fs si el LSB actual es 1. Reverse es XOR con Fs si LSB es 0 y luego ROR.

En el segundo pensamiento simplemente XORing predicciones a los verdaderos valores puede ser mejor que la diferencia, ya que no tiene que hacer el paso 3 a continuación.

4. Puede intentar reordenar bytes a grupos de bytes con la misma importancia juntos. Como, primero todos los bytes más significativos, y así sucesivamente. Por lo menos, deberías obtener algo así como una racha masiva de ceros con al menos algunos bits de ruido primero.

5. Run través de un compresor genérico o incluso primera RLE en la carrera de ceros, a continuación, un codificador de entropía, como Huffman, o mejor, el codificador intervalo de 7zip/LZMA.

Hay algo bueno acerca de sus datos, es monótono. Hay algo malo acerca de sus datos: simplemente es un conjunto demasiado pequeño. ¿Cuánto quieres ahorrar, solo kilobyes? ¿Para qué? La efectividad de la compresión sufrirá mucho si a menudo existe una diferencia de exponente entre valores adyacentes.

Si está procesando una gran cantidad de esos conjuntos de datos, debe considerar usar su similitud para comprimirlos juntos mejor, tal vez intercalarlos en algún momento. Si puede vivir con alguna pérdida, puede ser una buena idea poner a cero algunos bytes menos significativos, tal vez tanto en los datos de origen como en la predicción para que no reintroduzca el ruido allí.

Answer 6

Si desea almacenamiento de archivos de alta compresión, "Rendimiento de compresión alta de doble precisión de punto flotante-Data" por Burtscher & Patanaworabhan o "FFI compresión ciente rápida y E del punto flotante de datos" por Lindstrom & Isenberg puede ser útil tú.

Si desea un acceso dinámico más rápido a expensas de una tasa de compresión más baja, entonces una wavelet de elevación 1D puede ser adecuada. Puede cuantizar los datos en enteros más pequeños especificando la cantidad de dígitos que se deben conservar. A continuación, utilice la codificación delta con un modelo predictivo seguido de transformación con Haar o una transformada wavelet más costosa y la codificación aritmética de los coeficientes mayores que un valor especificado.

creo que sirve

Puede obtener algoritmo de ZFP de Lindstrom aquí: https://github.com/LLNL/zfp