懂AI
BitMagic

BitMagic

C++位向量压缩库用于高效数据处理和内存优化

BitMagic是一个专注于内存优化的C++库，用于信息检索和数据科学。它通过位切片变换、秩选择压缩和逻辑计算实现高效的位向量和容器压缩。该库支持快速序列化和搜索，适用于内存受限场景和大数据处理。BitMagic提供集合运算、区间操作和三值逻辑等功能，并支持WebAssembly和ARM平台，为开发者提供全面的数据处理解决方案。

BitMagic压缩位向量数据科学SIMD优化序列化Github开源项目
访问官网GitHub论文文档

BitMagic C++库

BitMagic最初创建为信息检索的集合代数工具包，但现在已发展成为一个更通用的数据科学组件库，用于内存紧凑结构和简洁数据向量算法。 BitMagic实现了压缩位向量和容器（向量），基于位切片变换、秩选择压缩和内存压缩模型上的逻辑计算等思想。

所有BitMagic简洁容器都可序列化（使用最先进的二进制插值编码进行压缩），以实现高效存储和网络传输。所有容器都可以在压缩形式下快速搜索。

BitMagic提供了一系列方法和工具，帮助您设计应用程序使用高性能计算技术，实时节省内存（从而能够在一个计算单元中容纳更多数据），改善在文件或对象存储（SQL或noSQL）中存储数据向量和模型时的存储和流量模式，从低级别（CPU缓存）到网络和存储交换优化系统带宽。

BitMagic适用于两大类场景：

  • 内存受限的应用（WebAssembly、物联网、边缘计算、桌面/工作站应用）
  • 大数据高性能计算（PB级问题），数据量巨大，计算和存储必须分布式（需要高效传输）和带宽优化。

应用和用例

BitMagic被用作以下方面的构建块：

  • 信息检索的集合代数、数据库倒排索引构建或无索引列式数据库
  • 逻辑方案模拟（FPGA）
  • 压缩集上多维二进制距离的数据科学，二进制聚类、自组织映射的构建块
  • 构建内存压缩的生物信息学模型
    • 序列比对
    • 变异和SNP集合
    • 序列读取压缩
    • k-mer分类系统
  • 在内存受限的边缘配置中可视化数据集（边缘计算、物联网、WebAssembly）
  • 图形和树分析，构建关联压缩矩阵
  • Web和应用程序日志分析，可靠性自动化系统
  • 低延迟任务调度（编排）系统

请访问我们的用例说明： http://bitmagic.io/use-case.html

优化和SIMD

BitMagic库是一个高性能库，为各种平台和构建目标实现了优化：

  • x86（平台特定可用位扫描指令）
  • x86 SIMD：SSE2、SSE4.2（POPCNT、LZCNT）、AVX2（BMI1/BMI2）、AVX-512（进行中）
  • Arm SIMD：Neon
  • WebAssembly（使用WebAsm内置函数和平台特定技巧）
  • WebAssembly SIMD

BitMagic使用数据并行向量化设计，目标不仅是提供最佳单线程性能，还要促进多核系统上的高度并行计算。

压缩算法

BitMagic使用一套压缩算法、过滤器和变换来减少内存占用、存储成本和网络数据传输。 http://bitmagic.io/design.html

  • 位向量的层次压缩
  • 位块的D-GAP（RLE）
  • 二进制插值编码（BIC）
  • Elias-Gamma编码
  • 向量的按位转置（也称为位平面编码或位切片）
  • XOR压缩过滤器
  • 基于频率的字典重映射（类似于霍夫曼编码）

请访问我们的技术说明： http://bitmagic.io/articles.html

主要特性（bm::bvector<>）

  • 压缩位向量容器
  • 迭代器（bm::bvector<>::enumerator用于将位集解码为整数
  • 位向量和整数集的集合代数运算：AND、OR、XOR、MINUS、NOT
  • 快速位向量迭代器（enumerator）用于位向量遍历，基于函子的遍历算法（类似于std::for_each）
  • 整数列表的快速导入（压缩）（C++风格的bulk_insert_iterator或使用C数组）
  • 聚合器：对位向量组进行快速向量化逻辑AND、OR、AND-MINUS操作
  • 将位向量容器序列化/休眠为压缩BLOB以实现持久性（或RAM内压缩）
  • 压缩BLOB上的集合代数操作（即时反序列化与集合代数函数）
  • 统计算法，用于有效构建相似性和距离度量，测量位向量、整数集和压缩BLOB之间的相似性
  • 秩操作：位向量上的总体计数距离。 秩选择操作常用于简洁数据结构，BitMagic实现了一个紧凑的RS索引，通过SIMD和BMI（PDEP）加速

