Algoritmos de compresión solo para números

Question

Voy a comprimir los datos de ubicación (latitud, longitud, fecha, hora). Todos los números están en formato fijo. 2 de ellos (latitud, longitud) están en formato decimal. Otros 2 son enteros.

Ahora estos números están en cadena de formato fijo.

¿Cuáles son los algoritmos para comprimir números en formato fijo? ¿El número es solo compresiones (si hay alguna) mejor que la compresión de cadenas? ¿Debo comprimir una cadena directamente sin convertirla en números y luego comprimirla?

Gracias de antemano.

Answer 1

Este es uno de estos lugares donde una pequeña teoría es útil. Debe pensar en varias cosas:

• cuál es la resolución de sus medidas: 0.1 ° o 0.001 °? 1 segundo o un microsegundo?
• son las mediciones asociadas y en algún orden, o arrojadas al azar?

Digamos, por ejemplo, que la resolución es de 0.01 °. Ellos saben que sus valores van desde -180 ° a + 180 °, o 35900 valores diferentes. Lg (35900) ≈ 16 por lo que necesita 16 bits; 14 bits para -90 ° - + 90 °. Claramente, si está almacenando este tipo de valor como coma flotante, puede comprimir los datos a la mitad inmediatamente.

De forma similar con el tiempo de fecha, ¿cuál es el rango; ¿Cuántos bits debes tener?

Ahora, si los datos están en algún orden (como, muestras tomadas de forma secuencial a bordo de un solo barco), entonces todo lo que necesita es un valor inicial y un delta; eso puede hacer una gran diferencia . Con un barco viajando a 30 nudos, la posición no puede cambiar más de 0.03 grados por hora o aproximadamente 0.0000083 grados por segundo. Esos deltas van a ser valores muy pequeños, por lo que puede almacenarlos en muy pocos bits.

El punto es que hay una serie de cosas que puede hacer, pero debe saber más sobre los datos que nosotros para hacer una recomendación.

---

Actualización: Oh, espera, punto fijo cadenas?!

Bien, esto es (relativamente) fácil. Para empezar, sí, quiere convertir sus cadenas en una representación binaria. Sólo que componen un elemento de datos, es posible que tenga

040.00105.0020090518212100Z 

que se podría convertir en

 
| 4000   | short int, 16 bits | 
| 10500   | short int, 16 bits | 
| 20090518212100Z | 64 bits   | 

Así que es 96 bits, 12 bytes contra 26 bytes.

Answer 2

La compresión normalmente funciona en un flujo de bytes. Cuando una transmisión tiene una distribución no uniforme de valores de bytes (por ejemplo, texto o números almacenados como texto), la relación de compresión que puede alcanzar será mayor, ya que se utilizan menos bits para almacenar los bytes que aparecen con mayor frecuencia (en Huffman compresión).

Normalmente, los datos de los que está hablando se almacenarán simplemente como números binarios (no como texto), y eso generalmente es eficiente en espacio y recuperación.

te recomiendo echar un vistazo a The Data Compression Book

Answer 3

Qué tipo de datos que está comprimiendo? ¿Cómo se distribuye? ¿Está ordenado de alguna manera? Todas estas cosas pueden afectar lo bien que se comprime, y quizás te permitan convertir los datos en algo más fácil de comprimir, o simplemente más pequeños a la salida.

La compresión de datos funciona mal en datos "aleatorios". Si sus datos están dentro de un rango más pequeño, es posible que pueda aprovechar eso.

En verdad, simplemente debe intentar ejecutar cualquiera de los algoritmos comunes y ver si los datos son "suficientemente comprimidos". De lo contrario, y usted sabe más acerca de los datos que los algoritmos de compresión puede "intuir", debe aprovechar esa información.

Un ejemplo es decir que sus datos no son solo de Lat y Long, sino que se supone que están "cerca" entre sí. Entonces probablemente puedas almacenar un lat de "origen" y largo, y el resto puede ser diferencial. Quizás estas diferencias son lo suficientemente pequeñas como para caber en un solo byte firmado.

Eso es solo un ejemplo simple de cosas que puede hacer con el conocimiento de los datos frente a lo que algunos algoritmos genéricos pueden no ser capaces de descifrar.

Answer 4

Depende de lo que va a hacer con los datos y de la precisión que necesita.

Lat/long se da tradicionalmente en grados, minutos y segundos, con 60 segundos al minuto, 60 minutos al grado y 1 grado de latitud nominalmente igual a 60 millas náuticas (nmi). 1 minuto es 1 nmi, y 1 segundo es poco más de 100 ft.

Latitude va de -90 a +90 grados. La representación de latitud como segundos enteros le da un rango de -324000 .. + 324000, o aproximadamente 20 bits. La longitud va de -180 a +180, por lo que representar la longitud de la misma manera requiere 1 bit más.

Para que pueda representar una posición lat/long completa, a +/- 50 pies, en 41 bits.

Obviamente, si no necesita mucha precisión, puede reducir la cantidad de bits.

Observe que un flotador tradicional de 32 bits de precisión simple usa alrededor de 24 bits de mantisa, por lo que tiene hasta +/- 6 pies si solo convierte su latitud/longitud en segundos para flotar. Es difícil vencer a dos flotadores de precisión simple para este tipo de cosas.