自学内容网 自学内容网

【高阶数据结构】布隆过滤器+海量数据处理

一.什么是布隆过滤器?

  1. 有一些场景下面,有大量数据需要判断是否存在,而这些数据不是整形,那么位图就不能使用了,使用红黑树/哈希表等内存空间可能不够。这些场景就需要布隆过滤器来解决。
  2. 布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构,特点是高效地插入和查询,可以用来告诉你"某样东西一定不存在或者可能存在",它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。
  3. 布隆过滤器的思路就是把key先映射转成哈希整型值,再映一个位,如果只映射一个位的话,冲突率会比较多,所以可以通过多个哈希函数映射多个位,降低冲突率。
  4. 布隆过滤器这里跟哈希表不一样,它无法解决哈希冲突的,因为它压根就不存储这个值,只标记映射的位。它的思路是尽可能降低哈希冲突。判断一个值key在是不准确的,判断一个值key不在是准确的。

在这里插入图片描述
上图:有0就代表不在,否则代表在(判断在是不准确的,判断不在是准确的)

二.布隆过滤器器误判率推导

在这里插入图片描述
布隆过滤器(Bloom Filter)- 原理、实现和推导

三.布隆过滤器代码实现

namespace xzy
{
//N是需要多少比特位
template<size_t N>
class bitset
{
public:
bitset()
{
_bs.resize(N / 32 + 1);
}

//x映射的位标记为1
void set(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;

_bs[i] |= (1 << j);
}

//x映射的位标记为0
void reset(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;

_bs[i] &= ~(1 << j);
}

//x映射的位是1返回真
//x映射的位是0返回假
bool test(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;

return _bs[i] & (1 << j);
}

private:
vector<int> _bs;
};
}

struct HashFuncBKDR
{
// @detail 本算法由于在Brian Kernighan与Dennis Ritchie的《The CProgramming Language》
// 一书被展示而得名,是一种简单快捷的hash算法,也是Java目前采用的字符串的Hash算法累乘因子为31。
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash *= 31;
hash += ch;
}
return hash;
}
};

struct HashFuncAP
{
// 由Arash Partow发明的一种hash算法。  
size_t operator()(const string& s)
{
size_t hash = 0;
for (size_t i = 0; i < s.size(); i++)
{
if ((i & 1) == 0) // 偶数位字符
{
hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
}
else              // 奇数位字符
{
hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));
}
}

return hash;
}
};

struct HashFuncDJB
{
// 由Daniel J. Bernstein教授发明的一种hash算法。 
size_t operator()(const string& s)
{
size_t hash = 5381;
for (auto ch : s)
{
hash = hash * 33 ^ ch;
}

return hash;
}
};

//K:插入数据的类型
//N:插入数据的个数
//M:布隆过滤器的长度
//X:M/N
//Hash1、Hash2、Hash3:哈希函数
//已知哈希函数的个数为M/N*In2时:误判率最低
//给出M/N等于5时:哈希函数个数等于3,
template<size_t N,
 size_t X = 5,
 class K = string,
 class Hash1 = HashFuncBKDR,
 class Hash2 = HashFuncAP,
 class Hash3 = HashFuncDJB>
class BloomFilter
{
public:
void Set(const K& key)
{
size_t hash1 = Hash1()(key) % M;
size_t hash2 = Hash2()(key) % M;
size_t hash3 = Hash3()(key) % M;

_bs.set(hash1);
_bs.set(hash2);
_bs.set(hash3);
}

bool Test(const K& key)
{
size_t hash1 = Hash1()(key) % M;
if (_bs.test(hash1) == false)
return false;

size_t hash2 = Hash2()(key) % M;
if (_bs.test(hash2) == false)
return false;

size_t hash3 = Hash3()(key) % M;
if (_bs.test(hash3) == false)
return false;

return true; //可能存在误判
}

//获取公式计算出的误判率
double getFalseProbability()
{
double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);

return p;
}

private:
static const int M = X * N;
//我们实现位图是用vector,也就是堆上开的空间
xzy::bitset<M> _bs;

