유스 케이스에 가장 효율적인 비트 벡터 압축 방법은 무엇입니까?

Question

저는 전산 생물학 프로젝트를 진행하고 있으며 많은 서열 사이에 다른 궤적 색인을 저장해야합니다. 지금은 B + Tree를 사용하고 있지만 비트 맵 인덱스를 사용하면 두 개의 시퀀스 사이에 소수의 궤적이 다르다는 것을 알 수 있습니다. 시퀀스를 따라 거의 균등하게 분배된다. 그래서 비트 맵 인덱스 압축을위한 많은 공간이있는 것처럼 보입니다. 내 문제는 내가 효율적으로 할 수있는 압축 방법을 찾을 관리 할 수 ​​있다는 것입니다 :

• 비트 맵을 통해 빠른 개별 비트 설정/반환하기
• 허가 효율적인 범위 쿼리
• 가능하게 할 수 있도록를 빠르게 XOR-ING/두 인덱스 AND-ing

Thx 사전에 제안 사항을 입력하십시오.

Answer 1

체크 아웃 FastBit :

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

Answer 2

당신은이 같은 간단한 트리 데이터 구조를 사용할 수는 :

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

모든 노드는 큰 비트 배열의 하위 배열 (대표 2^n) * sizeof (long) 비트, n> = 0. 리프 노드는 트리의 맨 아래에있는 경우 원시 비트 마스크를 '마스크'에 저장하고 그렇지 않은 경우 '마스크'에 0을 저장합니다. 이 방법으로 'mask'값이 0 인 잎 노드는 비트 배열에서 (2^n) * sizeof (long) 크기의 빈 영역을 나타낼 수 있으므로 스파 스 비트 배열을 효율적으로 저장할 수 있습니다.

leftChild와 rightChild는 물론 모든 리프 노드에서 null입니다. 다른 모든 노드에는 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 %는 아직 일반 비트 배열 (64 비트를 각각 저장하는 것으로 가정 할 때, 평균적으로 1 비트 이상을 설정하는 데 2 ​​개 이상의 long을 취하지 않는다고 가정 함)과 비교할 때 이보다 더 좋지 않을만큼 희박하지는 않지만, 희소성이 그 이상으로 증가하면 공간 및 시간 절감 효과가 나타납니다.