位元魔法
v.7.13.4
BitMagic 是作為用於資訊檢索的集合代數工具包而創建的，但目前已發展成為更通用的資料科學組件庫，用於簡潔資料向量上的記憶體緊湊結構和演算法。 BitMagic 基於位元切片變換、Rank-Select 壓縮和記憶體壓縮模型的邏輯計算的想法實現了壓縮的位元向量和容器（向量）。
所有 BitMagic 簡潔容器均可序列化（使用最先進的二進位插值編碼進行壓縮），以實現高效儲存和網路傳輸。所有容器都可以以壓縮形式快速搜尋。
BitMagic 提供了一組方法和工具來建立您的應用程序，以使用HPC 技術來節省運行中的記憶體（從而能夠在一個計算單元中容納更多資料），在將資料向量和模型儲存在檔案或對象中時改進儲存和流量模式儲存（SQL 或 noSQL），優化從低階（CPU 快取）到網路和儲存交換的系統頻寬。
BitMagic 支援兩大類場景：
BitMagic 被用作以下功能的構建塊：
請造訪我們的用例說明：http://bitmagic.io/use-case.html
BitMagic 函式庫是一個高效能函式庫，實現了針對各種平台和建置目標的最佳化：
BitMagic 使用資料並行向量化設計，其目標不僅是提供最佳的單執行緒效能，而且促進多核心系統上的高度並行運算。
BitMagic 使用一套壓縮演算法、過濾器和轉換來減少記憶體佔用、儲存成本和網路資料傳輸。 http://bitmagic.io/design.html
請造訪我們的技術說明：http://bitmagic.io/articles.html
BitMagic 支援將位元向量重新解釋為兩側為 0 的非重疊範圍 1 的集合（例如：011110110）。常規集合函數提供集合交集/並集區間操作，實現區間迭代器並蒐索區間邊界。範圍和區間在生物資訊學中具有很大的用途，因為基因組數據通常被註釋為座標範圍。 BitMagic 提供了在編碼為位元向量的間隔上進行高效操作的構建塊（查找間隔開始/結束、檢查範圍是否為 inetrval、迭代間隔
BitMagic 以緊湊的雙位元向量表示形式實現 True/False/Unknown 的三值邏輯（也稱為三元邏輯、三價、三元）的邏輯運算，支援遵循 Kleene 定義的反轉、AND、OR 運算。 https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic
BitMagic 使用兩階段序列化-反序列化的概念。重點是快速反序列化。 BitMagic 實作了用於快速向量範圍反序列化和壓縮 BLOB 的收集反序列化的 API。 BitMagic 的終極功能是能夠處理壓縮資料。
這是 RAM 中的主要操作狀態，其中向量以記憶體緊湊形式保存。簡潔不是壓縮。可以存取容器中的隨機元素、解碼區塊、迭代向量、進行更新、運行搜尋演算法。 Stage One 提供透明的使用，它的向量看起來很像 STL。 Succinct 是記憶體緊湊但未完全壓縮的。
BitMagic 可以序列化所有容器和向量，並基於啟發式區塊和編解碼器進行額外壓縮。主要編碼技術是：二進位插值編碼 (BIC) 和 Elias Gamma。
BitMagic 容器被稱為「稀疏」向量，但實際上它的壓縮方案對於稀疏和密集資料都適用。
BitMagic 在 Gov2 倒排列表基準集和專有資料集數量上進行了測試。 http://bitmagic.io/bm5-cmpr.html
反序列化總是回到第一階段，因此資料並沒有完全解碼，而是
RAM 中簡潔。我們的目標是減少應用程式記憶體佔用並改善反序列化延遲。解壓縮演算法支援任意範圍的反序列化，甚至收集元素的反序列化。
BitMagic 支援基於位元轉置換的簡潔（記憶體緊湊）向量
也稱為位元平面壓縮 (BPC)（又稱位元切片）加上排名選擇壓縮。 BitMagic 簡潔向量有點誤導性地標記為“稀疏”，但它們適用於密集向量。
位元轉置解決了兩個目的：釋放未使用的位元平面並將規律性和熵隔離為單獨的（稀疏）位元向量。位元平面壓縮提供了卓越的記憶體效能和快速搜尋。設計目標之一是使用快速向量化邏輯運算對簡潔向量執行無索引搜尋。
BitMagic 簡潔向量可以記憶體壓縮形式進行無索引搜尋。速度很快！
簡潔的位元轉置實作對於整數向量（有符號或無符號）以及字串向量都適用。它可以與前綴樹等其他簡潔方案相媲美。簡潔向量可以是已排序的也可以是未排序的。這裡的想法與 Apache Arrow-Parquet 類似，但它透過位元平面壓縮和加速 Rank-Select 壓縮的廣泛使用而走得更遠。
BitMagic 支援序列化（協定）演進 - 如果序列化格式發生變化，舊儲存的資料仍然可以被新程式碼讀取。舊程式碼將無法讀取新的 BLOB。當序列化格式變更時，BitMagic 會變更主版本號。
BitMagic 實作所有向量的記憶體分析呼叫。可以對任何向量進行記憶體佔用採樣，因此頂層系統可以根據運行時記憶體分析來調整記憶體管理網路。典型的用例是物件的記憶體緩存，壓縮到 RAM，然後根據資源消耗和成本（需求和供應的動態平衡）將其逐出到磁碟。
是的！ BitMagic 支援 64 位，可與 32 位元位址空間（開銷較小）或完整的 64 位元位址空間一起使用。 32 位元位址空間是預設模式 2^31-1 元素應該非常適合中短程 IR 和資料科學系統。使用#define BM64ADDR 或#include "bm64.h" 可以使用64 位元位址模式。目前的 64 位元實作允許大型系統使用 2^48-1 個向量元素。
BitMagic 編譯並使用 WebAssmbly (emscripten)。最新版本包括針對該平台的多項調整。效能數字接近沒有 SIMD 的本機代碼（有時在之後）。範例編譯行如下圖所示：
emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -s WASM=1 ...
支援 WebAssembly SIMD，但預設未啟用。使用： #define BMWASMSIMDOPT啟用它。 Emscripten cmd 範例：
emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -msse4.2 -msimd128 -D BMWASMSIMDOPT -s WASM=1 -s DISABLE_EXCEPTION_CATCHING=0 -fno-rtti
目前實作使用 SSE4.2 反編譯（透過內部函數），因此-msse4.2是必要的。
BitMagic 完全支援 ARM CPU。所有版本均使用 Raspberry Pi 4 進行壓力測試。 BitMagic 簡潔容器對於可用記憶體量有限的邊緣運算嵌入式系統非常有用。
提供 Arm Neon SIMD 支援（透過 SSE2NEON 庫）。
BitMagic C++ 是一個僅包含頭檔的函式庫（易於在專案中建置和使用），並且附帶一組範例。不建議使用測試作為程式碼範例來研究庫的使用情況。測試並不能說明最佳的使用模式和模型，而且通常是故意降低效率的。
API文件和範例：http://www.bitmagic.io/apis.html
集合代數教學：http://bitmagic.io/set-algebra.html
使用案例和應用說明：http://bitmagic.io/use-case.html
有關效能優化的技術說明：http://bitmagic.io/articles.html
Doxygen：http://bitmagic.io/doxygen/html/modules.html
阿帕奇2.0。
重要的！我們要求您在任何衍生作品或我們發佈的資料中明確提及 BitMagic 專案。在您的產品/專案頁面上正確引用是使用 BitMagic 函式庫的要求。
BitMagic 函式庫非常注重程式碼品質和測試覆蓋率。
作為構建塊庫 BitMagic 需要穩定且一致才能有用。
我們不僅僅依賴單元測試，我們的測試經常使用「混沌測試」 （又稱模糊測試），其中壓力測試基於隨機生成集合和隨機操作。我們定期為發布和調試模式建立和運行測試套件，以實現 SIMD 優化的各種組合。
測試構建的所有變體都需要幾天的時間才能運行，因此不能保證工作主分支始終是完美的。對於生產，請使用 SourceForge 的穩定 github 發布分支或發行版：https://sourceforge.net/projects/bmagic/files/
GitHub master 接受補丁請求 我們的分支政策是 master 不能被認為在版本之間完全穩定。 （為了生產穩定性，請使用發布版本）
需要映射到 Python 和其他語言的幫助（BitMagic 具有 C 綁定）
BitMagic C++ 是一個僅包含頭檔的軟體包，您可能可以直接取得原始程式碼並將其放入您的專案中。所有 C++ 庫原始碼/頭檔都位於 src 目錄中。
但是，如果您想使用我們的 makefile，您需要遵循以下簡單說明：
透過在專案根目錄中執行 bmenv.sh 應用一些環境變數：
$ source ./bmenv.sh
（請使用“.”“./bmenv.sh”應用根環境變數）
使用 GNU make (gmake) 來建置安裝。
$make rebuild
或（調試版本）
$gmake DEBUG=YES rebuild
Unix 和 CygWin 上的預設編譯器是 g++。如果您想更改預設值，您可以在 makefile.in 中執行此操作（應該很容易做到）
如果您使用 cygwin 安裝，請遵循一般 Unix 建議。 MSVC - 解決方案和專案可透過 CMAKE 取得。
Xcode - 專案文件可透過 CMAKE 取得。
用於 C 和 JNI 映射的 BitMagic 庫。
BitMagic 函式庫可用於 C 語言（這是正在進行中的工作）。 C 建置的主要目標是將 BitMagic 橋接到其他程式語言中。 C build 位於子目錄「lang-maps」中。
C build為SSE和AVX創建了BitMagic build的版本，並添加了CPU識別，因此上層系統可以支援動態CPU識別和程式碼調度。
C 建置使用 C++ 編譯器，但不使用 RTTI、異常（以長跳轉模擬）和 C++ 記憶體管理，因此它是 C++ 語言中立的，沒有執行時間依賴項。演算法和行為在 C 和 C++ 之間共享。
目前發展狀況：
Python 支援正在等待中，我們需要幫助。如果您對 Python 充滿熱情並認為您可以提供協助，請聯絡：anatoliy.kuznetsov @ yahoo dot com
BitMagic 函式庫需要 CXX-11。它使用移動語義、noexept、初始化器列表、線程。下一個公共版本將使用 CXX-17（constexpr ifs 等）。
###微調與最佳化：
所有 BitMagic 微調參數均由預處理器定義（以及用於程式碼產生的目標架構特定編譯器鍵）控制。
| ＃定義 | 描述 | 寬度 |
|---|---|---|
| BMSSE2OPT | SSE2程式碼優化 | 128位 |
| BMSSE42OPT | SSE4.2程式碼最佳化加上POPCNT、BSF等 | 128位 |
| BMAVX2OPT | AVX2、POPCNT、LZCNT、BMI1、BMI2 優化 | 256位 |
| BMAVX512OPT | AVX-512，（實驗性） | 512位 |
| 寶馬ASMSIMDOPT | WebAssembly SIMD 優化（透過 SSE4.2） | 128位 |
| DBMNEOOPT | Arm Neon SIMD 優化（透過 SSE2 轉換） | 128位 |
####限制：
SIMD 最佳化定義是互斥的，不能同時擁有 BMSSE42OPT 和 BMAVX2OPT。只選一個。
BM 函式庫不支援多程式碼路徑和運行時 CPU 辨識。您必須專門為您的目標系統建置或使用預設的便攜式建置。
####範例：
BitMagic 範例和測試可以使用命令列設定透過 GCC 建置：
make BMOPTFLAGS=-DBMAVX2OPT rebuild
或者
make BMOPTFLAGS=-DBMSSE42OPT rebuild
它會自動為目標建置套用正確的編譯器 (GCC) 標誌集。
CMAKE
cd build
cmake -DBMOPTFLAGS:STRING=BMSSE42OPT ..
make
或者
cmake -DBMOPTFLAGS:STRING=BMAVX2OPT ..
BM 函式庫支援「restrict」關鍵字，當限製關鍵字有幫助時，某些編譯器（例如 Intel C++）會產生更好的程式碼（亂序載入儲存）。該選項預設為關閉，因為大多數 C++ 編譯器不支援它。要打開它，請在您的專案中#define BM_HASRESTRICT。有些編譯器使用“__restrict”關鍵字來達到此目的。要修正它，請定義 BMRESTRICT 巨集來修正關鍵字。
如果您想在「非 STL 專案」（如嵌入式系統）中使用 BM 函式庫，請定義 BM_NO_STL。
此規則僅適用於核心 bm::bvector<> 方法。輔助演算法、範例等仍將使用STL。
在 Twitter 上關注我們：https://twitter.com/bitmagicio
感謝您使用 BitMagic 函式庫！
電子郵件：[email protected]
網址：http://bitmagic.io
GitHub：https://github.com/tlk00/BitMagic
