现在21世纪,有人称之为大数据时代,谁有数据量大的数据,谁能够从海量数据中提取到有用信息,并能够将其转换为资本,谁就取得了互联网的地位。
互联网数据是由生活在网络上的每一个用户所产生的,用户在互联网上的活动会被记录下来,这就是数据,海量用户,有着海量数据。这些数据被利用,分析,与各种各样的广告联系在一起,进而把这些广告推送给用户,这些推送的广告都是用户的网络行为分析出的结果。
QQ上活跃这大量的用户,QQ空间里面记录了许多人的日常,这些就是数据。在日常使用QQ空间的时候,会偶尔点击给我们好友点赞的朋友,之后我们就能看到我们好友的好友的空间,依次类推,我们可以看到海量信息。
一、 前言
布隆过滤器 (Bloom Filter)是由Burton Howard Bloom于1970年提出,用于判断一个元素是否在集合中。与课本上学的数据结构不同,它是一种概率型数据结构,所谓概率型,就是指在判重的时候,并不是完全一定确保某个数据在集合中,课本上的二分查找,哈希,都可以一定确定某个元素是否在集合中。
在爬虫的时候,数据发生重复,需要判重,判断该条数据是否加入到队列中。传统哈希表可用于判断元素是否在集合中,时间复杂度O(1),空间复杂度o(n),布隆过滤器牺牲了一点时间,空间复杂度大约是哈希表的\frac{1}{4}。
布隆过滤器也支持数据的插入。
二、算法过程
一个布隆过滤器是一个有m个bit位的数组,每一个bit位都初始化为0。并且定义有k个不同的hash 函数,每个都以随机的将元素均匀hash到m个不同位置中的一个。
在下面的介绍中n为元素数,m为布隆过滤器或哈希表的槽数,k为布隆过滤器hash 函数个数。
三、举例说明
以垃圾邮件过滤中黑白名单为例:假设现有1亿个email的黑名单,每个都拥有8 bytes的指纹信息,则能的数据量大小为
需要的位数组大小为
这个数据量对于位数组来说是太大了,且在邮箱里,邮箱数量相比较邮箱范围过于稀疏,而且还没有考虑到哈希表中的碰撞问题。
若采用哈希表,由于大多数采用开放地址法来解决碰撞,而此时的查找时间复杂度为 :O(\frac{1}{1-\frac{n}{m}}),当哈希表半满(\frac{n}{m}=\frac{1}{2}),则每次search需要探测2次,因此在保证效率的情况下哈希表的存储效率最好不超过50%。此时每个元素占8 bytes,总空间为:\frac{10^8×8Byte}{1-0.5}=1.6GB
若采用布隆过滤器,取k=8。因为n为1亿,所以总共需要8 × 10^8被置位为1,在保证误判率低,选取合适的k,m,让空间利用率为50%,所以总空间为:\frac{8×10^8bis}{50%}\approx200MB,所需空间比上述哈希结构小得多,并且误判率在万分之一以下。
四、误判概率的证明和计算
假设布隆过滤器中的hash函数满足简单均匀哈希假设:每个元素都等概率地hash到m个槽中的任何一个,与其它元素被hash到哪个slot无关。
若m为bit数,则对某一特定bit位在一个元素由某特定hash函数插入时没有被置位为1的概率为:1-\frac{1}{m},该结论算法导论有详细证明。
那么k个hash 函数中没有一个对其置位的概率为:(1-\frac{1}{m})^k。
如果插入了n个元素,但都未将其置位的概率为:(1-\frac{1}{m})^{kn}。
则此位被置位的概率为:1-(1-\frac{1}{m})^{kn}。
现在考虑查找阶段,若对应某个待查找元素的k bits全部置位为1,则可判定其在集合中。因此将某元素误判的概率为:(1-(1-\frac{1}{m})^{kn})^k。
从上式中可以看出,当m增大或n减小时,都会使得误判率减小,这也符合直觉。
根据小学二年级学过的极限公式:\lim\limits_{x\to0} (1+x)^{\frac{1}{x}}=e
(1-(1-\frac{1}{m})^{kn})^k=(1-(1-\frac{1}{m})^{m×\frac{kn}{-m}})^k~(1-e^{-\frac{nk}{m}})^k。
现在可以假设当给定m,和n的当k取何值时,可以将误判率降至最低。
假设f(k)=(1-e^{-\frac{nk}{m}})^k,设b = e^{\frac{n}{m}},此时,f(k)=(1-b^{-k})^k,接下来求f(k)的最值:
f(k)=(1-b^{-k})^k,两边同时取对数lnf(k)=kln(1-b^{-k})
两边同时对k求导 \frac{1}{f(k)}f’(k)=ln(1-b^{-k})+k\frac{b^{-k}lnb}{1-b^{-k}}=0
解上述方程:☞(1-b^{-k})ln(1-b^{-k})=-kb^{-k}lnb
☞(1-b^{-k})ln(1-b^{-k})=b^{-k}lnb^{-k}
☞(1-b^{-k})=b^{-k}
☞b^{-k}=\frac{1}{2}
☞e^{-\frac{kn}{m}}=\frac{1}{2}
☞k = ln2\frac{m}{n}
此时误判率f(k)=(1-b^{-k})^k=(1-\frac{1}{2})^{k}=2^{-ln2\frac{m}{n}}\approx0.6185^{\frac{m}{n}}
调节\frac{m}{n}的大小,即可降低误判率f(k)。
五、设计和应用布隆过滤器的方法
首先要先由用户决定要add的元素数n,希望的误差率P。其他参数需要计算。
首先要计算需要的内存大小m bits:p = 2^{-ln2\frac{m}{n}}⇨m=-\frac{nlnp}{(ln2)^2}
再由m,n得到hash函数的个数:k = ln2\frac{m}{n}
至此结束。
一、前言
人的社交可以抽象定义成一个网络图。
以每一个个人为中心,向外扩充一圈即时自己的好友圈。好友圈会有交叠。
不断的以每个人为中心,向外扩充,就是整个网络图(社交遍历)。
每个人的好友圈是不同的,你的好友情况在别人那里情况可能是不一样的。
个人只能看到自己的朋友圈,去看看别人的朋友圈,了解一下其他圈子动态,也是一件相当有趣的事。
经过一圈圈的扩充遍历,好友的动态内容逐渐不同。我一开始能够访问到的内容是像自己一样普通大学生的动态,日常,到中间是那些转发,非原创动态,到最后,就逐渐变成卖衣服,卖手机的。
个人解释:qq空间其实是可以限制访问的,那些开放qq空间的人,会有哪些人?一,不在意别人访问的,二,需要别人浏览,阅读,转发。三,为了利益。
这些数据都有些什么用呢?有这些人的qq号,qq号主发的动态,号主的资料卡信息,其实这里最真实的只有qq号,然后是动态,分析假的资料信息并没有什么意义。qq号没得分析,动态分析,只得大致去浏览了。告一段落吧。
qq空间里人间百态。那个80-90-00的人间百态。