介绍
(20120511)位图就是通过将数组下标与应用中的一些值关联,数组中该下标所指定的位置上的元素可以用来标识应用中值的情况(是否存在 or 数目 or 。。。)。
位图中的值可以是计数、标识(如例1)。
可以运用在快速查找、排重、删除?、排序、压缩数据等。
实现
不同语言版本
相关应用
压缩
排序
例:有1000,0000个数,如果想对这些数排序,并且想尽量少用内存,该如何设计数据结构和排序算法?
方案1 :采用32Bitmap(即容量为1000,1000/32,每个元素为32bit)位图中元素为整型32bit(下标为0-31),位图中元素可以存储相邻32个数是否存在的信息。例如89256 mod 32=2789…8,这样我们应该置a[2789]中32位字符串的第8位(从低位数起)为1。89257 mod 32=2789…9,设置a[2789]中元素的第9位为1。在将1000,0000个数都存入位图后,然后进行排序,遍历位图,将元素通过 ”位操作“还原为原值,输出。
注:来自http://blog.csdn.net/QIBAOYUAN/article/details/5914662 ,该文利用位图实现了压缩和排序,压缩体现在位图中每个元素为32位,将某个数与32取模,将取模后值对应到32位中的某位上设置为1,这样,32位就能保存相邻的32个数是否存在的信息。这样位图的大小就可以缩小到10000000/32.
搜索
例1:在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数。
方案1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32 * 2 bit=1 GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。
例2:在Map3搜索例子中,通过将url的个数存储在bitmap中,可以通过歌曲id来快速找到歌曲url个数。
http://tech.techweb.com.cn/thread-222923-1-1.html
例3:给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
最简单的方法就是将这40亿个整数载入到数组中,然后遍历,看给定的数是否在这个数组中。但这是一个非常粗糙的方法,没有考虑存储空间和搜索效率问题。
可以考虑快速排序+二分查找,但是内存占用还是很大,并且如果40亿数据还有增加,涉及重排序。能不能有一种结构不用排序,占用内存比较少,面对增量数据也能从容应对呢?——bitmap
构建一个bitmap,元素为1bit(0表示无,1表示有),遍历40亿数据,设置bitmap里相应位置上元素值为1,搜索时只要根据目标值去bitmap里查找该位置上元素即可。
设计搜索剪枝时,需要保存已经搜索过的历史信息,有些情况下,可以使用位图减小历史信息数据所占空间。
扩展
Bloom filter
参考阅读
1. http://dongxicheng.org/structure/bitmap/
C++的STL中有bitmap类/
分享到:
相关推荐
BMP位图数据结构BMP位图数据结构BMP位图数据结构BMP位图数据结构BMP位图数据结构BMP位图数据结构BMP位图数据结构BMP位图数据结构BMP位图数据结构BMP位图数据结构BMP位图数据结构BMP位图数据结构BMP位图数据结构BMP...
主要介绍了数据结构之位图详解,本文讲解了位图的基本知识、位图的实现方法、位图的应用等内容,需要的朋友可以参考下
BMP位图数据结构BMP位图数据结构BMP位图数据结构
BMP位图数据结构 BMP文件格式,又称为Bitmap(位图)或是DIB(Device-Independent Device,设备无关位图),是Windows系统中广泛使用的图像文件格式
Linux 内核数据结构:位图(Bitmap).docx
位图的数据结构全文共15页,当前为第1页。位图文件的数据结构 一、文件的组成 Bmp 文件由文件头、位图信息头、调色板、数据区等四个部分组成(真彩位图没有调色板,由三个部分组成),结构如下(在以下所有表格中,...
Java图数据结构
BMP文件头数据结构含有BMP文件的类型、文件大小和位图起始位置等信息。 其结构定义如下: typedef struct tagBITMAPFILEHEADER { WORDbf Type; // 位图文件的类型,必须为BMP(0-1字节) DWORD bfSize; /...
BMP文件头数据结构含有BMP文件的类型、文件大小和位图起始位置等信息。 其结构定义如下: typedef struct tagBITMAPFILEHEADER { WORD bfType; // 位图文件的类型,必须为BM DWORD bfSize; // 位图文件的大小,以...
按文件读取BMP位图,注意仅仅对24位位图有效。
Creating a bitmap object from a BMP file从位图文件中创建位图对象(6KB)
数据结构之线性结构(一,表结构) 作者:冲出宇宙 时间:2006-10-24 修改:2006-11-3 转载请注明作者。 作者主要参考了www.answers.com 上面的资料(因为wikipedia上不去)和部分较新学术论文(一般来自于acm, IEEE...
介绍了位图的数据结构,bitmap file format.pdf
图标文件的数据结构之研究 这几天因为编写一个图标编辑程序,研究了一下图标的数据结构, 颇有一些心得,写出 来与各位兄弟共享。(笔者注:以下所说的图标均为调色板模式的图 标,真彩图标会特别注 明) 一、从图标...
这是一个位图显示及从位图中将数据提取出的程序。出于simon haykin著的《神经网络与机器学习》的双月结构实验程序二维随机变量从位图中提取出来。可用于感知机的分类实验。
数据结构课程设计-基于Huffman编码的文件压缩与解压缩20分-内容与要求.docx 西南交通大学 报告仅供参考,请独立完成作业
BMP位图结构分析源码例程程序置入汇编代码并调用API函数演示了位图数据结构组成。 点评:位图结构易语言演示源码仅供学习参考。
。
。