kl800.com省心范文网

大数据常见处理方法总结


《海量数据处理常用思路和方法》
大数据量,海量数据 处理方法总结

最近有点忙,稍微空闲下来,发篇总结贴。 大数据量的问题是很多面试笔试中经常出现的问题,比如 baidu google 腾讯 这样的一些涉及到海量数据 的公司经常会问到。 下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有 的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司 的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论。 1.Bloom filter 适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集 基本原理及要点: 对于原理来说很简单,位数组+k 个独立 hash 函数。将 hash 函数对应的值的位数组置 1,查找时如果发现 所有 hash 函数对应位都是 1 说明存在,很明显这个过程并不保证查找的结果是 100%正确的。同时也不支 持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个 counter 数组代替位数组,就可以支持删除了。 还有一个比较重要的问题,如何根据输入元素个数 n,确定位数组 m 的大小及 hash 函数个数。当 hash 函 数个数 k=(ln2)*(m/n)时错误率最小。在错误率不大于 E 的情况下,m 至少要等于 n*lg(1/E)才能表示任意 n 个元素的集合。 m 还应该更大些, 但 因为还要保证 bit 数组里至少一半为 0, m 应该>=nlg(1/E)*lge 大 则 概就是 nlg(1/E)1.44 倍(lg 表示以 2 为底的对数)。 举个例子我们假设错误率为 0.01,则此时 m 应大概是 n 的 13 倍。这样 k 大概是 8 个。 注意这里 m 与 n 的单位不同, 是 bit 为单位, n 则是以元素个数为单位(准确的说是不同元素的个数)。 m 而 通常单个元素的长度都是有很多 bit 的。所以使用 bloom filter 内存上通常都是节省的。 扩展: Bloom filter 将集合中的元素映射到位数组中,用 k(k 为哈希函数个数)个映射位是否全 1 表示元素在不 在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个 counter,从而支持了元素的 删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF 采用 counter 中的最小值来 近似表示元素的出现频率。 问题实例:给你 A,B 两个文件,各存放 50 亿条 URL,每条 URL 占用 64 字节,内存限制是 4G,让你找出 A,B 文件共同的 URL。如果是三个乃至 n 个文件呢? 根据这个问题我们来计算下内存的占用,4G=2^32 大概是 40 亿*8 大概是 340 亿,n=50 亿,如果按出错

率 0.01 算需要的大概是 650 亿个 bit。现在可用的是 340 亿,相差并不多,这样可能会使出错率上升些。 另外如果这些 urlip 是一一对应的,就可以转换成 ip,则大大简单了。 2.Hashing 适用范围:快速查找,删除的基本数据结构,通常需要总数据量可以放入内存 基本原理及要点: hash 函数选择,针对字符串,整数,排列,具体相应的 hash 方法。 碰撞处理,一种是 open hashing,也称为拉链法;另一种就是 closed hashing,也称开地址法,opened addressing。 扩展: d-left hashing 中的 d 是多个的意思,我们先简化这个问题,看一看 2-left hashing。2-left hashing 指的是 将一个哈希表分成长度相等的两半,分别叫做 T1 和 T2,给 T1 和 T2 分别配备一个哈希函数,h1 和 h2。 在存储一个新的 key 时,同时用两个哈希函数进行计算,得出两个地址 h1[key]和 h2[key]。这时需要检查 T1 中的 h1[key]位置和 T2 中的 h2[key]位置,哪一个位置已经存储的(有碰撞的)key 比较多,然后将新 key 存储在负载少的位置。如果两边一样多,比如两个位置都为空或者都存储了一个 key,就把新 key 存 储在左边的 T1 子表中,2-left 也由此而来。在查找一个 key 时,必须进行两次 hash,同时查找两个位置。 问题实例: 1).海量日志数据,提取出某日访问百度次数最多的那个 IP。 IP 的数目还是有限的,最多 2^32 个,所以可以考虑使用 hash 将 ip 直接存入内存,然后进行统计。 3.bit-map 适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是 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。

4.堆 适用范围:海量数据前 n 大,并且 n 比较小,堆可以放入内存 基本原理及要点:最大堆求前 n 小,最小堆求前 n 大。方法,比如求前 n 小,我们比较当前元素与最大堆 里的最大元素,如果它小于最大元素,则应该替换那个最大元素。这样最后得到的 n 个元素就是最小的 n 个。适合大数据量,求前 n 小,n 的大小比较小的情况,这样可以扫描一遍即可得到所有的前 n 元素,效 率很高。 扩展:双堆,一个最大堆与一个最小堆结合,可以用来维护中位数。 问题实例: 1)100w 个数中找最大的前 100 个数。 用一个 100 个元素大小的最小堆即可。 5.双层桶划分 ----其实本质上就是【分而治之】的思想,重在“分”的技巧上! 适用范围:第 k 大,中位数,不重复或重复的数字 基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最 后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个例子。 扩展: 问题实例: 1).2.5 亿个整数中找出不重复的整数的个数,内存空间不足以容纳这 2.5 亿个整数。 有点像鸽巢原理,整数个数为 2^32,也就是,我们可以将这 2^32 个数,划分为 2^8 个区域(比如用单个文 件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利用 bitmap 就可以直接解决了。也 就是说只要有足够的磁盘空间,就可以很方便的解决。 2).5 亿个 int 找它们的中位数。 这个例子比上面那个更明显。首先我们将 int 划分为 2^16 个区域,然后读取数据统计落到各个区域里的数 的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是 中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。 实际上, 如果不是 int 是 int64, 我们可以经过 3 次这样的划分即可降低到可以接受的程度。 即可以先将 int64 分成 2^24 个区域,然后确定区域的第几大数,在将该区域分成 2^20 个子区域,然后确定是子区域的第 几大数,然后子区域里的数的个数只有 2^20,就可以直接利用 direct addr table 进行统计了。 6.数据库索引

