大数据处理之bitmap

发布时间：2020-12-14 03:32:01 所属栏目：大数据来源：网络整理

导读：?? ??? bitmap是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节

?? ??? bitmap是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

?????适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下

基本原理及要点：使用bit数组来表示某些元素是否存在，比如8位电话号码

扩展：bloom filter可以看做是对bit-map的扩展

问题实例：

1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。

8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。

2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map。

注：对于上面两题用前缀树（Trie）来做也可行效率应该更高

例如第一题：

1. 将每一整数看成8字符串，因此Trie树的高度最多为8+1.

2. 因为数字只有0-9十个数字，所以每一个节点最多10个分支。

因此该Trie树占用的内存非常小。

对于每一8位字符串进行Trie搜索，如果不存在则创建，存在则统计该字符串出现的次数

遍历所有整数后，我们就得到了所有整数的Trie树统计，每一节点都包含所有出现整数的统计次数。

最后遍历Trie树找出出现的整数即可。

下面是一个简单的例子：

// bigdata_bitmap.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

/************************************************************************/
/*?
bitmap 实现：
bitmap 一般用于内存不足，对输入数据进行去重
输入一个数组{2,4,5,6,7,8,33,30,54,43,32,56,67,100}
用bitmap 去掉重复的数字
*/
/************************************************************************/

char* g_bitmap = NULL;

int g_size = 0;
int g_base = 0;

int bitmap_init(int maxNum,int start = 0)
{
g_size = maxNum/8+1;
g_base = start;
g_bitmap = new char[g_size];
if (g_bitmap == NULL)
{
return 0;
}
memset(g_bitmap,0x0,g_size);
return 1;
}

int bitmap_set(int index)
{
int slot = (index-g_base)/8; //位于哪一个字节
int inside_index = (index - g_base)%8; //字节内便宜

if (slot > g_size)
{
return 0;
}

unsigned int x = 0x1 << inside_index;

g_bitmap[slot] |= x; //特定位置1
return 1;
}

int bitmap_get(int index) //获得特定位的值0,1
{
int slot = (index-g_base)/8; //位于哪一个字节
int inside_index = (index - g_base)%8; //字节内便宜

if (slot > g_size)
{
return -1; //wrong
}
unsigned int x = 0x1 << inside_index;
return (x & g_bitmap[slot]);
}

void main()
{
int data[] = {2,100};
int length = 21;

cout<<"raw data"<<endl;
for (int i = 0 ;i < length ;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
bitmap_init(100);
for (int i = 0 ;i < length ;i++)
{
if(0 == bitmap_set(data[i]))
{
cout<<"wrongn";
return;
}
}
cout<<"bitmap processedn";
for (int i = 0 ; i <= 100;i++)
{
int ret = bitmap_get(i);
if (ret == -1)
{
cout<<"wrongn";
return;
}
else if (ret)
{
cout<<i<<" ";
}
}
cout<<endl;
}

执行结果：

raw data 2 ? ? ? 4 ? ? ? 4 ? ? ? 5 ? ? ? 6 ? ? ? 7 ? ? ? 8 ? ? ? 7 ? ? ? 33 ? ? ?30 33 ? ? ?33 ? ? ?54 ? ? ?43 ? ? ?32 ? ? ?43 ? ? ?54 ? ? ?56 ? ? ?5 ? ? ? 67 100 bitmap processed 2 ? ? ? 4 ? ? ? 5 ? ? ? 6 ? ? ? 7 ? ? ? 8 ? ? ? 30 ? ? ?32 ? ? ?33 ? ? ?43 54 ? ? ?56 ? ? ?67 ? ? ?100 请按任意键继续. . .

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!