//std::bitset<M> _bs;
//vs下std的位图是开的静态数组,M太大会存在崩溃的问题
//解决方案就是bitset对象整体new一下,空间就开到堆上了
//std::bitset<M>* _bs = new std::bitset<M>;
};

void TestBloomFilter1()
{
string strs[] = { "百度","字节","腾讯" };
BloomFilter<10> bf;

for (auto& s : strs)
{
bf.Set(s);
}

for (auto& s : strs)
{
cout << bf.Test(s) << endl;
}

for (auto& s : strs)
{
cout << bf.Test(s + 'a') << endl;
}
cout << bf.Test("摆渡") << endl;
cout << bf.Test("百渡") << endl;
}

void TestBloomFilter2()
{
srand(time(0));
const size_t N = 1000000;
BloomFilter<N> bf;
//BloomFilter<N, 3> bf;
//BloomFilter<N, 10> bf;

vector<string> v1;
//string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
string url = "猪八戒";

for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + to_string(i));
}
for (auto& str : v1)
{
bf.Set(str);
}

// 相似字符串集:前缀一样,但是后缀不一样
v1.clear();
for (size_t i = 0; i < N; ++i)
{
string urlstr = url;
urlstr += to_string(9999999 + i);
v1.push_back(urlstr);
}

size_t n2 = 0;
for (auto& str : v1)
{
if (bf.Test(str)) //误判:不在的值判断为在
{
++n2;
}
}
cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

// 不相似字符串集:前缀后缀都不一样
v1.clear();
for (size_t i = 0; i < N; ++i)
{
//string url = "zhihu.com";
string url = "孙悟空";
url += to_string(i + rand());
v1.push_back(url);
}

size_t n3 = 0;
for (auto& str : v1)
{
if (bf.Test(str)) //误判:不在的值判断为在
{
++n3;
}
}
cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;

cout << "公式计算出的误判率:" << bf.getFalseProbability() << endl;
}

int main()
{
TestBloomFilter1();
TestBloomFilter2();

return 0;
}

四.布隆过滤器删除问题

  1. 布隆过滤器默认是不支持删除的,因为比如"猪八戒"和"孙悟空"都映射在布隆过滤器中,他们映射的位有一个位是共同映射的(冲突的),如果我们把孙悟空删掉,那么再去查找"猪八戒"会查找不到,因为那么"猪八戒"间接被删掉了。
  2. 解决方案:可以考虑计数标记的方式,一个位置用多个位标记,记录映射这个位的计数值,删除时,仅仅减减计数,那么就可以某种程度支持删除。但是这个方案也有缺陷,如果一个值不在布隆过滤器中,被误判为在,那么我们去删除,减减了映射位的计数,那么会影响已存在的值,也就是说,一个确定存在的值,可能会变成不存在,这里就很坑。当然也有人提出,我们可以考虑计数方式支持删除,但是定期重建一下布隆过滤器,这样也是一种思路。

在这里插入图片描述

五.布隆过滤器的应用

优点:效率高,节省空间,相比位图,可以适用于各种类型的标记过滤。
缺点:存在误判(在是不准确的,不在是准确的),不好支持删除。

