Qual è il metodo di compressione vettoriale bit più efficiente per il mio caso d'uso?

Question

Sto lavorando a un progetto di biologia computazionale e ho bisogno di memorizzare un indice di locus che differiscono tra molte sequenze. Per ora, sto usando un albero B + per questo scopo, ma suppongo che l'uso di un indice bitmap sarebbe molto più veloce per un caso d'uso di questo tipo: solo un piccolo numero di locus differisce tra due sequenze, l'1% in media, e sono quasi equamente distribuiti lungo la sequenza; quindi sembra che ci sia un sacco di spazio per la compressione dell'indice bitmap. mio problema è che non riesco a trovare un metodo di compressione che può efficacemente:

• consentire l'impostazione singolo bit/disinserimento
• permesso efficienti le query veloci di portata lungo la bitmap
• possibilmente permettono veloce XOR-ing/AND-ing di due indici

Thx in anticipo per i vostri suggerimenti.

Answer 1

Partenza FastBIT:

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

Answer 2

Si potrebbe utilizzare una semplice struttura dati ad albero simile a questo:

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

Ogni nodo rappresenta un sub-array della grande matrice di bit che è (2^n) * sizeof (long) bit, n> = 0. I nodi foglia archiviano una maschera bit grezza in 'maschera' se si trovano nella parte inferiore dell'albero, altrimenti memorizzano 0 in 'maschera'. In questo modo, il nodo foglia con un valore 'maschera' di 0 può rappresentare un'area (2^n) * sizeof (lunga) di dimensioni vuote nell'array di bit, in modo che gli array di bit sparsi possano essere memorizzati in modo efficiente.

leftChild e rightChild sono ovviamente nulli in tutti i nodi foglia. Ogni altro nodo ha un puntatore leftChild e rightChild e ogni nodo che non è un nodo foglia ha almeno un nodo discendente con maschera che contiene bit impostati.

Per trovare un po 'ad un determinato indice:

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); 
} 

Costruire l'albero e lo sviluppo di tutto il resto degli algoritmi dovrebbe essere abbastanza facile una volta capito l'idea. Non ho effettivamente testato il codice, poiché questa non è una soluzione completa, alcuni refusi o simili potrebbero rimanere. E io non sono un esperto di indice bitmap, potrebbe esserci (probabilmente è) un pacchetto già pronto che lo fa meglio, ma questa soluzione è semplice e dovrebbe essere relativamente efficiente. L'1% potrebbe non essere ancora abbastanza spoglio per renderlo migliore rispetto a un semplice array di bit (supponendo che i lunghi memorizzino 64 bit ciascuno, non ci vogliono più di 2 lunghi per avere in media più di un bit), ma se il la scarsità aumenta oltre a quello che mostrerà il risparmio di spazio e di tempo.