Compresión en Scala

Question

Estoy trabajando en Scala con listas muy larg de Int (tal vez grande ) y necesito para comprimirlos y para mantenerlo en su memoria.

El único requisito es que puedo tirar (y descomprimir) el primer número de la lista de trabajo con, whithout tocar el resto de la lista.

Tengo muchas ideas buenas, pero la mayoría de ellos se traducen los números de bits. Ejemplo:

Puede escribir cualquier número de x como la tupla | log (x) |, x- | log (x) | el primer elemento que la derecha como una cadena de 1 y un 0 al final (Código Unario) y el segundo en binario. por ejemplo:

  

1 -> 0,1 -> 0 1

     

...

     

5 -> 2,1 -> 110 01

     

...

     

8 -> 3,0 -> 1110 000

     

9 -> 3,1 -> 1110 001

     

...

Mientras que un Int toma fija 32 bits de memoria y una larga 64, con esta compresión x requiere 2log (x) bits para el almacenamiento y pueden crecer indefinetly. Esta compresión hace reducememory en la mayoría de los casos.

¿Cómo manejaría este tipo de datos? ¿Hay algo como BitArray o algo?

Cualquier otra manera de comprimir estos datos en Scala?

Gracias

Answer 1

En función de la poca densidad y alcance de su conjunto de datos, que puede mantener sus datos como una lista de los deltas en lugar de números. Que se utiliza para la compresión de sonido, por ejemplo, y puede ser tanto con o sin pérdidas, dependiendo de sus necesidades.

Por ejemplo, si tiene un número Int pero sabe que casi nunca ser más que una (firmado) Byte aparte, se podría hacer algo como esto lista de bytes:

-1           // Use -1 to imply the next number cannot be computed as a byte delta
0, 0, 4, 0   // 1024 encoded as bytes
1            // 1025 as a delta
-5           // 1020 as a delta
-1           // Next number can't be computed as a byte delta
0, 0, -1, -1 // 65535 encoded as bytes -- -1 doesn't have special meaning here
10           // 65545 as a delta

Por lo que no tiene que manejar bits utilizando esta codificación particular. Pero, en realidad, usted no obtener buenas respuestas sin una indicación muy clara del problema en particular, las características de los datos, etc.

Al releer su pregunta, parece que no es descarte técnicas de compresión de datos que se convierten en bits. Si no es así, entonces le sugiero Huffman - predictivo si es necesario - o algo de la familia de Lempel-Ziv

.

Y, no, Scala tiene ninguna biblioteca para manejar los datos binarios, por desgracia. Aunque paulp probablemente tiene algo así como que en el propio compilador.