- 快捷搜索
- 全站搜索
布隆过滤器（Bloom Filter）的基本思想是：当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是l，则被检元素很可能在。
布隆过滤器在空间和时间方面都有巨大的优势：
（1）在复杂度方面，布隆过滤器存储空间和插入／查询时间都是常数（即复杂度为O(k)）；
（2）在关系方面，散列函数相互之间没有关联关系，方便由硬件并行实现；
（3）在存储方面，布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
布隆过滤器的具体实现方法是，已经抓取过的每个URL，经过k个hash函数的计算，得出k个值，再和一个巨大bit数组的这k个位置的元素对应起来（这些位置数组元素的值被设置为1）。在需要判断某个URL是否被抓取过时，先用k个hash函数对该URL计算出k个值，然后查询巨大的bit数组内这k个位置上的值，如果全为l，则是已经被抓取过，否则没有被抓取过。
三、数据处理的基本流程与关键技术
1．数据处理的整体框架
数据处理的整个过程如图3所示，主要包括四个模块：分词（Words Analyze）、排重（Content Deduplicate）、整合（Integrate）和数据。
这四个模块的主要功能如下。
分词：对抓取到的网页内容进行切词处理。
排重：对众多的网页内容进行排重。
整合：对不同来源的数据内容进行格式上的整合。
数据：包含两方面的数据，Spider Data（爬虫从网页中抽取出来的数据）和Dp Data（在整个数据处理过程中产生的的数据）。
2．数据处理的基本流程
整个数据处理过程的基本步骤如下：
（1）对抓取来的网页内容进行分词；
（2）将分词处理的结果写入数据库；
（3）对抓取来的网页内容进行排重；
（4）将排重处理后的数据写入数据库；
（5）根据之前的处理结果，对数据进行整合；
（6）将整合后的结果写入数据库。
3．数据处理的关键技术——排重
排重就是排除掉与主题相重复项的过程，网页排重就是通过两个网页之间的相似度来排除重复项。Simhash算法是一种高效的海量文本排重算法，相比于余弦角、欧式距离、Jaccard相似系数等算法，Simhash避免了对文本两两进行相似度比较的复杂方式，从而大大提高了效率。
采用Simhash算法来进行抓取网页内容的排重，可以容纳更大的数据量，提供更快的数据处理速度，实现大数据的快速处理。图4是Simhash的算法思路。
Simhash算法的基本思想描述如下：
输入为一个N维向量V，比如文本的特征向量，每个特征具有一定权重。输出是一个C位的二进制签名S。
（1）初始化一个C维向量Q为0，C位的二进制签名S为0。
（2）对向量V中的每一个特征，使用传统的Hash算法计算出一个C位的散列值H。对l<=i<=C，如果H的第i位为1，则Q的第i个元素加上该特征的权重；否则，Q的第i个元素减去该特征的权重。
（3）如果Q的第i个元素大于0，则S的第i位为l；否则为0。
（4）返回签名S。
对每篇文档根据SimHtash算出签名后，再计算两个签名的海明距离（两个二进制异或后l的个数）即可。根据经验值，对64位的SimHash，海明距离在3以内的可以认为相似度比较高。
4．数据处理的关键技术——整合
整合就是把抓取来的网页内容与各个公司之间建立对应关系。对于每一个公司来说，可以用一组关键词来对该公司进行描述，同样的，经过dp处理之后的网页内容，也可以用一组关键词来进行描述。因此，整合就变成了两组关键词（公司关键词，内容关键词）之间的匹配。
对于网页内容的分词结果来说，存在着两个特点：（1）分词结果的数量很大；（2）大多数的分词对描述该网页内容来说是没有贡献的。因此，对网页的分词结果进行一下简化，使用词频最高的若干个词汇来描述该网页内容。
经过简化之后，两组关键词的匹配效率就得到了很大的提升，同时准确度也得到了保障；经过整合之后，抓取来的网页内容与公司之间就建立了一个对应关系，就能知道某个具体的公司有着怎样的数据了。
（文章来源：《中国金融电脑》杂志）
2013年下半年，余额宝看似“暴发户”式的成功造成了银行领域的极大震动，大
商业银行只有从打造数据化能力做起，让数据转化为对业务产生洞察的信息，才