范围和区间（bmintervals.h）

BitMagic支持将位向量重新解释为由0flanked的不重叠的1范围集合（例如：011110110）。常规集合函数提供集合交集/并集 区间操作实现区间迭代器和搜索区间边界。 范围和区间在生物信息学中有很大的用处，因为基因组数据通常被注释为坐标范围。BitMagic为编码为位向量的区间上的高效操作提供了构建块（查找区间开始/结束、检查范围是否为区间、迭代区间）

三值逻辑（bm3vl.h）

BitMagic在紧凑的两个位向量表示中实现了真/假/未知的3值逻辑（也称为三元逻辑、三值逻辑）的逻辑运算，支持按照Kleene的定义进行反转、AND、OR操作。 https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic

带压缩的序列化

BitMagic使用两阶段序列化-反序列化的概念。 重点是快速反序列化。BitMagic实现了快速向量范围反序列化和压缩BLOB的聚集反序列化的API。BitMagic的终极功能是能够处理压缩数据。

第一阶段：简洁内存

这是主要的RAM操作状态，向量以内存紧凑形式保存。 简洁不是压缩。可以访问容器中的随机元素，解码块，迭代向量，进行更新，运行搜索算法。第一阶段提供透明使用，向量看起来很像STL。简洁是内存紧凑的，但不是完全压缩的。

第二阶段：压缩

BitMagic可以序列化所有容器和向量，通过基于块的启发式和编解码器进行额外压缩。主要的编码技术是：二进制插值编码（BIC）和Elias Gamma。

BitMagic容器被称为"稀疏"向量，但实际上其压缩方案对稀疏和密集数据都有效。

BitMagic在Gov2基准倒排列表集和多个专有数据集上进行了测试。 http://bitmagic.io/bm5-cmpr.html

解压缩

反序列化总是回到第一阶段，所以数据不会完全解码，而是在RAM中保持简洁。我们的目标是既减少应用程序内存占用，又提高反序列化延迟。解压缩算法支持任意范围的反序列化，甚至支持元素的聚集反序列化。

简洁向量

BitMagic支持基于位转置变换的简洁（内存紧凑）向量，也称为位平面压缩（BPC）（又称位切片）加上秩选择压缩。 BitMagic简洁向量有些误导性地标记为"稀疏"，但它们对密集向量也适用。

位转置解决了两个目的：释放未使用的位平面，并将规律性和熵隔离到单独的（稀疏）位向量中。对位平面的压缩既提供了卓越的内存性能，又实现了快速搜索。设计目标之一是使用快速向量化逻辑操作在内存压缩形式下对简洁向量进行无索引搜索。

BitMagic简洁向量可在内存压缩形式下进行无索引搜索。速度很快！

简洁的位转置实现对整数向量（有符号或无符号）和字符串向量都有效。它与其他简洁方案（如前缀树）相媲美。简洁向量可以是排序的，也可以是未排序的。 这里的想法类似于Apache Arrow-Parquet，但通过位平面压缩和广泛使用加速的秩选择压缩，将其推进了一步。

  • 比特转置表示法为数值向量提供了最佳的内存占用,适用于有限或可变位数的数据。如果数据只需要27位,简洁向量就只使用27位,而不是最接近的32位自然类型。它是自适应且完全自动的。

  • 如果字符串向量在特定位置只需要几位来表示一个字符(如DNA字符串、化学化合物的SMILES表示法等),BitMagic可以进行透明的重映射,因此DNA字符串向量只需要2-3位(用于ATGCN字母表),重映射会分析频率,类似于霍夫曼编码。

  • 秩选择方法允许合并所有NULL值以节省内存

  • 为了更深层次的压缩,BitMagic还实现了XOR过滤器,可以找出位平面之间可能的相关性以减少熵 http://bitmagic.io/bm-xor.html