适用范围:大数据量的增删改查 基本原理及要点:利用数据的设计实现方法,对海量数据的增删改查进行处理。 扩展: 问题实例:

7.倒排索引(Inverted index) 适用范围:搜索引擎,关键字查询 基本原理及要点:为何叫倒排索引?一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一 组文档中的存储位置的映射。 以英文为例,下面是要被索引的文本: T0 = "it is what it is" T1 = "what is it" T2 = "it is a banana" 我们就能得到下面的反向文件索引: "a": "is": "it": "what": {2} {0, 1, 2} {0, 1, 2} {0, 1} "banana": {2}

检索的条件"what", "is" 和 "it" 将对应集合的交集。 正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查 询和每个单词在校验文档中的验证这样的查询。在正向索引中,文档占据了中心的位置,每个文档指向了 一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词,而反向索引则是单词指向了包含 它的文档,很容易看到这个反向的关系。 扩展: 问题实例:文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字搜索。 8.外排序 适用范围:大数据的排序,去重 基本原理及要点:外排序的归并方法,置换选择 败者树原理,最优归并树 扩展: 问题实例:

1).有一个 1G 大小的一个文件,里面每一行是一个词,词的大小不超过 16 个字节,内存限制大小是 1M。 返回频数最高的 100 个词。 这个数据具有很明显的特点,词的大小为 16 个字节,但是内存只有 1m 做 hash 有些不够,所以可以用来 排序。内存可以当输入缓冲区使用。 9.trie 树 适用范围:数据量大,重复多,但是数据种类小可以放入内存 基本原理及要点:实现方式,节点孩子的表示方式 扩展:压缩实现。 问题实例: 1).有 10 个文件,每个文件 1G, 每个文件的每一行都存放的是用户的 query,每个文件的 query 都可能重 复。要你按照 query 的频度排序 。 2).1000 万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。请问怎么 设计和实现? 3).寻找热门查询:查询串的重复度比较高,虽然总数是 1 千万,但如果除去重复后,不超过 3 百万个,每 个不超过 255 字节。 10.分布式处理 mapreduce 适用范围:数据量大,但是数据种类小可以放入内存 基本原理及要点:将数据交给不同的机器去处理,数据划分,结果归约。

1. Bloom-Filter 算法简介
Bloom-Filter,即布隆过滤器,1970 年由 Bloom 中提出。它可以用于检索一个元素是否在一个集合 中。 Bloom Filter(BF)是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并 能判断一个元素是否属亍这个集合。它是一个判断元素是否存在集合的快速的概率算法。Bloom Filter 有 可能会出现错诨判断,但丌会漏掉判断。也就是 Bloom Filter 判断元素丌再集合,那肯定丌在。如果判断 元素存在集合中,有一定的概率判断错诨。因此,Bloom Filter 丌适合那些“零错诨”的应用场合。而在 能容忍低错诨率的应用场合下,Bloom Filter 比其他常见的算法(如 hash,折半查找)极大节省了空间。 它的优点是空间效率和查询时间都进进超过一般的算法,缺点是有一定的诨识别率和删除困难。

Bloom Filter 的详细介绍:Bloom

Filter

2、 Bloom-Filter 的基本思想
Bloom-Filter 算法的核心思想就是利用多个丌同的 Hash 函数来解决“冲突” 。 计算某元素 x 是否在一个集合中, 首先能想到的方法就是将所有的已知元素保存起来构成一个集合 R, 然后用元素 x 跟这些 R 中的元素一一比较来判断是否存在亍集合 R 中;我们可以采用链表等数据结构来实 现。但是,随着集合 R 中元素的增加,其占用的内存将越来越大。试想,如果有几千万个丌同网页需要下 载,所需的内存将足以占用掉整个迚程的内存地址空间。即使用 MD5,UUID 这些方法将 URL 转成固定 的短小的字符串,内存占用也是相当巨大的。 亍是,我们会想到用 Hash table 的数据结构,运用一个足够好的 Hash 函数将一个 URL 映射到二迚 制位数组(位图数组)中的某一位。如果该位已经被置为 1,那么表示该 URL 已经存在。 Hash 存在一个冲突(碰撞)的问题,用同一个 Hash 得到的两个 URL 的值有可能相同。为了减少冲 突,我们可以多引入几个 Hash,如果通过其中的一个 Hash 值我们得出某元素丌在集合中,那么该元素肯 定丌在集合中。只有在所有的 Hash 函数告诉我们该元素在集合中时,才能确定该元素存在亍集合中。这 便是 Bloom-Filter 的基本思想。

