vector comprimido/clase de matriz con acceso aleatorio a datos

Question

Me gustaría crear una clase "vector comprimido"/"vector comprimido" (detalles a continuación), que permite el acceso aleatorio a datos con un tiempo más o menos constante.

"tiempo más o menos constante" significa que aunque el tiempo de acceso al elemento no es constante, no debería seguir aumentando cuando me acerque a cierto punto de la matriz. Es decir. el contenedor no debe hacer muchos más cálculos (como "descomprimir todo una vez más para obtener el último elemento", y "hacer casi nada para obtener el último elemento") para obtener un elemento. Probablemente se logre dividiendo la matriz en fragmentos de datos comprimidos. Es decir. el acceso a un elemento debe tomar "averageTime" + - alguna desviación. Podría decir que quiero que el tiempo de acceso al mejor de los casos y el tiempo de acceso al peor de los casos sea relativamente cercano al tiempo promedio de acceso.

¿Cuáles son mis opciones (algoritmos adecuados/contenedores ya disponibles, si hay alguno)?

detalles de contenedores:

1. Container actúa como una matriz lineal de elementos idénticos (como std :: vector)
2. Una vez que se inicializa contenedor, los datos es constante y no cambia nunca. El contenedor necesita proporcionar acceso de solo lectura.
3. El contenedor debe comportarse como array/std :: vector - es decir, los valores accedidos a través del operador [], hay .size(), etc.
4. Sería bueno si pudiera hacerlo como clase de plantilla.
5. El acceso a los datos debe ser más o menos de tiempo constante. No necesito el mismo tiempo de acceso para cada elemento, pero no debería tener que descomprimir todo para obtener el último elemento.

Ejemplo de uso:
Búsqueda binaria en los datos.

Datos de datos:
1. Los datos son estructuras que consisten principalmente en flotadores y algunos ints. Hay más flotadores que ints. Sin cadenas.
2. Es poco probable que haya muchos elementos idénticos en el conjunto, por lo que simplemente no será posible indexar los datos.
3. El tamaño de un elemento es inferior a 100 bytes.
4. El tamaño total de los datos por contenedor es de entre algunos kilobytes y algunos megabytes.
5. Los datos no son escasos: es un bloque continuo de elementos, todos ellos asignados, no hay "espacios vacíos".

El objetivo de la compresión es reducir la cantidad de memoria RAM que toma el bloque cuando se compara con la representación sin comprimir como matriz, manteniendo un rendimiento de acceso de lectura razonable y permitiendo acceder aleatoriamente a los elementos como matriz. Es decir. los datos deben almacenarse en forma comprimida internamente, y debería poder acceder a él (solo lectura) como si fuera un contenedor estándar o similar.

Ideas/Opiniones?

Answer 1

¿Puedo entender que desea una gama cuyos elementos no se almacenan de vainilla, pero comprimido, para minimizar el uso de memoria.

En cuanto a la compresión, no tiene una idea excepcional sobre la estructura de sus datos, por lo que está bien con algún tipo de codificación de entropía. Idealmente, quisiera ejecutar GZIP en toda su matriz y terminar con eso, pero eso perdería el acceso O (1), que es crucial para usted.

Una solución es utilizar Huffmann coding junto con una tabla de índice.

La codificación Huffmann funciona reemplazando cada símbolo de entrada (por ejemplo, un byte ASCII) con otro símbolo de variable longitud de bit, dependiendo de la frecuencia de ocurrencia en toda la secuencia.Por ejemplo, el carácter E aparece muy a menudo, por lo que obtiene una secuencia de bits cortos, mientras que 'W' es rara vez y obtiene una secuencia de bits larga.

E -> 0b10 
W -> 0b11110 

Ahora, comprima toda la matriz con este método. Desafortunadamente, dado que los símbolos de salida tienen una longitud variable, ya no puede indexar sus datos como antes: el número de elemento 15 ya no está en stream[15*sizeof(item)].

Afortunadamente, este problema se puede resolver utilizando una tabla de índice adicionalindex que almacena dónde comienza cada elemento en la secuencia comprimida. En otras palabras, los datos comprimidos para el artículo 15 se pueden encontrar en stream[index[15]]; la tabla de índice acumula las longitudes de salida variables.

Por lo tanto, para obtener el elemento 15, simplemente comience a descomprimir los bytes en stream[index[15]]. Esto funciona porque la codificación de Huffmann no hace nada extravagante a la salida, simplemente concatena las nuevas palabras de código, y puede comenzar la decodificación dentro de la transmisión sin tener que decodificar todos los elementos anteriores.

Por supuesto, la tabla de índice agrega algunos overhead; Es posible que desee ajustar la granularidad para que compressed data + index table sea aún menor que original data.

Answer 2

Bien, desde mi mejor entendimiento, lo que quiere es algún tipo de plantilla de acceso. Básicamente, crear un adaptador de plantilla que tiene como argumento una de sus tipos de elementos que se accede internamente a través de lo que sea, un puntero, un índice en su burbuja, etc. que el adaptador puntero similar:

const T &operator->(void) const; 

etc.ya que es más fácil crear un adaptador de puntero que un adaptador de referencia (aunque vea el vector si quiere saber cómo escribir uno de ellos). Aviso, hice este accesorio constante según sus pautas. Luego, calcule previamente sus compensaciones cuando la burbuja se cargue/comprima y llene el vector con su clase de adaptador con plantilla. ¿Esto tiene sentido? Si necesita más detalles, estaré encantado de proporcionarle.

En cuanto al algoritmo de compresión, sugiero que simplemente haga un análisis de frecuencia de bytes en su blob y luego ejecute su blob sin comprimir a través de una codificación Huffman codificada (como se sugirió más o menos anteriormente), capturando el desplazamiento de cada elemento y almacenarlo en su adaptador proxy que a su vez son los elementos de su matriz. De hecho, puede hacer que todo esto forme parte de una clase de compresión que comprima y genere elementos que puedan insertarse desde el principio en su vector. Nuevamente, responda si necesita código de muestra.

Answer 3

¿Está codificando para un sistema integrado y/o tiene cientos o miles de estos contenedores? Si no, aunque creo que esta es una pregunta teórica interesante (+1), sospecho que la desaceleración como resultado de hacer la descompresión no será trivial y que sería mejor usar el uso de std::vector.

A continuación, ¿está seguro de que los datos que está almacenando son lo suficientemente redundantes como para que bloques más pequeños sean realmente compresibles? ¿Has intentado guardar bloques de diferentes tamaños (poderes de 2 tal vez) e intenté ejecutarlos a través de gzip como un ejercicio? Puede ser que cualquier dato adicional necesario para ayudar al algoritmo de descompresión (dependiendo del enfoque) reduzca los beneficios de espacio de este tipo de contenedor comprimido.

Si decide que todavía es razonable hacer la compresión, existen al menos un par de posibilidades, aunque ninguna pre-escrita. Puede comprimir cada elemento individual, almacenando un puntero al fragmento de datos comprimidos. Entonces, el acceso al índice sigue siendo constante, solo necesita descomprimir los datos reales. Posiblemente el uso de un objeto proxy haría que la descompresión de datos real sea más fácil y transparente (y tal vez incluso le permita usar std::vector como contenedor subyacente).

O alternativamente, std::deque almacena sus datos en fragmentos, por lo que podría utilizar un enfoque similar aquí. Por ejemplo, std::vector<compressed_data_chunk>, donde cada fragmento contiene, por ejemplo, 10 elementos comprimidos juntos como su contenedor subyacente. Entonces todavía puede indexar directamente el fragmento que necesita, descomprimirlo y devolver el artículo de los datos descomprimidos. Si lo desea, su objeto contenedor (que contiene el vector) podría incluso almacenar en caché el último trozo descomprimido o dos para obtener un mayor rendimiento en el acceso consecutivo (aunque esto no ayudaría mucho en la búsqueda binaria).

Answer 4

He estado pensando en esto desde hace un tiempo. Desde un punto de vista teórico, identifiqué 2 posibilidades:

• Flyweight, porque la repetición puede reducirse con este patrón.
• serialización (compresión es alguna forma de serialización)

El primero es puramente orientado a objetos y encaja bien Creo que en general, no tienen la desventaja de ensuciar punteros por ejemplo.

El segundo parece mejor adaptado aquí, aunque tiene una ligera desventaja en general: invalidación del puntero + problemas con la codificación/decodificación del puntero, tablas virtuales, etc. ... Notablemente no funciona si los elementos se refieren a cada uno otros usan punteros en lugar de índices.

He visto algunas soluciones de "codificación Huffman", sin embargo, esto significa que para cada estructura se necesita proporcionar un algoritmo de compresión. No es fácil generalizar.

Así que preferiría ir por el otro lado y usar una biblioteca de compresión como 'zlib', eligiendo un algoritmo rápido como lzo, por ejemplo.

• B * árbol (o una variante) con un gran número de elementos por nodo (ya que no se mueve) como por ejemplo 1001. Cada nodo contiene una representación comprimida de la matriz de elementos. Los índices no están comprimidos.
• Posiblemente: cache_view para acceder al contenedor mientras se almacenan los últimos 5 nodos descomprimidos o algo así. Otra variante es implementar el recuento de referencias y mantener los datos descomprimidos siempre que alguien acceda a uno de los elementos en el nodo.

Algunas observaciones:

• si debe un gran número de elementos/teclas por nodo tiene cerca el tiempo de acceso constante, por ejemplo, con 1001 que significa que sólo hay 2 niveles de direccionamiento indirecto, siempre a medida que almacena menos de un millón de artículos, 3 niveles de indirección por mil millones, etc. ...
• puede construir un contenedor legible/grabable con dicha estructura. Lo haría de modo que solo vuelva a comprimir una vez que haya terminado de escribir el nodo.

Answer 5

¿Pueden algunas de las respuestas a "What is the best compression algorithm that allows random reads/writes in a file?" adaptarse a sus datos en memoria?