主要特性

  • 使用位切片和位切片单独压缩的原生整数类型稀疏向量,支持NULL值(未赋值),用于构建内存列式结构。位转置稀疏向量可用于天文、分子生物学或其他数据的即时压缩,高效存储图的关联等。

  • 排序和未排序简洁向量(整数或字符串向量)的搜索算法

  • 稀疏向量算法:动态范围裁剪、搜索、群论映像(重映射)

  • 所有容器都可序列化并支持压缩(XOR编码、二进制插值编码、Elias gamma编码)

  • 支持简洁不可变向量。向量可以设为只读,稀疏内存块可以重新排列以碎片整理堆、节省内存并促进更好的CPU缓存重用

序列化和版本控制

BitMagic支持序列化(协议)演进 - 如果序列化格式发生变化,旧的保存数据仍然可以被新代码读取。旧代码将无法读取新的BLOB。当序列化格式发生变化时,BitMagic会更改主版本号。

内存分析/监控

BitMagic为所有向量实现了内存分析调用。任何向量都可以对内存占用进行采样,因此顶层系统可以根据运行时内存分析来调整内存管理。典型用例是对象的内存缓存,先压缩到RAM,然后根据资源消耗和成本(需求和供给的动态平衡)驱逐到磁盘。

64位与32位

是的! BitMagic支持64位,可以用于32位地址空间(开销较小)或完整的64位地址空间。32位地址空间是默认模式,2^31-1个元素应该适合短到中等范围的IR和数据科学系统。64位地址模式可通过#define BM64ADDR或#include "bm64.h"使用。当前的64位实现允许大规模系统使用2^48-1个向量元素。

WebAssembly和WebAssembly SIMD

BitMagic可以编译并与WebAssembly(emscripten)一起工作。最新版本包含了多个针对该平台的优化。性能数据接近不使用SIMD的原生代码(有时更快)。示例编译命令如下:

emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -s WASM=1 ...

支持WebAssembly SIMD,但默认不开启。 使用: #define BMWASMSIMDOPT 来启用它。Emscripten命令示例:

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。

Arm

BitMagic完全支持ARM CPU。所有发布版本都在Raspberry Pi 4上进行压力测试。BitMagic实现了一些专门针对ARM的算法优化和改进(如使用LZCNT指令)。BitMagic的简洁容器在内存有限的嵌入式系统上进行边缘计算时非常有用。

支持Arm Neon SIMD(通过SSE2NEON库)。

C库接口:

  • BitMagic库提供C库封装,可以构建为"纯C"库。为了重新分发,它不需要C++运行时,因为它在编译时不使用STL、C++内存分配(operator new)或异常。我们的目标是最终为其他数据科学语言(Python)和企业级开发语言(Java、Scala)通过JNI提供桥接。

正在开发的功能:

  • 压缩二进制关系矩阵和邻接矩阵以及矩阵运算,用于实体关系加速、图操作、社交分析、物化RDBMS连接等

如何开始使用BitMagic?

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

许可证:

Apache 2.0。

重要! 我们要求您在任何衍生作品或已发布材料中明确提及BitMagic项目。在您的产品/项目页面上适当引用是使用BitMagic库的要求。

质量保证:

BitMagic库非常重视代码质量和测试覆盖率。作为构建块库,BitMagic需要稳定和符合标准才能有用。

我们不仅仅依赖单元测试,我们的测试经常使用"混沌测试"(又称模糊测试),其中压力测试基于随机生成的集合和随机操作。我们定期为各种SIMD优化组合构建和运行Release和Debug模式的测试套件。

所有测试构建变体需要数天时间才能运行完成,因此工作主分支并不保证始终完美。对于生产环境,请使用稳定的github发布分支或来自SourceForge的发行版: https://sourceforge.net/projects/bmagic/files/

如果您想为BitMagic库做出贡献或支持:

  1. GitHub主分支接受补丁请求 我们的分支策略是,主分支在发布之间不能被认为是完全稳定的。 (为了生产稳定性,请使用发布版本)

  2. 需要帮助将其映射到Python和其他语言(BitMagic有C绑定)

如何构建BitMagic C++库:

BitMagic C++是一个仅头文件的软件包,您可能只需要直接将源代码放入您的项目中。所有C++库源代码/头文件都在src目录中。

但是,如果您想使用我们的makefiles,您需要遵循以下简单说明:

Unix:
  1. 传统(原地构建)

通过在项目根目录运行bmenv.sh应用一些环境变量:

$ source ./bmenv.sh

(请使用"." "./bmenv.sh"来应用根环境变量)

使用GNU make (gmake)构建安装。

$make rebuild

或(DEBUG版本)

$gmake DEBUG=YES rebuild

Unix和CygWin上的默认编译器是g++。 如果您想更改默认值,可以在makefile.in中进行更改 (应该很容易做到)

  1. 基于CMake的构建 项目现在带有一组用于cmake的makefiles,您可以直接构建它或为任何cmake支持的环境生成项目文件。
Windows:

如果您使用cygwin安装,请遵循一般Unix建议。 MSVC - 可通过CMAKE获得解决方案和项目。

MacOS

Xcode - 可通过CMAKE获得项目文件。

BitMagic库的C和JNI映射。

BitMagic库可用于C语言(这是正在进行的工作)。 C构建的主要目标是将BitMagic桥接到其他编程语言。 C构建在"lang-maps"子目录中。

C构建为SSE和AVX创建BitMagic构建版本,并添加CPU识别, 因此上层系统可以支持动态CPU识别和代码分发。 C构建使用C++编译器，但不使用RTTI、异常(通过长跳转模拟)和C++内存管理，因此它是C++语言中立的，没有运行时依赖。C和C++之间共享算法和行为。

当前开发状态:

  • 位向量功能可通过C接口使用

Python支持

Python支持正在进行中，我们需要在这方面的帮助。 如果你对Python充满热情并认为你可以提供帮助，请联系: anatoliy.kuznetsov @ yahoo dot com

现代C++(C++17)

BitMagic库需要C++11。它使用了移动语义、noexcept、初始化列表、线程。 下一个公开版本将使用C++17(constexpr if等)。

精细调整和优化:

所有BitMagic的精细调整参数都由预处理器定义(以及目标架构特定的编译器代码生成键)控制。

#define描述宽度
BMSSE2OPTSSE2代码优化128位
BMSSE42OPTSSE4.2代码优化加上POPCNT、BSF等128位
BMAVX2OPTAVX2、POPCNT、LZCNT、BMI1、BMI2优化256位
BMAVX512OPTAVX-512(实验性)512位
BMWASMSIMDOPTWebAssembly SIMD优化(通过SSE4.2)128位
DBMNEONOPTArm Neon SIMD优化(通过SSE2转换)128位

限制:

SIMD优化定义是互斥的，你不能同时使用BMSSE42OPT和BMAVX2OPT。 只能选择一个。

BM库不支持多代码路径和运行时CPU识别。 你必须专门为你的目标系统构建或使用默认的可移植构建。

示例:

可以使用GCC通过命令行设置构建BitMagic示例和测试:

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++)在使用restrict关键字时可以生成更好的代码(乱序加载存储)。默认情况下此选项是关闭的，因为大多数C++编译器不支持它。要打开它，请在你的项目中#define BM_HASRESTRICT。一些编译器使用"__restrict"关键字。要纠正这一点，请将BMRESTRICT宏定义为正确的关键字。

如果你想在"无STL项目"(如嵌入式系统)中使用BM库，请定义BM_NO_STL。

这条规则只适用于核心bm::bvector<>方法。 辅助算法、示例等仍会使用STL。

在Twitter上关注我们: https://twitter.com/bitmagicio

感谢使用BitMagic库!

电子邮件: info@bitmagic.io

网站: http://bitmagic.io

GitHub: https://github.com/tlk00/BitMagic

编辑推荐精选

Trae

Trae

字节跳动发布的AI编程神器IDE

Trae是一种自适应的集成开发环境（IDE），通过自动化和多元协作改变开发流程。利用Trae，团队能够更快速、精确地编写和部署代码，从而提高编程效率和项目交付速度。Trae具备上下文感知和代码自动完成功能，是提升开发效率的理想工具。

AI工具TraeAI IDE协作生产力转型热门
问小白

问小白

