Phương pháp nén bit bit hiệu quả nhất cho trường hợp sử dụng của tôi là gì?

Question

Tôi đang làm việc trên một dự án về sinh học tính toán và tôi cần lưu trữ chỉ mục các locus khác nhau giữa nhiều trình tự. Hiện tại, tôi đang sử dụng cây B + cho mục đích đó, nhưng tôi đoán sử dụng chỉ mục bitmap sẽ nhanh hơn cho trường hợp sử dụng như vậy: chỉ một số ít locus khác nhau giữa hai chuỗi, trung bình 1% và được phân phối gần như ngang nhau theo trình tự; do đó, có vẻ như có rất nhiều chỗ để nén chỉ mục bitmap. Vấn đề của tôi là tôi không thể quản lý để tìm một phương pháp nén mà có thể có hiệu quả:

• phép chút thiết lập cá nhân/unset
• giấy phép có hiệu quả truy vấn phạm vi nhanh hơn bitmap
• có thể cho phép nhanh XOR-ing/VÀ-ing của hai chỉ mục

Thx trước cho các đề xuất của bạn.

Answer 1

Check-out FastBit:

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

Answer 2

Bạn có thể sử dụng một cấu trúc dữ liệu cây đơn giản như thế này:

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

Mỗi nút biểu một tiểu mảng của mảng chút lớn đó là (2^n) * kích thước (dài) bit, n> = 0. Nút lá lưu trữ một mặt nạ bit thô trong 'mặt nạ' nếu chúng ở dưới cùng của cây, nếu không chúng sẽ lưu 0 trong 'mặt nạ'. Bằng cách này, nút lá có giá trị 'mặt nạ' là 0 có thể đại diện cho một vùng trống (dài 2) kích thước (dài) trong mảng bit, vì vậy mảng bit thưa có thể được lưu trữ một cách hiệu quả.

leftChild và rightChild tất nhiên là null trong tất cả các nút lá. Mỗi nút khác có cả con trỏ leftChild và rightChild, và mọi nút không phải là nút lá có ít nhất một nút con với mặt nạ có bit được đặt trong nó.

Để tìm một chút tại một chỉ số đưa ra:

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

Xây dựng cây và phát triển các phần còn lại của các thuật toán nên đủ dễ dàng khi bạn hiểu được ý tưởng. Tôi đã không thực sự thử nghiệm mã, vì đây không phải là một giải pháp hoàn chỉnh, một số lỗi chính tả hoặc như vậy có thể vẫn còn. Và tôi không phải là chuyên gia về chỉ số bitmap, có thể có (có thể là) một gói sẵn sàng thực hiện điều này tốt hơn, nhưng giải pháp này rất đơn giản và nên tương đối hiệu quả. 1% có thể chưa đủ thưa thớt để làm điều này tốt hơn so với chỉ một mảng bit đơn giản (giả sử thời lượng lưu trữ 64 bit mỗi bit, không mất nhiều hơn 2 thời gian để có nhiều hơn một bit đặt ở mức trung bình), nhưng nếu sparsity tăng vượt ra ngoài mà không gian và tiết kiệm thời gian sẽ hiển thị.