¿Cuál es el método de compresión de vectores de bits más eficiente para mi caso de uso?

Question

Estoy trabajando en un proyecto de biología computacional y necesito almacenar un índice de locus que difieren entre muchas secuencias. Por ahora, estoy usando un Árbol B + para ese propósito, pero supongo que usar un índice de mapa de bits sería mucho más rápido para ese caso de uso: solo un pequeño número de locus difiere entre dos secuencias, 1% en promedio, y están distribuidos casi por igual a lo largo de la secuencia; por lo que parece que hay mucho espacio para la compresión del índice de mapa de bits. Mi problema es que no consigo encontrar un método de compresión que puede de manera eficiente:

• permiten una configuración rápida y bit individual/desarmado
• permisos consultas de rango eficiente sobre el mapa de bits
• posiblemente permiten rápida XOR-ing/AND-ing de dos índices

Thx de antemano para sus sugerencias.

Answer 1

Salida FastBit:

https://sdm.lbl.gov/fastbit/

Answer 2

se puede utilizar una estructura de datos de árbol simple como esto:

struct node { 
    node * leftChild; 
    node * rightChild; 
    long mask; 
}; 
struct tree { 
    int exponent; // the size of the tree is 2^exponent 
    node rootNode; 
}; 

Cada nodo representa un sub-conjunto de la gran matriz de bits que es (2^n) * tamaño de bits (largos), n> = 0. Los nodos hoja almacenan una máscara de bits sin formato en 'máscara' si están en la parte inferior del árbol, de lo contrario almacenan 0 en 'máscara'. De esta forma, el nodo hoja con un valor de 'máscara' de 0 puede representar un área vacía de tamaño (2^n) * de largo (largo) en la matriz de bits, por lo que las matrices de bits dispersas se pueden almacenar de manera eficiente.

leftChild y rightChild son, por supuesto, nulos en todos los nodos de hoja. Cada otro nodo tiene un puntero leftChild y rightChild, y cada nodo que no es un nodo hoja tiene al menos un nodo descendiente con máscara que tiene bits establecidos en él.

Para conocer un poco a un índice determinado:

bool find_bit_at_index(tree t, long ind) { 
    long divider = 1 << (t.exponent - 1); 
    node *n = &t.rootNode; 
    node *lastNode; 
    while (n) 
    { 
     lastNode = n; 
     if (ind >= divider) { 
      n = n->rightChild; 
      ind -= divider; 
     } 
     else { 
      n = n->leftChild; 
     } 
     divider >>= 1; 
    } 
    return lastNode->mask & (1 << ind); 
} 

Construir el árbol y el desarrollo del resto de los algoritmos debe ser bastante fácil una vez que entienda la idea. En realidad, no he probado el código, ya que esta no es una solución completa, podrían quedar algunos errores tipográficos o similares. Y no soy un experto en índices de mapas de bits, puede haber (probablemente) un paquete listo que lo haga mejor, pero esta solución es simple y debería ser relativamente eficiente. Es posible que el 1% aún no sea lo suficientemente escaso para hacerlo mejor en comparación con solo una matriz de bits simple (suponiendo que los datos almacenan 64 bits cada uno, no se requieren más de 2 búsquedas para tener más de un bit establecido en promedio), pero si la escasez aumenta más allá de lo que mostrarán los ahorros en espacio y tiempo.