原理要点:一是位数组, 而是 k 个独立 hash 函数。
1)位数组: 假设 Bloom Filter 使用一个 m 比特的数组来保存信息,初始状态时,Bloom

Filter 是一个包含 m 位的

位数组,每一位都置为 0,即 BF 整个数组的元素都设置为 0。

2)添加元素,k 个独立 hash 函数
为了表达 S={x1, x2,…,xn}这样一个 n 个元素的集合, Bloom Filter 使用 k 个相互独立的哈希函数 (Hash Function),它们分别将集合中的每个元素映射到{1,…,m}的范围中。

当我们往 Bloom Filter 中增加任意一个元素 x 时候,我们使用 k 个哈希函数得到 k 个哈希值,然后将数组中 对应的比特位设置为 1。即第 i 个哈希函数映射的位置 hashi(x)就会被置为 1(1≤i≤k)。

注意, 如果一个位置多次被置为 1, 那么只有第一次会起作用, 后面几次将没有任何效果。 在下图中, k=3, 且有两个哈希函数选中同一个位置(从左边数第五位,即第二个“1“处)。

3)判断元素是否存在集合
在判断 y 是否属于这个集合时,我们只需要对 y 使用 k 个哈希函数得到 k 个哈希值,如果所有 hashi(y) 的位置都是 1(1≤i≤k),即 k 个位置都被设置为 1 了,那么我们就认为 y 是集合中的元素,否则就认为 y 不是集合中的元素。 下图中 y1 就不是集合中的元素 (因为 y1 有一处指向了“0”位) y2 或者属于这个集合, 。 或者刚好是一个 false positive。

显然这 个判断并丌保证查找的结果是 100%正确的。 Bloom Filter 的缺点: 1)Bloom Filter 无法从 Bloom Filter 集合中删除一个元素。因为该元素对应的位会牵劢到其

他的元素。 所以一个简单的改迚就是 counting Bloom filter, 用一个 counter 数组代替位数组, 就可以支持删除了。 此外,Bloom Filter 的 hash 函数选择会影响算法的效果。
2)还有一个比较重要的问题,如何根据输入元素个数 n,确定位数组 m 的大小及 hash 函数个数, 即 hash 函数选择会影响算法的效果。当 hash 函数个数 k=(ln2)*(m/n)时错诨率最小。在错诨率丌大亍 E 的情冴 下,m 至少要等亍 n*lg(1/E) 才能表示任意 n 个元素的集合。但 m 还应该更大些,因为还要保证 bit 数组里至少一半为 0,则 m 应 该>=nlg(1/E)*lge ,大概就是 nlg(1/E)1.44 倍(lg 表示以 2 为底的对 数)。 举个例子我们假设错诨率为 0.01,则此时 m 应大概是 n 的 13 倍。这样 k 大概是 8 个。 注意:

这里 m 不 n 的单位丌同,m 是 bit 为单位,而 n 则是以元素个数为单位(准确的说是丌同元素的个 数)。通常单个元素的长度都是有很多 bit 的。所以使用 bloom filter 内存上通常都是节省的。 一般 BF 可以不一些 key-value 的数据库一起使用,来加快查询。由亍 BF 所用的空间非常小,所有 BF 可以常驻内存。这样子的话,对亍大部分丌存在的元素,我们只需要访问内存中的 BF 就可以判断出来 了,只有一小部分,我们需要访问在硬盘上的 key-value 数据库。从而大大地提高了效率。

一个 Bloom Filter 有以下参数:

m n k f

bit 数组的宽度(bit 数) 加入其中的 key 的数量 使用的 hash 函数的个数 False Positive 的比率

Bloom Filter 的 f 满足下列公式:

在给定 m 和 n 时,能够使 f 最小化的 k 值为:

此时给出的 f 为:

根据以上公式,对亍任意给定的 f,我们有:

n = m ln(0.6185) / ln(f)

[1]

同时,我们需要 k 个 hash 来达成这个目标:

k = - ln(f) / ln(2)

[2]

由于 k 必须取整数,我们在 Bloom Filter 的程序实现中,还应该使用上面的公式来求得实际的 f:
-kn/m k

f = (1 – e

)

[3]

以上 3 个公式是程序实现 Bloom Filter 的关键公式。

3、 扩展 CounterBloom Filter

CounterBloom Filter
BloomFilter 有个缺点, 就是不支持删除操作, 因为它不知道某一个位从属于哪些向量。 那我们可以给 Bloom Filter 加上计数器,添加时增加计数器,删除时减少计数器。 但这样的 Filter 需要考虑附加的计数器大小,假如同个元素多次插入的话,计数器位数较少的情况下,就 会出现溢出问题。如果对计数器设置上限值的话,会导致 Cache Miss,但对某些应用来说,这并不是什么 问题,如 Web Sharing。

