Tengo una necesidad especial y las preocupaciones más importantes son:algoritmo: gigantesco número de matrices de bits muy dispersos, que codificación a usar
- en memoria
- muy bajo consumo de memoria
- velocidad
Aquí está mi "problema": Necesito almacenar, en la memoria, un gran número de matrices de bits muy dispersas. Esos bitsets son "solo anexados" y se deben usar principalmente para intersecciones. En grande, me refiero a arreglos de hasta 200 000 bits.
El rango debe estar entre [0 ... 16 000 000] para cada conjunto de bits.
que corrieron algunos pre-test con "sólo" 10 673 matrices de bits que contiene algunos datos reales que tengo y tiene los siguientes resultados:
1% of the bit arrays ( 106 bit arrays) Hamming weight: at most 1 bit set
5% of the bit arrays ( 534 bit arrays) Hamming weight: at most 4 bits set
10% of the bit arrays (1068 bit arrays) Hamming weight: at most 8 bits set
15% of the bit arrays (1603 bit arrays) Hamming weight: at most 12 bits set
20% of the bit arrays (2137 bit arrays) Hamming weight: at most 17 bits set
25% of the bit arrays (2671 bit arrays) Hamming weight: at most 22 bits set
30% of the bit arrays (3206 bit arrays) Hamming weight: at most 28 bits set
35% of the bit arrays (3740 bit arrays) Hamming weight: at most 35 bits set
40% of the bit arrays (4274 bit arrays) Hamming weight: at most 44 bits set
45% of the bit arrays (4809 bit arrays) Hamming weight: at most 55 bits set
50% of the bit arrays (5343 bit arrays) Hamming weight: at most 67 bits set
55% of the bit arrays (5877 bit arrays) Hamming weight: at most 83 bits set
60% of the bit arrays (6412 bit arrays) Hamming weight: at most 103 bits set
65% of the bit arrays (6946 bit arrays) Hamming weight: at most 128 bits set
70% of the bit arrays (7480 bit arrays) Hamming weight: at most 161 bits set
75% of the bit arrays (8015 bit arrays) Hamming weight: at most 206 bits set
80% of the bit arrays (8549 bit arrays) Hamming weight: at most 275 bits set
85% of the bit arrays (9083 bit arrays) Hamming weight: at most 395 bits set
90% of the bit arrays (9618 bit arrays) Hamming weight: at most 640 bits set
95% of the bit arrays (10152 bit arrays) Hamming weight: at most 1453 bits set
96% of the bit arrays (10259 bit arrays) Hamming weight: at most 1843 bits set
97% of the bit arrays (10366 bit arrays) Hamming weight: at most 2601 bits set
98% of the bit arrays (10473 bit arrays) Hamming weight: at most 3544 bits set
99% of the bit arrays (10580 bit arrays) Hamming weight: at most 4992 bits set
100% of the bit arrays (10687 bit arrays) Hamming weight: at most 53153 bits set
visto los números implicados, que obviamente tendrá que utilizar comprimido arreglos de bits y eso no es un problema: debe ser fácil de tratar visto que las matrices de bits son "solo agregar".
Los bits de la matriz de bits que están encendidos están algo agrupados, pero no totalmente. Por lo tanto, tenderá a tener varios bits en la misma área (pero normalmente no uno después de otro, lo que hace que RLE no sea lo suficientemente bueno para los bits que están activados).
Mi pregunta es ¿qué tipo de compresión usar?
Ahora no sé si debería poner mi primer enfoque aquí o en una respuesta a mi propia pregunta.
Básicamente lo que imaginaba un escenario de "peor de los casos", utilizando una codificación muy tonta:
1 bit: Si está activado, los siguientes 5 bits determinan la cantidad de bits necesaria para calcular el 'omisiones', si off, optimización: los siguientes 5 bits determinan cuántos bits se deben tomar literalmente (es decir, 'on' u 'off', sin omitir) [esto solo se cambiará cuando se determine que es más eficiente que la otra representación, por lo que cuando entre, siempre habrá una optimización (tamaño-sabio)]
5 bits: cuántos bits podemos omitir antes de la siguiente bi t en
x bits de: omitir
Aquí está un ejemplo: una matriz de bits tiene conjunto de 3 bits, el primer bit de estar en 3 098 137, el segundo en 3 098 141 y la tercera en 3 098 143.
+-- now we won't skip
|
| +-- 3 because we need 3 bits to store "6" (from 3 098 138 to 3 098 143)
| | +--- 3 098 141 is on
22 3 098 137 | 3 | +- 3 098 143 is on
1 10110 1011110100011000011001 0 00011 000101 etc.
El primer bit dice que vamos a omitir los bits. 5 bits siguientes (siempre 5) indica cuántos bits necesitamos para saber cuántos bits omitiremos 22 bits diciendo omitir a 3 098 137 un bit apagado diciendo ahora que no estamos salteando los bits 5 bits siguientes (siempre 5) cuenta el número de bits leeremos "tal cual" 6 bits de: fuera, fuera, fuera, encendido, apagado, es decir, en 3 098 141 y 3 098 143 están en etc.
visto el increíble la escasez de estas matrices de bits, esto parece bastante eficiente en cuanto a tamaño.
Utilicé esa codificación, tomé los datos de muestra y calculé el peor de los casos (todavía no escribí el algoritmo, prefiero tener algunas entradas): básicamente consideré que no solo la "optimización de tamaño" nunca funcionaría y, también, que los 5 bits siempre se ajustarían a su valor máximo (24 bits), lo que por supuesto no puede suceder.
Lo hice solo para tener una aproximación muy cruda de lo que podría ser el "peor de los peores" casos.
Me sorprendió muy gratamente:
Worst case scenario:
108 913 290 bits needed for the 10 687 very sparse bit arrays
12.9 MB (13 295 KB)
Los que son datos reales y todos los datos son datos similares, sé que, si las cosas se ponen peor, podría guardar mis 200 000 matrices de bits en aproximadamente 240 MB, lo cual está bien.
Estoy bastante seguro de que la codificación real será menos que eso, pero como aún no la he escrito, solo puedo (muy fácilmente) calcular el "peor caso", por lo que solo muestro eso uno.
Cualquier sugerencia/idea sobre cómo hacer esto más eficiente en cuanto al tamaño (recordando que estas son matrices de bits súper dispersas, que habrá cientos de miles, que deben estar en la memoria, y que serán " Añadir solo ")?
Acerca de mi caso 'solo-agregar'
Básicamente tengo una creciente "expansión" (la gama, pero "expansión" es el término real como yo lo entiendo) y una gran cantidad de matrices de bits que tienen algunos conjuntos de bits. Cuando el rango va desde, digamos, 0 a 1 000 000, todas las matrices de bits van de 0 a 1 000 000 a. Cuando el rango crece a 1 000 001, todas las matrices de bits también crecen, todo en un bit. Pero la mayoría de estas matrices de bits tendrán un '0' agregado en su extremo, mientras que aproximadamente de 4 a 8 de las matrices de bits tendrán un '1' agregado en su extremo. Sin embargo, no puedo predecir de antemano cuál de las matrices de bits tendrá un 0 o un 1 anexado.
Así que tengo un montón de matrices de bits que tienen todas del mismo tamaño, que son todas escasas (< 0.5% de sus bits) y que están "creciendo" a medida que aumenta el rango (entonces re todos siempre creciendo al mismo ritmo).
Judy arrays son geniales. Pero leí sobre ellos hace unos años y esas cosas estaban "por encima de mi cabeza". Las matrices de Judy son una lib 20KLOC exclusiva de C y definitivamente no estoy volviendo a implementar eso. Pero son increíbles.
Así que supongo que tengo que añadir que me gustaría que todo esto se mantuviera relativamente simple, lo que no es tan exagerado como la propiedad especial de "solo agregar" de mis matrices de bits muy dispersas.
Tenga en cuenta que los comentarios sobre reinventar la rueda se pueden enviar a */dev/null *: si solo para la matemática/desafío detrás de ella Quiero implementar esto yo mismo. Y de todos modos estaría muy sorprendido de encontrar una rueda que pueda manejar 200 000 arreglos de bits "solo para agregar" en la memoria :) Pero si tienes uno, la mecánica detrás de esto me interesa mucho :) – SyntaxT3rr0r
Hay teoría límite en la densidad de codificación: con un conjunto de N elementos, de los cuales n se establecen, el número mínimo de bits para codificar sería -n * log2 (n/N) - (Nn) * log (1-n/N). Para su matriz en la que se establece 53153 de 16M, esta sería de 514kBits y para 4992 bits configurada - 65 kBits. Y acerque su memoria a este límite, codificación más compleja que debe elegir. – Vovanium
@Vovanium, creo que dejaste fuera un contexto necesario para tu límite teórico (como, algún tipo de suposición estadística sobre la distribución de los bits que se establecen?) – comingstorm