PForDelta
PForDelta es un método de compresión para series de números enteros derivado de PFor (Patched Frame of reference), pero que adicionalmente utiliza codificación delta.
Características y casos de uso
- Es un método de compresión sin pérdida.
- Tiene múltiples implementaciones y variantes.
- Es muy efectivo para compactar arreglos ordenados.
- Es muy rápido para comprimir y descomprimir.
- Se puede usar vectorización para mejorar el rendimiento.
Funcionamiento
Codificación Delta
Es una transformación que consiste en representar cada número de un arreglo como la diferencia entre él mismo y el valor anterior.
Resulta más efectiva para secuencias de poca variación local, en particular, para las secuencias ordenadas, ya que estas suelen tener valores adyacentes similares, y además, nos evitamos los valores negativos que puedes ser más complicados de comprimir.
Ejemplos:
| original | 100 | 204 | 320 | 400 | 500 | 734 | 768 |
|---|---|---|---|---|---|---|---|
| transformado | 100 | 104 | 116 | 80 | 100 | 234 | 34 |
| original | 4 | 14 | 5 | 17 | 20 | 2 | 10 | 9 | 1 | 6 |
|---|---|---|---|---|---|---|---|---|---|---|
| transformado | 4 | 10 | -9 | 12 | 3 | -18 | 8 | 1 | -8 | 5 |
| original | 0 | 0 | 2 | 3 | 7 | 7 | 9 | 9 | 9 | 10 | 10 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| transformado | 0 | 0 | 2 | 1 | 4 | 0 | 2 | 0 | 0 | 1 | 0 | 2 |
Frame of reference (For)*
Es un método de compresión para secuencias de números, consiste en separar la secuencia en bloques de tamaño fijo y hacer bit packing en cada uno. Distintos bloques se van a poder compactar más o menos dependiendo de su valor más grande, por lo que es necesario almacenar el tamaño en bits de los números dentro de cada bloque (información que también podemos compactar).
* Existen dos definiciones de Frame of reference, aquí se describe el método de compresión, pero también se define como una transformación que consiste en representar valores por su diferencia con un valor de referencia.
Ejemplo:
Compactemos el siguiente arreglo con bloques de tamaño 4
| posición | valor | mínimo de bits | bits usados dentro del bloque: |
|---|---|---|---|
| 0 | 14 | 4 | 4 |
| 1 | 8 | 4 | 4 |
| 2 | 2 | 2 | 4 |
| 3 | 15 | 4 | 4 |
| 4 | 20 | 5 | 12 |
| 5 | 2573 | 12 | 12 |
| 6 | 30 | 5 | 12 |
| 7 | 32 | 6 | 12 |
| 8 | 64293943 | 26 | 26 |
| 9 | 3 | 2 | 26 |
| 10 | 5 | 3 | 26 |
| 11 | 7 | 3 | 26 |
Como resultado tendremos 3 bloques que almacenaran sus valores en espacios de 4, 12 y 26 bits cada uno respectivamente, no está mal, pero si nos fijamos, tan sólo 2 valores requieren más de 6 bits. Para mejorar esto se introduce PFor.
Patched Frame of reference (PFor)
Para ciertos casos es más conveniente tratar ciertos valores como excepciones y almacenarlos de forma especial, para esto requerimos metadata adicional y poder distinguir los valores que conviene tratar como excepciones.
Información que necesitamos guardar por cada bloque:
- Bloque comprimido
- Tamaño en bits de los números
- Cantidad de excepciones
Si la cantidad de excepciones es mayor a cero:
- Bits faltantes de las excepciones
- Tamaño en bits de las excepciones (opcionalmente las podemos asignarle a todas un valor fijo)
- Las posiciones de las excepciones dentro del bloque
Para escoger las excepciones podemos calcular el espacio usado por cada caso. Usando como ejemplo el arreglo anterior, si todo perteneciera al mismo bloque tendríamos los siguientes casos (consideraremos que cada valor en la metadata usa 8 bits, sin embargo esto depende de la implementación):
-
bits=26. Sin excepciones
valores + Num. bits + Num. exep
12*26 + 8 + 8 = 328 -
bits=12. Excepciones={64293943}
valores + Num. bits + Num. exep + Num. bits exep + pos. exep + bits faltantes
12*12 + 8 + 8 + 8 + 1*8 + (26-12) = 182 -
bits=6. Excepciones={64293943, 2573}
valores + Num. bits + Num. exep + Num. bits exep + pos. exep + bits faltantes
12*6 + 8 + 8 + 8 + 2*8 + (26-6)*2 = 152 -
bits=5. Excepciones={64293943, 2573, 32}
valores + Num. bits + Num. exep + Num. bits exep + pos. exep + bits faltantes
12*5 + 8 + 8 + 8 + 3*8 + (26-5)*3 = 171 -
bits=4. Excepciones={64293943, 2573, 32, 30, 20}
valores + Num. bits + Num. exep + Num. bits exep + pos. exep + bits faltantes
12*4 + 8 + 8 + 8 + 5*8 + (26-4)*5 = 222 -
bits=3. Excepciones={64293943, 2573, 32, 30, 20, 15, 14, 8}
valores + Num. bits + Num. exep + Num. bits exep + pos. exep + bits faltantes
12*3 + 8 + 8 + 8 + 8*8 + (26-3)*8 = 308 -
bits=2. Excepciones={64293943, 2573, 32, 30, 20, 15, 14, 8, 7, 5}
valores + Num. bits + Num. exep + Num. bits exep + pos. exep + bits faltantes
12*2 + 8 + 8 + 8 + 10*8 + (26-2)*10 = 368 -
bits=0. Excepciones={64293943, 2573, 32, 30, 20, 15, 14, 8, 7, 5, 3, 2}
Num. bits + Num. exep + Num. bits exep + pos. exep + bits faltantes
8 + 8 + 8 + 14*8 + (26-0)*14 = 432
Como podemos ver, el caso 3 es el que menos espacio ocupa, por lo que es el que nos conviene usar.
Resultado:
| valores | binario | pos. excep | bits faltantes |
|---|---|---|---|
| 14 | 001110 | - | - |
| 8 | 001000 | - | - |
| 2 | 000010 | - | - |
| 15 | 001111 | - | - |
| 20 | 010100 | - | - |
| 2573 | 001101 | 5 | 00000000000000101000 |
| 30 | 011110 | - | - |
| 32 | 100000 | - | - |
| 64293943 | 110111 | 8 | 11110101010000110000 |
| 3 | 000011 | - | - |
| 5 | 000101 | - | - |
| 7 | 000111 | - | - |
metadata
| Num. bloque | Num. bits | Num. excep | Num. bits excep |
|---|---|---|---|
| 0 | 6 | 2 | 20 |
Ejemplo:
Comprimiendo el siguiente arreglo con bloques de tamaño 8:
{ 0, 0, 2, 3, 4, 5, 8, 9, 9, 9,10,10,12,14,15,16, 17,18,19,20,21,22,87,88, 90,90,91,93,94,95,96,98}
Nos quedan 4 bloques:
| Num. bloque | Num. bits | Num. excep | Num. bits excep | pos. excep |
|---|---|---|---|---|
| 0 | 2 | 0 | - | - |
| 1 | 2 | 0 | - | - |
| 2 | 1 | 1 | 6 | 6 |
| 3 | 2 | 0 | - | - |
y se reduce a un tamaño de 142 bits, en lugar de los 128 bytes que ocupaba originalmente.