Compressed Bloom Filter
为了能在服务器之间更快地通过网络传输 Bloom Filter,我们有方法能在已完成 Bloom Filter 之后,得到一 些实际参数的情况下进行压缩。 将元素全部添加入 Bloom Filter 后,我们能得到真实的空间使用率,用这个值代入公式计算出一个比 m 小 的值,重新构造 Bloom Filter,对原先的哈希值进行求余处理,在误判率不变的情况下,使得其内存大小更 合适。

4、 Bloom-Filter 的应用
Bloom-Filter 一般用亍在大数据量的集合中判定某元素是否存在。例如邮件服务器中的垃圾 邮件过滤器。在搜索引擎领域,Bloom-Filter 最常用亍网络蜘蛛(Spider)的 URL 过滤,网络蜘蛛通 常有一个 URL 列表,保存着将要下载和已经下载的网页的 URL,网络蜘蛛下载了一个网页,从网页 中提取到新的 URL 后,需要判断该 URL 是否已经存在亍列表中。此时,Bloom-Filter 算法是最好的 选择。

1.key-value 加快查询 一般 Bloom-Filter 可以不一些 key-value 的数据库一起使用,来加快查询。 一般 key-value 存储系统的 values 存在硬盘,查询就是件费时的事。将 Storage 的数据都插入
Filter,在 Filter 中查询都丌存在时,那就丌需要去 Storage 查询了。当 False Position 出现时,只是会导 致一次多余的 Storage 查询。

由亍 Bloom-Filter 所用的空间非常小,所有 BF 可以常驻内存。这样子的话,对亍大部分丌存 在的元素,我们只需要访问内存中的 Bloom-Filter 就可以判断出来了,只有一小部分,我们需要访 问在硬盘上的 key-value 数据库。从而大大地提高了效率。如图:

2 .Google 的 BigTable Google 的 BigTable 也使用了 Bloom Filter, 以减少丌存在的行戒列在磁盘上的查询, 大大提高了 数据库的查询操作的性能。

3. Proxy-Cache

在 Internet Cache Protocol 中的 Proxy-Cache 很多都是使用 Bloom Filter 存储 URLs,除了高效的查 询外,还能很方便得传输交换 Cache 信息。

4.网络应用
1) P2P 网络中查找资源操作, 可以对每条网络通路保存 Bloom Filter, 当命中时, 则选择该通路访问。 2)广播消息时,可以检测某个 IP 是否已发包。 3)检测广播消息包的环路,将 Bloom Filter 保存在包里,每个节点将自己添加入 Bloom Filter。 4)信息队列管理,使用 Counter Bloom Filter 管理信息流量。

5. 垃圾邮件地址过滤
像网易, QQ 这样的公众电子邮件 (email) 提供商, 总是需要过滤来自发送垃圾邮件的人 (spamer) 的垃圾邮件。 一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址,全世界少说 也有几十亿个发垃圾邮件的地址,将他们都存起来则需要大量的网络服务器。 如果用哈希表,每存储一亿个 email 地址,就需要 1.6GB 的内存(用哈希表实现的具体办法是将每一 个 email 地址对应成一个八字节的信息指纹,然后将这些信息指纹存入哈希表,由于哈希表的存储效率一 般只有 50%, 因此一个 email 地址需要占用十六个字节。 一亿个地址大约要 1.6GB, 即十六亿字节的内存) 。 因此存贮几十亿个邮件地址可能需要上百 GB 的内存。 而 Bloom Filter 只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。 BloomFilter 决不会漏掉任何一个在黑名单中的可疑地址。而至于误判问题,常见的补救办法是在建立一个 小的白名单,存储那些可能别误判的邮件地址。

5、 Bloom-Filter 的具体实现
c 诧言实现: stdafx.h:
1. 2. 3. 4. 5. 6. #pragma once #include <stdio.h> #include "stdlib.h" #include <iostream> #include <time.h> using namespace std;

1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

#include "stdafx.h"

#define ARRAY_SIZE 256 /*we get the 256 chars of each line*/ #define SIZE 48000000 /* size should be 1/8 of max*/ #define MAX 384000000/*the max bit space*/

#define SETBIT(ch,n) ch[n/8]|=1<<(7-n%8) #define GETBIT(ch,n) (ch[n/8]&1<<(7-n%8))>>(7-n%8)

