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

data-structures information-retrieval (7)

Tengo una aplicación de recuperación de información que crea matrices de bits del orden de 10 s de un millón de bits. El número de bits "establecidos" en la matriz varía ampliamente, de todo claro a todo conjunto. Actualmente, estoy usando una matriz de bits directa ( java.util.BitSet ), por lo que cada una de las matrices de mis bits requiere varios megabytes.

Mi plan es observar la cardinalidad de los primeros N bits, luego tomar 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 se configuran aproximadamente la mitad de los bits (cuando se establecen la mayoría de los bits, 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 consejos:

Los bits se establecen solo una vez, y en orden de índice.
Necesito el 100% de precisión, por lo que algo como un filtro Bloom no es lo suficientemente bueno.
Después de que se haya creado el conjunto, necesito poder iterar eficientemente sobre los bits "establecidos".
Los bits se distribuyen aleatoriamente, por lo que los algoritmos de codificación de longitud de ejecución probablemente no sean mucho mejores que una simple lista de índices de bits.
Estoy tratando de optimizar la utilización de la memoria, pero la velocidad aún tiene algo de peso.

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

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

Rápida prueba combinatoria de que no puedes ahorrar mucho espacio:

Supongamos que tiene un subconjunto arbitrario de n / 2 bits establecido 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 a las elecciones más probables representaciones más cortas. Entonces necesitamos log_2 (n choose n / 2) bits, que es sobre n - (1/2) log (n) bits.

Eso no es un muy buen ahorro de memoria. Por ejemplo, si trabaja con n = 2 ^ 20 (1 meg), solo puede guardar unos 10 bits. No vale la pena.

Habiendo dicho todo eso, también parece muy poco probable que cualquier información realmente útil sea verdaderamente aleatoria. En caso de que haya más estructura en sus datos, probablemente haya una respuesta más optimista.

Un pensamiento de compresión más:

Si la matriz de bits no es lo suficientemente larga, podría intentar aplicar la transformación Burrows-Wheeler antes de usar cualquier codificación de repetición, como Huffman. Una implementación ingenua tomaría O (n ^ 2) memoria durante la (de) compresión y O (n ^ 2 log n) tiempo para descomprimir - es casi seguro que también se tengan atajos. Pero si hay alguna estructura secuencial para 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 mantener el uso del tiempo / memoria 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.

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 Huffman, pero esto es especialmente cierto cuando el tamaño del alfabeto es muy pequeño. De hecho, cuando el "alfabeto nativo" es simplemente 0s y 1s, la única forma en que Huffman puede obtener cualquier compresión es mediante la combinación de esos símbolos, que es exactamente lo que la codificación de rango hará, de manera más efectiva.

Quizás sea demasiado tarde para ti, pero hay una biblioteca muy rápida y eficiente en memoria para matrices de bits dispersos (sin pérdida) y otros tipos de datos basados en intentos. Mira las matrices de Judy

A menos que los datos sean verdaderamente aleatorios y tengan una distribución simétrica 1/0, esto simplemente se convierte en un problema de compresión de datos sin pérdida y es muy similar a la compresión del Grupo 3 del CCITT utilizada para imágenes de FAX en blanco y negro (es decir, binarias). El Grupo 3 del CCITT usa un esquema de codificación Huffman. En el caso de FAX, están utilizando 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 y cuando solo necesites acceder a los bits secuencialmente, como implicaste, 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 binaria para varios puntos de compensación en la matriz que le permitiría acercarse a la ubicación deseada y luego caminar desde allí.

Nota : El esquema Huffman aún funciona bien incluso si los datos son aleatorios, siempre y cuando la distribución 1/0 no sea perfectamente pareja. 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, de acuerdo con el Sr. Claude Shannon , no podrás comprimirlo en cantidades significativas usando ningún esquema.

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

Recogeré todos los primeros N hits en una matriz de bits convencional, y elegir uno de los tres métodos, en función de la simetría de esta muestra.

Si la muestra es muy 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érdida como la codificación Huffman sugerida por InSciTekJeff .

Los límites entre las regiones asimétrica, moderada y simétrica dependerán del tiempo requerido por los diversos algoritmos equilibrados con el espacio que necesitan, donde el valor relativo del tiempo frente al 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 pruebas. Además, probaré los tres métodos para determinar los requisitos de tiempo de mi implementación.

Es posible (y de hecho estoy esperando) que el método de compresión del medio sea siempre mejor que la lista o la matriz de bits, o ambas cosas. Tal vez pueda alentar esto eligiendo un conjunto de códigos Huffman adaptados para una simetría mayor o menor. Entonces puedo simplificar el sistema y solo usar dos métodos.