Bitmap 算法

简介: 位图算法,内存中连续的二进制位bit,用于对大量整型数据做去重和查询。 举个例子,给定一块长度是10bit的内存空间,依次插入4,3,2,1,怎么存储? 1. 给定长度是10的bitmap,每一个bit位分别对应着从0到9的10个整型数。

位图算法,内存中连续的二进制位bit,用于对大量整型数据做去重和查询。

举个例子,给定一块长度是10bit的内存空间,依次插入4,3,2,1,怎么存储?

1. 给定长度是10的bitmap,每一个bit位分别对应着从0到9的10个整型数。此时bitmap的所有位都是0。

2. 把整型数4存入bitmap,对应存储的位置就是下标为4的位置,将此bit置为1。

3. 把整型数2存入bitmap,对应存储的位置就是下标为2的位置,将此bit置为1。

4. 把整型数1存入bitmap,对应存储的位置就是下标为1的位置,将此bit置为1。

5. 把整型数3存入bitmap,对应存储的位置就是下标为3的位置,将此bit置为1。

Bitmap不仅方便查询,还可以去除掉重复的整型数。

使用场景:

开发一个用户画像系统,实现用户信息的标签化。用户标签包含用户的社会属性,生活习惯,消费行为。

通过用户标签,实现多样的用户群体统计,统计用户的男女比例,统计喜欢旅游的用户数量等。

1. 建立用户名和用户ID的映射:  1->me   2->you  3->he

2.让每一个标签存储包含此标签的所有用户ID,每一个标签都是一个独立的Bitmap。

男[1,2]   女[3] 爱旅游[2]  程序员[1,2]

3. 这样,实现用户的去重和查询统计,就变得一目了然:

Bitmap在做交集和并集运算的时候也有极大的便利。位运算的高性能。

男性的程序员  110&110=110

不能做非运算,并不是除了1,2的其他都是女性,其实只有3是女性。除非提供一个全量的Bitmap,做异或即可。

一个很长的Bitmap里使用率低的话很浪费空间。

谷歌所实现的EWAHCompressedBitmap中,对存储空间做了优化:

<dependency>
  <groupId>com.googlecode.javaewah</groupId>
  <artifactId>JavaEWAH</artifactId>
  <version>1.1.0</version>
</dependency>

  

 

目录
相关文章
|
存储 算法 程序员
bitmap算法的PHP实现,快速去重排序,数据压缩储存
因为电路的逻辑只有0和1两个状态,这里的0和1并不是数字的0和1,0和1是表示两种不同的状态,0表示低电平,1表示高电平。因为计算机是由无数个逻辑电路组成的,只能根据0和1的无限位数和组合来表达信息。 电脑只认识0和1这两个数字,所有的数据在电脑中都是以0和1组成的编码存储的,这样的编码叫做二进制。一个0或一个1就叫做一个位 最初的计算机性能和存储容量都比较差,所以普遍采用4位BCD编码(这个编码出现比计算机还早,最早是用在打孔卡上的)。
320 0
|
存储 SQL 算法
漫画:Bitmap算法 整合版
为满足用户标签的统计需求,小灰利用Mysql设计了如下的表结构,每一个维度的标签都对应着Mysql表的一列。
143 0
漫画:Bitmap算法 整合版
|
算法 大数据 索引
大数据处理时的一种BitMap小算法
一种大数据外部排序(内存无法加载所有排序元素)、去除重复元素、快速找到随机被删除元素的BitMap小算法,核心思想即通过将一个数作为下标(index)来索引一个bit表示一个数是否存在,排序时的时间复杂度为O(N),需要的额外空间的复杂度O(N/8)...
1077 0
|
算法 人工智能 搜索推荐
经典算法题每日演练——第十一题 Bitmap算法
原文:经典算法题每日演练——第十一题 Bitmap算法      在所有具有性能优化的数据结构中,我想大家使用最多的就是hash表,是的,在具有定位查找上具有O(1)的常量时间,多么的简洁优美, 但是在特定的场合下: ①:对10亿个不重复的整数进行排序。
824 0
|
17天前
|
机器学习/深度学习 人工智能 算法
基于DCT和扩频的音频水印嵌入提取算法matlab仿真
本文介绍了结合DCT和扩频技术的音频水印算法,用于在不降低音质的情况下嵌入版权信息。在matlab2022a中实现,算法利用DCT进行频域处理,通过扩频增强水印的隐蔽性和抗攻击性。核心程序展示了水印的嵌入与提取过程,包括DCT变换、水印扩频及反变换步骤。该方法有效且专业,未来研究将侧重于提高实用性和安全性。
|
4天前
|
存储 算法
m基于LDPC编译码的matlab误码率仿真,对比SP,MS,NMS以及OMS四种译码算法
MATLAB 2022a仿真实现了LDPC译码算法比较,包括Sum-Product (SP),Min-Sum (MS),Normalized Min-Sum (NMS)和Offset Min-Sum (OMS)。四种算法在不同通信场景有各自优势:SP最准确但计算复杂度高;MS计算复杂度最低但性能略逊;NMS通过归一化提升低SNR性能;OMS引入偏置优化高SNR表现。适用于资源有限或高性能需求的场景。提供的MATLAB代码用于仿真并绘制不同SNR下的误码率曲线。
145 3
|
7天前
|
算法 数据安全/隐私保护 计算机视觉
基于DCT变换的彩色图像双重水印嵌入和提取算法matlab仿真
**算法摘要:** - 图形展示:展示灰度与彩色图像水印应用,主辅水印嵌入。 - 软件环境:MATLAB 2022a。 - 算法原理:双重水印,转换至YCbCr/YIQ,仅影响亮度;图像分割为M×N块,DCT变换后嵌入水印。 - 流程概览:两步水印嵌入,每步对应不同图示表示。 - 核心代码未提供。
|
8天前
|
机器学习/深度学习 算法 数据可视化
Matlab决策树、模糊C-均值聚类算法分析高校教师职称学历评分可视化
Matlab决策树、模糊C-均值聚类算法分析高校教师职称学历评分可视化
|
8天前
|
算法 TensorFlow 算法框架/工具
基于直方图的图像阈值计算和分割算法FPGA实现,包含tb测试文件和MATLAB辅助验证
这是一个关于图像处理的算法实现摘要,主要包括四部分:展示了四张算法运行的效果图;提到了使用的软件版本为VIVADO 2019.2和matlab 2022a;介绍了算法理论,即基于直方图的图像阈值分割,通过灰度直方图分布选取阈值来区分图像区域;并提供了部分Verilog代码,该代码读取图像数据,进行处理,并输出结果到&quot;result.txt&quot;以供MATLAB显示图像分割效果。