11. unsigned int len(char *ch);/* functions to calculate the length of the url*/ 12. 13. unsigned int RSHash(char* str, unsigned int len);/* functions to calculate the hash value of the url */ 14. unsigned int JSHash(char* str, unsigned int len);/* functions to calculate the hash value of the url */ 15. unsigned int PJWHash(char* str, unsigned int len);/* functions to calculate the hash value of the ur l*/ 16. unsigned int ELFHash(char* str, unsigned int len);/* functions to calculate the hash value of the ur l*/ 17. unsigned int BKDRHash(char* str, unsigned int len);/* functions to calculate the hash value of the u rl*/ 18. unsigned int SDBMHash(char* str, unsigned int len);/* functions to calculate the hash value of the u rl*/ 19. unsigned int DJBHash(char* str, unsigned int len);/* functions to calculate the hash value of the ur l*/ 20. unsigned int DEKHash(char* str, unsigned int len);/* functions to calculate the hash value of the ur l*/ 21. unsigned int BPHash(char* str, unsigned int len);/* functions to calculate the hash value of the url */ 22. unsigned int FNVHash(char* str, unsigned int len);/* functions to calculate the hash value of the ur l*/ 23. unsigned int APHash(char* str, unsigned int len);/* functions to calculate the hash value of the url */ 24. unsigned int HFLPHash(char* str,unsigned int len);/* functions to calculate the hash value of the ur l*/ 25. unsigned int HFHash(char* str,unsigned int len);/* functions to calculate the hash value of the url* / 26. unsigned int StrHash( char* str,unsigned int len);/* functions to calculate the hash value of the ur l*/ 27. unsigned int TianlHash(char* str,unsigned int len);/* functions to calculate the hash value of the u rl*/ 28. 29.

30. int main() 31. { 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. if( GETBIT(vector, StrHash(ch,len(ch))%MAX) ) { } fgets(ch,ARRAY_SIZE,fp1); flag=0; tt++; if( GETBIT(vector, HFLPHash(ch,len(ch))%MAX) ) { flag++; } else { SETBIT(vector,HFLPHash(ch,len(ch))%MAX ); while(!feof(fp1)) { /* the check process*/ } for(i=0;i<SIZE;i++) { vector[i]=0; /*set 0*/ } strftime(buf,32,"%Y-%m-%d %H:%M:%S",localtime(&tmp)); printf("%s\n",buf); /*print the system time*/ printf("Please enter the file you want to save to:\n"); scanf("%s",&file2); if( (fp2 = fopen(file2,"w")) == NULL) { printf("Connot open the file %s\n",file2); } printf("Please enter the file with repeated urls:\n"); scanf("%s",&file1); if( (fp1 = fopen(file1,"rb")) == NULL) { /* open the goal file*/ char file1[100],file2[100]; FILE *fp1,*fp2;/*pointer to the file */ char ch[ARRAY_SIZE]; char *vector ;/* the bit space*/ vector = (char *)calloc(SIZE,sizeof(char)); int i,num,num2=0; /* the number to record the repeated urls and the total of it*/ unsigned int tt=0; int flag; char buf[257]; /*it helps to check weather the url has already existed */ /*it helps to print the start time of the program */

time_t tmp = time(NULL);

printf("Connot open the file %s!\n",file1);

74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. } } /* else } } } } }

flag++; } else { SETBIT(vector,StrHash(ch,len(ch))%MAX );

if( GETBIT(vector, HFHash(ch,len(ch))%MAX) ) flag++; } else { SETBIT(vector,HFHash(ch,len(ch))%MAX );

{

if( GETBIT(vector, DEKHash(ch,len(ch))%MAX) ) { flag++; } else { SETBIT(vector,DEKHash(ch,len(ch))%MAX );

if( GETBIT(vector, TianlHash(ch,len(ch))%MAX) ) { flag++; } else { SETBIT(vector,TianlHash(ch,len(ch))%MAX );

if( GETBIT(vector, SDBMHash(ch,len(ch))%MAX) ) flag++; } else { SETBIT(vector,SDBMHash(ch,len(ch))%MAX );

{

if(flag<6) num2++;

fputs(ch,fp2);

printf(" %d",flag); */

/* the result*/ printf("\nThere are %d urls!\n",tt); printf("\nThere are %d not repeated urls!\n",num2); printf("There are %d repeated urls!\n",tt-num2); fclose(fp1); fclose(fp2); return 0;

118. 119. 120. /*functions may be used in the main */ 121. unsigned int len(char *ch) 122. { 123. 124. 125. 126. 127. 128. } 129. 130. unsigned int RSHash(char* str, unsigned int len) { 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. } 142. /* End Of RS Hash Function */ 143. 144. 145. unsigned int JSHash(char* str, unsigned int len) 146. { 147. 148. 149. 150. 151. 152. 153. 154. } 155. /* End Of JS Hash Function */ 156. 157. 158. unsigned int PJWHash(char* str, unsigned int len) 159. { 160. 161. const unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8); const unsigned int ThreeQuarters = (unsigned int)((BitsInUnsignedInt * 3) / 4); } return hash; for(i=0; i<len; str++, i++) { hash ^= ((hash<<5) + (*str) + (hash>>2)); unsigned int hash = 1315423911; unsigned int i = 0; } return hash; for(i=0; i<len; str++, i++) { hash = hash*a + (*str); a = a*b; unsigned int b = 378551; unsigned int a = 63689; unsigned int hash = 0; unsigned int i = 0; } return m; int m=0; while(ch[m]!='\0') { m++;

162. 163. 164. 165. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. }

const unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8); const unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth); unsigned int hash = 0; unsigned int test = 0; unsigned int i = 0;

for(i=0;i<len; str++, i++) { hash = (hash<<OneEighth) + (*str); if((test = hash & HighBits) != 0) {

hash = ((hash ^(test >> ThreeQuarters)) & (~HighBits)); } }

return hash;

