¿Cuáles son algunas alternativas a una matriz de bits?

Question

Tengo una aplicación de recuperación de información que crea matrices de bits del orden de decenas de millones de bits.El número de bits "establecidos" en la matriz varía ampliamente, desde todo limpio hasta todo establecido.Actualmente, estoy usando una matriz de bits sencilla (java.util.BitSet), por lo que cada una de mis matrices de bits ocupa varios megabytes.

Mi plan es observar la cardinalidad del primero. norte bits, luego tome una decisión sobre qué estructura de datos usar para el resto.Claramente, algunas estructuras de datos son mejores para matrices de bits muy dispersas y otras cuando aproximadamente la mitad de los bits están configurados (cuando la mayoría de los bits están configurados, puedo usar la negación para tratarlo como un conjunto disperso de ceros).

• ¿Qué estructuras podrían ser buenas en cada extremo?
• ¿Hay alguno en el medio?

Aquí hay algunas restricciones o sugerencias:

1. Los bits se configuran sólo una vez y en orden de índice.
2. Necesito una precisión del 100%, por lo que algo como un filtro Bloom no es lo suficientemente bueno.
3. Una vez creado el conjunto, necesito poder iterar eficientemente sobre los bits del "conjunto".
4. Los bits se distribuyen aleatoriamente, por lo que no es probable que los algoritmos de codificación de longitud de ejecución sean mucho mejores que una simple lista de índices de bits.
5. Estoy intentando optimizar la utilización de la memoria, pero la velocidad aún se mantiene. alguno peso.

Algo con una implementación Java de código abierto es útil, pero no estrictamente necesario.Estoy más interesado en los fundamentos.

Answer 1

A menos que los datos sean verdaderamente aleatorios y tiene una distribución simétrica 1/0, entonces esto simplemente se convierte en un problema de compresión de datos sin pérdidas y es muy análogo a la compresión CCITT Grupo 3 utilizada para blanco y negro (es decir:Binario) Imágenes de FAX.El CCITT Grupo 3 utiliza un esquema de codificación Huffman.En el caso de FAX, utilizan un conjunto fijo de códigos Huffman, pero para un conjunto de datos determinado, puede generar un conjunto específico de códigos para cada conjunto de datos para mejorar la relación de compresión lograda.Siempre que solo necesite acceder a los bits de forma secuencial, como insinuó, este será un enfoque bastante eficiente.El acceso aleatorio crearía algunos desafíos adicionales, pero probablemente podría generar un índice de árbol de búsqueda binario para varios puntos de desplazamiento en la matriz que le permitiría acercarse a la ubicación deseada y luego caminar desde allí.

Nota:El esquema de Huffman sigue funcionando bien incluso si los datos son aleatorios, siempre que la distribución 1/0 no sea perfectamente uniforme.Es decir, cuanto menos uniforme sea la distribución, mejor será la relación de compresión.

Finalmente, si los bits son verdaderamente aleatorios con una distribución uniforme, entonces, bueno, según Señor.Claude Shannon, no podrá comprimirlo en una cantidad significativa utilizando ningún esquema.

Answer 2

Consideraría seriamente utilizar la codificación de rango en lugar de la codificación de Huffman.En general, la codificación de rango puede explotar la asimetría de manera más efectiva que la codificación de Huffman, pero esto es especialmente cierto cuando el tamaño del alfabeto es tan pequeño.De hecho, cuando el "alfabeto nativo" es simplemente 0 y 1, la única forma en que Huffman puede obtener alguna compresión es combinando esos símbolos, que es exactamente lo que hará la codificación de rango, de manera más efectiva.

Answer 3

Quizás sea demasiado tarde para usted, pero existe una biblioteca muy rápida y eficiente en memoria para matrices de bits dispersos (sin pérdidas) y otros tipos de datos basados ​​en intentos.Mira a matrices judy

Answer 4

Gracias por las respuestas.Esto es lo que voy a intentar para elegir dinámicamente el método correcto:

Recogeré todo el primero. norte aciertos en una matriz de bits convencional y elija uno de los tres métodos, según la simetría de esta muestra.

• Si la muestra es altamente asimétrica, simplemente almacenaré los índices en los bits establecidos (o tal vez la distancia al siguiente bit) en una lista.
• Si la muestra es altamente simétrica, seguiré usando una matriz de bits convencional.
• Si la muestra es moderadamente simétrica, usaré un método de compresión sin pérdidas como Huffman Coding sugerido por inscitekjeff.

Los límites entre las regiones asimétrica, moderada y simétrica dependerán del tiempo requerido por los distintos algoritmos equilibrados con el espacio que necesitan, donde el valor relativo del tiempo versus el espacio sería un parámetro ajustable.El espacio necesario para la codificación de Huffman es una función de la simetría, y lo perfilaré con las pruebas.Además, probaré los tres métodos para determinar los requisitos de tiempo de mi implementación.

Es posible (y de hecho espero) que el método de compresión intermedia siempre sea mejor que la lista, la matriz de bits o ambos.Quizás pueda fomentar esto eligiendo un conjunto de códigos de Huffman adaptados para una simetría mayor o menor.Entonces puedo simplificar el sistema y simplemente usar dos métodos.

Answer 5

Un pensamiento de compresión más:

Si la matriz de bits no es muy larga, puede intentar aplicar el Transformada de Burrows-Wheeler antes de utilizar cualquier codificación de repetición, como Huffman.Una implementación ingenua requeriría O(n^2) memoria durante la (des)compresión y O(n^2 log n) tiempo para descomprimir; es casi seguro que también existen atajos.Pero si hay alguna estructura secuencial en sus datos, esto realmente debería ayudar a la codificación de Huffman.

También puede aplicar esa idea a un bloque a la vez para que el uso de tiempo/memoria sea más práctico.Usar un bloque a la vez podría permitirle mantener siempre comprimida la mayor parte de la estructura de datos si está leyendo/escribiendo secuencialmente.

Answer 6

La compresión sencilla y sin pérdidas es el camino a seguir.Para que se pueda realizar búsquedas, deberá comprimir bloques relativamente pequeños y crear un índice en una matriz de bloques.Este índice puede contener el desplazamiento de bits del bit inicial en cada bloque.

Answer 7

Prueba combinatoria rápida de que realmente no se puede ahorrar mucho espacio:

Supongamos que tiene un subconjunto arbitrario de n/2 bits configurado en 1 de n bits totales.Tienes (n elige n/2) posibilidades.Usando La fórmula de Stirling., esto es aproximadamente 2^n / sqrt(n) * sqrt(2/pi).Si todas las posibilidades son igualmente probables, entonces no hay forma de dar representaciones más cortas a las opciones más probables.Entonces necesitamos log_2 (n elija n/2) bits, que son aproximadamente n - (1/2)log(n) bits.

Ese no es un muy buen ahorro de memoria.Por ejemplo, si está trabajando con n=2^20 (1 mega), entonces sólo podrá guardar unos 10 bits.No vale la pena.

Dicho todo esto, también parece muy poco probable que algún dato realmente útil sea verdaderamente aleatorio.En caso de que sus datos tengan más estructura, probablemente haya una respuesta más optimista.