布隆过滤器的应用:

  1. 爬虫系统中URL去重:在爬虫系统中,为了避免重复爬取相同的URL,可以使用布隆过滤器来进行URL去重。爬取到的URL可以通过布隆过滤器进行判断,已经存在的URL则可以直接忽略(可能不在的URL被误判为在,也就是说少爬了一些URL,不过影响不大),避免重复的网络请求和数据处理。
  2. 垃圾邮件过滤:在垃圾邮件过滤系统中,布隆过滤器可以用来判断邮件是否是垃圾邮件。系统可以将已知的垃圾邮件的特征信息存储在布隆过滤器中,当新的邮件到达时,可以通过布隆过滤器快速判断是否为垃圾邮件,从而提高过滤的效率。
  3. 预防缓存穿透:在分布式缓存系统中,布隆过滤器可以用来解决缓存穿透的问题。数据库上层设置缓存,先到缓存中找数据,若缓存不在,则到数据库中找数据,并将数据库中的数据加载到缓存中,为了下一次查找相同的数据时不用到数据库中查找,提高效率。但是存在缓存穿透问题,缓存穿透是指恶意用户请求一个不存在的数据,导致请求直接访问数据库,造成数据库压力过大。布隆过滤器可以先判断请求的数据是否存在于布隆过滤器中,如果不存在,直接返回不存在,避免对数据库的无效查询。
  4. 对数据库查询提效:在数据库中,布隆过滤器可以用来加速查询操作。例如:一个app要快速判断一个电话号码是否注册过,可以使用布隆过滤器来判断一个用户电话号码是否存在于表中,如果不存在,可以直接返回不存在,避免对数据库进行无用的查询操作。如果在(存在误判),再去数据库查询进行二次确认。

六.海量数据处理问题

1.10亿个整数中求最大的前100个

经典topk问题,用小堆解决

2.100亿个整数中,求某个整数是否出现

位图问题

3.给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?

分析:假设平均每个query字符串50byte,100亿个query就是5000亿byte,约等于500G(1G约等于10亿多Byte)。哈希表/红黑树等数据结构肯定是无能为力的。

解决方案1:可以用布隆过滤器解决,一个文件中的query放进布隆过滤器,另一个文件依次查找,在的就是交集,问题就是找到交集不够准确,因为在的值可能是误判的,但是交集一定被找到了。

解决方案2:

  1. 哈希切分,首先内存的访问速度远大于硬盘,大文件放到内存搞不定,那么我们可以考虑切分为小文件,再放进内存处理。
  2. 但是不要平均切分,因为平均切分以后,每个小文件都需要依次暴力处理,效率还是太低了。
  3. 可以利用哈希切分,依次读取文件中query,i=HashFunc(query)%N,N为准备切分多少分小文件,N取决于切成多少份,内存能放下,query放进第i号小文件,这样A和B中相同的query算出的hash值i是一样的,相同的query就进入的编号相同的小文件就可以编号相同的文件直接找交集,不用交叉找,效率就提升了。
  4. 本质是相同的query在哈希切分过程中,一定进入的同一个小文件Ai和Bi,不可能出现A中的某个query进入Ai,但是B中的相同query进入了和Bj的情况,所以对Ai和Bi进行求交集即可,不需要Ai和Bj求交集(i和j是不同的整数)
  5. 哈希切分的问题就是每个小文件不是均匀切分的,可能会导致某个小文件很大内存放不下。我们细细分析一下某个小文件很大有两种情况:1.这个小文件中大部分是同一个query。2.这个小文件是有很多的不同query构成,本质是这些query冲突了。针对情况1,其实放到内存的set中是可以放下的,因为set是去重的。针对情况2,需要换个哈希函数继续⼆次哈希切分。所以本体我们遇到大于1G小文件,可以继续读到set中找交集,若set insert时抛出了异常(set插入数据抛异常只可能是申请内存失败了,不会有其他情况),那么就说明内存放不下是情况2,换个哈希函数进行⼆次哈希切分后再对应找交集。

在这里插入图片描述

4.给一个超过100G大小的log file,log中存着ip地址,设计算法找到出现次数最多的ip地址?查找出现次数前10的ip地址?

本题的思路跟上题完全类似,依次读取文件A中ip,i=HashFunc(ip)%500,ip放进Ai号小文件,然后依次用map<string,int>对每个Ai小文件统计ip次数,同时求出现次数最多的ip或者topk ip。本质是相同的ip在哈希切分过程中,一定进入同一个小文件Ai,不可能出现同一个ip进入Ai和Aj的情况,所以对Ai进行统计次数就是准确的ip次数。

在这里插入图片描述


原文地址:https://blog.csdn.net/2203_76003626/article/details/145125849

免责声明:本站文章内容转载自网络资源,如侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!