177. /* End Of 178. 179.

P. J. Weinberger Hash Function */

180. unsigned int ELFHash(char* str, unsigned int len) 181. { 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193. 194. } 195. /* End Of ELF Hash Function */ 196. 197. 198. unsigned int BKDRHash(char* str, unsigned int len) 199. { 200. 201. 202. 203. 204. 205. for(i = 0; i < len; str++, i++) { unsigned int seed = 131; /* 31 131 1313 13131 131313 etc.. */ unsigned int hash = 0; unsigned int i = 0; } return hash; } hash &= ~x; for(i = 0; i < len; str++, i++) { hash = (hash << 4) + (*str); if((x = hash & 0xF0000000L) != 0) { hash ^= (x >> 24); unsigned int hash = 0; unsigned int x unsigned int i = 0; = 0;

206. 207. 208. 209. 210. } }

hash = (hash * seed) + (*str);

return hash;

211. /* End Of BKDR Hash Function */ 212. 213. 214. unsigned int SDBMHash(char* str, unsigned int len) 215. { 216. 217. 218. 219. 220. 221. 222. 223. 224. } 225. /* End Of SDBM Hash Function */ 226. 227. 228. unsigned int DJBHash(char* str, unsigned int len) 229. { 230. 231. 232. 233. 234. 235. 236. 237. 238. } 239. /* End Of DJB Hash Function */ 240. 241. 242. unsigned int DEKHash(char* str, unsigned int len) 243. { 244. 245. 246. 247. 248. 249. } for(i = 0; i < len; str++, i++) { hash = ((hash << 5) ^ (hash >> 27)) ^ (*str); unsigned int hash = len; unsigned int i = 0; return hash; } for(i = 0; i < len; str++, i++) { hash = ((hash << 5) + hash) + (*str); unsigned int hash = 5381; unsigned int i = 0; return hash; } for(i = 0; i < len; str++, i++) { hash = (*str) + (hash << 6) + (hash << 16) - hash; unsigned int hash = 0; unsigned int i = 0;

250. 251. }

return hash;

252. /* End Of DEK Hash Function */ 253. 254. 255. unsigned int BPHash(char* str, unsigned int len) 256. { 257. 258. 259. 260. 261. 262. 263. 264. } 265. /* End Of BP Hash Function */ 266. 267. 268. unsigned int FNVHash(char* str, unsigned int len) 269. { 270. 271. 272. 273. 274. 275. 276. 277. 278. 279. 280. } 281. /* End Of FNV Hash Function */ 282. 283. 284. unsigned int APHash(char* str, unsigned int len) 285. { 286. 287. 288. 289. 290. 291. 292. 293. } for(i = 0; i < len; str++, i++) { hash ^= ((i & 1) == 0) ? ( (hash << 7) ^ (*str) * (hash >> 3)) : unsigned int hash = 0xAAAAAAAA; unsigned int i = 0; return hash; } for(i = 0; i < len; str++, i++) { hash *= fnv_prime; hash ^= (*str); const unsigned int fnv_prime = 0x811C9DC5; unsigned int hash unsigned int i = 0; = 0; return hash; } unsigned int hash = 0; unsigned int i = 0;

for(i = 0; i < len; str++, i++) { hash = hash << 7 ^ (*str);

(~((hash << 11) + (*str) ^ (hash >> 5)));

294. 295. }

return hash;

296. /* End Of AP Hash Function */ 297. unsigned int HFLPHash(char *str,unsigned int len) 298. { 299. 300. 301. 302. 303. 304. 305. 306. } 307. /* End Of HFLP Hash Function*/ 308. unsigned int HFHash(char* str,unsigned int len) 309. { 310. 311. 312. 313. 314. 315. 316. 317. 318. 319. } 320. /*End Of HKHash Function */ 321. 322. unsigned int StrHash( char *str,unsigned int len) 323. { 324. 325. 326. 327. 328. 329. 330. 331. 332. } return h; } register unsigned int h; int result=0; char* ptr=str; int c; int i=0; for (i=1;c=*ptr++;i++) result += c*3*i; if (result<0) result = -result; return result%len; unsigned int n=0; int i; char* b=(char *)&n; for(i=0;i<strlen(str);++i) { b[i%4]^=str[i]; } return n%len;