全能AI智能助手，随时解答生活与工作的多样问题

问小白，由元石科技研发的AI智能助手，快速准确地解答各种生活和工作问题，包括但不限于搜索、规划和社交互动，帮助用户在日常生活中提高效率，轻松管理个人事务。

热门AI助手AI对话AI工具聊天机器人
Transly

Transly

实时语音翻译/同声传译工具

Transly是一个多场景的AI大语言模型驱动的同声传译、专业翻译助手，它拥有超精准的音频识别翻译能力，几乎零延迟的使用体验和支持多国语言可以让你带它走遍全球，无论你是留学生、商务人士、韩剧美剧爱好者，还是出国游玩、多国会议、跨国追星等等，都可以满足你所有需要同传的场景需求，线上线下通用，扫除语言障碍，让全世界的语言交流不再有国界。

讯飞智文

讯飞智文

一键生成PPT和Word，让学习生活更轻松

讯飞智文是一个利用 AI 技术的项目，能够帮助用户生成 PPT 以及各类文档。无论是商业领域的市场分析报告、年度目标制定，还是学生群体的职业生涯规划、实习避坑指南，亦或是活动策划、旅游攻略等内容，它都能提供支持，帮助用户精准表达，轻松呈现各种信息。

AI办公办公工具AI工具讯飞智文AI在线生成PPTAI撰写助手多语种文档生成AI自动配图热门
讯飞星火

讯飞星火

深度推理能力全新升级，全面对标OpenAI o1

科大讯飞的星火大模型，支持语言理解、知识问答和文本创作等多功能，适用于多种文件和业务场景，提升办公和日常生活的效率。讯飞星火是一个提供丰富智能服务的平台，涵盖科技资讯、图像创作、写作辅助、编程解答、科研文献解读等功能，能为不同需求的用户提供便捷高效的帮助，助力用户轻松获取信息、解决问题，满足多样化使用场景。

热门AI开发模型训练AI工具讯飞星火大模型智能问答内容创作多语种支持智慧生活
Spark-TTS

Spark-TTS

一种基于大语言模型的高效单流解耦语音令牌文本到语音合成模型

Spark-TTS 是一个基于 PyTorch 的开源文本到语音合成项目，由多个知名机构联合参与。该项目提供了高效的 LLM（大语言模型）驱动的语音合成方案，支持语音克隆和语音创建功能，可通过命令行界面（CLI）和 Web UI 两种方式使用。用户可以根据需求调整语音的性别、音高、速度等参数，生成高质量的语音。该项目适用于多种场景，如有声读物制作、智能语音助手开发等。

咔片PPT

咔片PPT

AI助力，做PPT更简单！

咔片是一款轻量化在线演示设计工具，借助 AI 技术，实现从内容生成到智能设计的一站式 PPT 制作服务。支持多种文档格式导入生成 PPT，提供海量模板、智能美化、素材替换等功能，适用于销售、教师、学生等各类人群，能高效制作出高品质 PPT，满足不同场景演示需求。

讯飞绘文

讯飞绘文

选题、配图、成文，一站式创作，让内容运营更高效

讯飞绘文，一个AI集成平台，支持写作、选题、配图、排版和发布。高效生成适用于各类媒体的定制内容，加速品牌传播，提升内容营销效果。

热门AI辅助写作AI工具讯飞绘文内容运营AI创作个性化文章多平台分发AI助手
材料星

材料星

专业的AI公文写作平台，公文写作神器

AI 材料星，专业的 AI 公文写作辅助平台，为体制内工作人员提供高效的公文写作解决方案。拥有海量公文文库、9 大核心 AI 功能，支持 30 + 文稿类型生成，助力快速完成领导讲话、工作总结、述职报告等材料，提升办公效率，是体制打工人的得力写作神器。

openai-agents-python

openai-agents-python

OpenAI Agents SDK，助力开发者便捷使用 OpenAI 相关功能。

openai-agents-python 是 OpenAI 推出的一款强大 Python SDK，它为开发者提供了与 OpenAI 模型交互的高效工具，支持工具调用、结果处理、追踪等功能，涵盖多种应用场景，如研究助手、财务研究等，能显著提升开发效率，让开发者更轻松地利用 OpenAI 的技术优势。

下拉加载更多