Jaka jest najskuteczniejsza metoda kompresji wektora bitowego dla mojego przypadku użycia?

Question

Pracuję nad projektem z dziedziny biologii obliczeniowej i muszę przechowywać indeks lokalizacji, które różnią się między wieloma sekwencjami. Na razie używam do tego celu drzewa B +, ale domyślam się, że użycie indeksu bitmapowego byłoby o wiele szybsze w takim przypadku użycia: tylko niewielka liczba locus różni się między dwiema sekwencjami, średnio 1%, i są prawie równomiernie rozmieszczone wzdłuż sekwencji; więc wydaje się, że jest dużo miejsca na kompresję indeksu bitmapowego. Moim problemem jest to, że nie uda się znaleźć metodę kompresji, która może skutecznie:

• umożliwiają szybkie indywidualnych ustawień bit/wyłączania
• umożliwienia skutecznego wyszukiwania zasięgu ponad bitmapy
• ewentualnie umożliwić szybki XOR-ing/AND-IN dwóch indeksów:

Thx z wyprzedzeniem za sugestie.

Answer 1

Wyjazd FastBit:

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

Answer 2

Można użyć prostego struktury danych drzewa tak:

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

Każdy węzeł reprezentuje sub-tablicę dużego bitowej tablicy, która jest (2^n) * sizeof (długie) bity, n> = 0. Węzły liści przechowują surową maskę bitową w "masce", jeśli znajdują się w dolnej części drzewa, w przeciwnym razie przechowują 0 w "masce". W ten sposób węzeł liścia z "maską" o wartości 0 może reprezentować (2^n) * sizeof (long) - rozmiar pustego obszaru w tablicy bitów, dzięki czemu rzadkie tablice bitów mogą być efektywnie przechowywane.

leftChild i rightChild są oczywiście puste we wszystkich węzłach liści. Każdy inny węzeł ma wskaźnik leftChild i rightChild, a każdy węzeł, który nie jest węzłem liścia, ma co najmniej jeden węzeł potomny z maską, w której są ustawione bity.

Aby dowiedzieć się trochę w danym indeksie:

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

konstruowania drzewa i rozwój algorytmów reszta powinna być na tyle łatwe, jeżeli rozumie się ten pomysł. Właściwie nie testowałem kodu, ponieważ nie jest to kompletne rozwiązanie, niektóre literówki lub takie mogą pozostać. Nie jestem ekspertem od map bitowych, może istnieć (prawdopodobnie jest) gotowy pakiet, który robi to lepiej, ale to rozwiązanie jest proste i powinno być względnie wydajne. 1% może nie być jeszcze wystarczająco rzadki, aby uczynić to lepszym w porównaniu do zwykłej tablicy bitów (zakładając, że longi przechowują po 64 bity, nie potrzeba więcej niż 2 longs, aby mieć średnio więcej niż jeden bit), ale jeśli Sparsity wzrośnie ponad to, co pokażą oszczędności czasu i przestrzeni.