register unsigned char *p; for(h=0,p=(unsigned char *)str;*p;p++) { h=31*h+*p;

333. /*End Of StrHash Function*/ 334. 335. unsigned int TianlHash(char *str,unsigned int len) 336. { 337. unsigned long urlHashValue=0;

338. 339. 340. 341. 342. 343. 344. 345. 346. 347. 348. 349. 350. 351. 352. 353. 354. 355. 356. 357. 358. 359. 360. 361. 362. 363. 364. 365. 366. 367. 368. 369. 370. }

int ilength=strlen(str); int i; unsigned char ucChar; if(!ilength) return 0; } if(ilength<=256) { {

urlHashValue=16777216*(ilength-1); } else { urlHashValue = 42781900080; } if(ilength<=96) { for(i=1;i<=ilength;i++) { ucChar=str[i-1]; if(ucChar<='Z'&&ucChar>='A') ucChar=ucChar+32; } urlHashValue+=(3*i*ucChar*ucChar+5*i*ucChar+7*i+11*ucChar)%1677216; } } else { {

for(i=1;i<=96;i++) { ucChar=str[i+ilength-96-1]; if(ucChar<='Z'&&ucChar>='A') { ucChar=ucChar+32; } urlHashValue+=(3*i*ucChar*ucChar+5*i*ucChar+7*i+11*ucChar)%1677216; } } return urlHashValue;

371. /*End Of Tianl Hash Function*/

网上找到的 php 简单实现:
1. 2. 3. 4. 5. 6. /** * Implements a Bloom Filter */ class BloomFilter { <?php

7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50.

/** * Size of the bit array * * @var int */ protected $m;

/** * Number of hash functions * * @var int */ protected $k;

/** * Number of elements in the filter * * @var int */ protected $n;

/** * The bitset holding the filter information * * @var array */ protected $bitset;

/** * 计算最优的 hash 函数个数:当 hash 函数个数 k=(ln2)*(m/n)时错误率最小 * * @param int $m bit 数组的宽度(bit 数) * @param int $n 加入布隆过滤器的 key 的数量 * @return int */ public static function getHashCount($m, $n) { return ceil(($m / $n) * log(2)); }

/** * Construct an instance of the Bloom filter * * @param int $m bit 数组的宽度(bit 数) Size of the bit array * @param int $k hash 函数的个数 Number of different hash functions to use

51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63.

*/ public function __construct($m, $k) { $this->m = $m; $this->k = $k; $this->n = 0;

/* Initialize the bit set */ $this->bitset = array_fill(0, $this->m - 1, false); }

/** * False Positive 的比率:f = (1 – e-kn/m)k * Returns the probability for a false positive to occur, given the current number of items in t he filter

64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93.

* * @return double */ public function getFalsePositiveProbability() { $exp = (-1 * $this->k * $this->n) / $this->m;

return pow(1 - exp($exp), }

$this->k);

/** * Adds a new item to the filter * * @param mixed Either a string holding a single item or an array of * * */ public function add($key) { if (is_array($key)) { foreach ($key as $k) { $this->add($k); } return; } string holding multiple items. In the latter case, all

items are added one by one internally.

$this->n++;

foreach ($this->getSlots($key) as $slot) { $this->bitset[$slot] = true; } }

94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. /** * Hashes the argument to a number of positions in the bit set and returns the positions * * @param string Item * @return array Positions */ protected function getSlots($key) { $slots = array(); $hash = self::getHashCode($key); } return true; } } foreach ($this->getSlots($key) as $slot) { if ($this->bitset[$slot] == false) { return false; } return true; } } /** * Queries the Bloom filter for an element * * If this method return FALSE, it is 100% certain that the element has * not been added to the filter before. In contrast, if TRUE is returned, However with

* the element *may* have been added to the filter previously.

* a probability indicated by getFalsePositiveProbability() the element has * not been added to the filter with contains() still returning TRUE. * * @param mixed Either a string holding a single item or an array of * * strings holding multiple items. In the latter case the

method returns TRUE if the filter contains all items.

* @return boolean */ public function contains($key) { if (is_array($key)) { foreach ($key as $k) { if ($this->contains($k) == false) { return false;

138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. /** }

mt_srand($hash);

for ($i = 0; $i < $this->k; $i++) { $slots[] = mt_rand(0, $this->m - 1); }

return $slots;

* 使用 CRC32 产生一个 32bit(位)的校验值。 * 由于 CRC32 产生校验值时源数据块的每一 bit(位)都会被计算,所以数据块中即使只有一位发生了变化,也会得到 不同的 CRC32 值。

150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. } 163. 164. 165.

* Generates a numeric hash for the given string * * Right now the CRC-32 algorithm is used. Alternatively one could e.g.

* use Adler digests or mimick the behaviour of Java's hashCode() method. * * @param string Input for which the hash should be created * @return int Numeric hash */ protected static function getHashCode($string) { return crc32($string); }

166. $items = array("first item", "second item", "third item"); 167. 168. /* Add all items with one call to add() and make sure contains() finds 169. * them all. 170. */ 171. $filter = new BloomFilter(100, BloomFilter::getHashCount(100, 3)); 172. $filter->add($items); 173. 174. //var_dump($filter); exit; 175. $items = array("firsttem", "seconditem", "thirditem"); 176. foreach ($items as $item) { 177. var_dump(($filter->contains($item))); 178. } 179. 180.

181. /* Add all items with multiple calls to add() and make sure contains() 182. * finds them all. 183. */ 184. $filter = new BloomFilter(100, BloomFilter::getHashCount(100, 3)); 185. foreach ($items as $item) { 186. 187. } 188. $items = array("fir sttem", "secondit em", "thir ditem"); 189. foreach ($items as $item) { 190. var_dump(($filter->contains($item))); 191. } 192. 193. 194. 195. $filter->add($item);

问题实例】 给你 A,B 两个文件,各存放 50 亿条 URL,每条 URL 占用 64 字节,内存限制是 4G,让你找 出 A,B 文件共同的 URL。如果是三个乃至 n 个文件呢? 根据这个问题我们来计算下内存的占用,4G=2^32 大概是 40 亿*8 大概是 340 亿 bit,n=50 亿,如果按 出错率 0.01 算需要的大概是 650 亿个 bit。 现在可用的是 340 亿,相差并丌多,这样可能会使出错率上 升些。另外如果这些 urlip 是一一对应的,就可以转换成 ip,则大大简单了。


大数据常见处理方法总结.doc

大数据常见处理方法总结_计算机软件及应用_IT/计算机_专业资料。大数据常用的处

大数据常见处理方法总结.doc

大数据常见处理方法总结 - 《海量数据处理常用思路和方法》 大数据量,海量数据

十道大数据面试题与十个方法总结.txt

十道大数据面试题与十个方法总结_面试_求职/职场_实用文档。第一部分、十道海量数据处理面试题 1、海量日志数据,提取出某日访问百度次数最多的那个IP。 首先是这...

大数据分析与处理方法解读.doc

大数据分析与处理方法解读_计算机硬件及网络_IT/计算机_专业资料。大数据分析与处理...具体的大数据处理方法其实有很多,但是根据长时间的实践,笔者总结了一个基 本的...

大数据分析和处理的方法步骤.pdf

大数据分析和处理的方法步骤 - 大数据处理数据时代理念的三大转变:要全体不要抽样,要效率不要绝对精 确,要相关不要因果。具体的大数据处理方法其实有很多,但是...

“大数据”解决方式.doc

“大数据”解决方式 - 用学生出现的大量错误来归纳总结,这是大数据的处理方式,也

大数据如何处理?大数据处理方法.pdf

大数据如何处理?大数据处理方法 - 16 年老品牌,上市 IT 培训机构 学大数据,就选光环大数据 官方网站 Hadoop.aura.cn 大数据如何处理?大数据处理方法 无论是...

大数据量的整理方法.doc

大数据量的整理方法 - 大数据量, 大数据量,海量数据 处理方法总结 来源: 葛林华的日志 大数据量的问题是很多面试笔试中经常出现的问题, 比如 baidu google 腾讯...

大数据量,海量数据 处理方法总结.doc

大数据量,海量数据 处理方法总结 - 大数据量的问题是很多面试笔试中经常出现的问题,比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到。 下面的...

大数据量,海量数据 处理方法总结.doc

大数据量,海量数据 处理方法总结 - 大数据量,海量数据 处理方法总结 大数据量的问题是很多面试笔试中经常出现的问题, 大数据量的问题是很多面试笔试中经常出现的...

常用 大数据量、海量数据处理 方法 算法总结.doc

常用 大数据量、海量数据处理 方法 算法总结 - 大数据量的问题是很多面试笔试中经常出现的问题,比如 baidu google 腾讯这样的一些涉 及到海量数据的公司经常会问...

大数据量,海量数据处理方法总结.doc

大数据量,海量数据处理方法总结 - 下面的方法是我对海量数据的处理方法进行了一个

常用大数据量、海量数据处理方法 (算法)总结.doc

常用大数据量、海量数据处理方法 (算法)总结 - ? 大数据量的问题是很多面试笔试中经常出现的问题,比如 baidu goog le 腾讯 这样的一些涉及到海量数据的公司经常...

大数据量,海量数据 处理方法总结.doc

大数据量,海量数据 处理方法总结 大数据量的问题是很多面试笔试中经常出现的问题,比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到。 下面的方法是...

大数据分析与处理方法解读.pdf

大数据分析与处理方法解读 - 大数据分析与处理方法解读 越来越多的应用涉及到大数据,这些大数据的属性,包括数量,速度,多样性等等都是 呈现了大数据不断增长的复杂...

(重点学习)海量数据处理方法总结.pdf

(重点学习)海量数据处理方法总结 - 海量数据处理方法总结 大数据量的问题是很多面试笔试中经常出现的问题,比如 baidu,google,腾讯这样的 一些涉及到海量数据的公司...

大数据知识汇总一.doc

海量数据:数据量太大,导致要么是无法在较短时间内迅速解决,要么是数 据太大...基于此, 大数据分析的方法理论有哪些呢? 大数据分析的五个基本方面 Predictive ...

大数据时代心得体会.pdf

大数据时代心得体会_学习总结_总结/汇报_实用文档。《大数据时代》心得体会信息...大数据更像是理论与现 实齐头并进,理论来创立处理非结构化数据的方法,处理...

电子政务领域的大数据解决思路+-+v1.2-胡书能.pdf

6 电子政务的大数据建设目标 问题分析 解决思路 行业实践 总结 (1)构建政务大...多种挖掘分析方式 ? 分类与回归分析 ? 聚类分析 ? 管理分析 ? 序列分析 ? ...

大数据知识汇总.doc

海量数据:数据量太大,导致要么是无法在较短时间内迅速解决,要么是数 据太大...基于此, 大数据分析的方法理论有哪些呢? 大数据分析的五个基本方面 Predictive ...