我的用例最有效的位向量壓縮方法是什麼？

我正在研究計算生物學的一個項目，我需要存儲許多序列之間不同的位點的索引。目前，我正在使用B +樹來達到這個目的，但我認爲使用位圖索引對於這樣的用例來說會更快：兩個序列之間只有少量的位點不同，平均爲1％在順序上幾乎是平均分配的;所以似乎有很多位圖索引壓縮的空間。我的問題是，我不能設法找到一個壓縮方法，可以有效地：我的用例最有效的位向量壓縮方法是什麼？

允許快速個別位設置/取消設置
許可證有效射程超過位圖的查詢
可能允許快速異或/ AND索引

Thx提前爲您的建議。

來源

2011-01-22 fokenrute

退房FastBit：

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

來源

2011-01-22 16:32:50

看起來很酷。不過，我懷疑它不支持快速更新，如果您想在運行過程中稍作修改，則需要在壓縮比特流的中間插入兩個字。也許你可以將比特流存儲在一個enfilade樹中以提高效率。 – 2011-01-22 17:06:52

非常酷，這實際上幫助了我的學士論文。謝謝一堆。如果您有權訪問，本文將介紹實際的編碼：http://dl.acm.org/citation.cfm?doid=502585.502689 – Honza 2012-04-10 19:23:05

你可以使用一個簡單的樹數據結構是這樣的：

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（長）位，n> = 0。如果葉子節點位於樹的底部，葉子節點將在「掩碼」中存儲原始位掩碼，否則它們將0存儲在「掩碼」中。這樣，'mask'值爲0的葉節點可以表示位數組中的（2^n）* sizeof（長）大小的空區域，因此可以有效地存儲稀疏位數組。

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％可能還沒有足夠稀疏，與僅僅一個普通的比特數組相比，這樣做更好（假設每個長度都存儲64個比特，平均有多個比特不超過2個長度），但是如果除了節省空間和時間以外，稀疏性還會增加。

來源

2011-02-15 14:56:52

我的用例最有效的位向量壓縮方法是什麼？

回答

相關問題