Какой метод сжатия битового вектора наиболее эффективен для моего варианта использования? - PullRequest
Новая
       19

Какой метод сжатия битового вектора наиболее эффективен для моего варианта использования?

8 голосов
/ 22 января 2011


Я работаю над проектом в области вычислительной биологии, и мне нужно сохранить индекс локусов, которые отличаются между многими последовательностями.На данный момент я использую B + Tree для этой цели, но я предполагаю, что использование индекса растрового изображения было бы намного быстрее для такого варианта использования: только небольшое количество локусов отличается между двумя последовательностями, в среднем 1%, и онипочти одинаково распределены по последовательности;так что кажется, что есть много места для сжатия растровых индексов.Моя проблема в том, что мне не удается найти метод сжатия, который может эффективно:

  • разрешить быструю установку / удаление отдельных битов
  • разрешить запросы эффективного диапазона по битовой карте
  • возможно разрешить быстрый XOR-IN / AND-IN из двух индексов

Заранее спасибо за ваши предложения.

Ответы [ 2 ]

2 голосов
/ 22 января 2011

Проверьте FastBit:

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

0 голосов
/ 15 февраля 2011

Вы можете использовать простую древовидную структуру данных, такую ​​как: 

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

Каждый узел представляет подмассив большого битового массива, который имеет (2 ^ n) * размер (длинных) битов, n> = 0. Листовые узлы хранят необработанную битовую маску в «маске», если они находятся в нижней части дерева, в противном случае они хранят 0 в «маске». Таким образом, листовой узел со значением «mask» 0 может представлять пустую область размером (2 ^ n) * sizeof (long) в массиве битов, поэтому разреженные битовые массивы могут быть эффективно сохранены.

leftChild и rightChild, конечно, равны нулю во всех конечных узлах. Каждый другой узел имеет указатель leftChild и rightChild, а каждый узел, который не является конечным узлом, имеет по крайней мере один узел-потомок с маской, в которой установлены биты.

Чтобы найти бит по заданному индексу: 

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

Построение дерева и разработка остальных алгоритмов должно быть достаточно легким, как только вы поймете идею. Я на самом деле не тестировал код, так как это не полное решение, некоторые опечатки или тому подобное могут остаться. И я не эксперт по растровым индексам, может быть (возможно, есть) готовый пакет, который делает это лучше, но это решение простое и должно быть относительно эффективным. 1% еще может быть недостаточно разреженным, чтобы сделать это лучше по сравнению с простым массивом битов (при условии, что long хранит по 64 бита каждый, для установки более одного бита в среднем требуется не более 2 long), но если редкость возрастает сверх того, что покажет экономия пространства и времени.

...