一. 搜索引擎常用结构:
就是如下图所示的三段式结构:
image.png
1.数据收集:通过爬虫(spider)从互联网网页爬取网页数据,存储到网页库;
2.建立索引:分析整理爬虫收集到的数据资源,建立索引,为检索系统提供数据;
3.提供检索服务:从预处理好的资源里挑选出用户最满意的结果最快最好的展现给用户;
二. 基于Hadoop MapReduce实现创建索引库的流程如下:
image.png
1. 目的: 建立供检索使用的索引和摘要
2. 输入: 网页
3. 输出: 索引和摘要
4. 处理: 多轮map-reduce
5. 页面分析和处理(parser-extractor)
6. 页面属性小库输出(splitter)
此时产生的是正排索引结构,比如:
关于三亚的旅游网页url --> 三亚,旅游,阳光,沙滩等索引
7. 小库正排转倒排(invert-index)
就是将上面的对应关系进行反转:
三亚 --> 关于三亚的旅游网页url1
旅游 --> 关于三亚的旅游网页url1
阳光 --> 关于三亚的旅游网页url1
沙滩 --> 关于三亚的旅游网页url1
8. 小库合并成大库(index merge)
一个索引可以指向多个url网页,所以需要进行合并操作,而合并操作时就涉及到快速判重的问题.
针对大数据量的快速判重这里有一种很好的解决方案就是布隆过滤器(Bloom Filter).
布隆过滤器使用BitMap算法,它由一个很长的二进制向量和一系列随机映射函数组成,可以用于检索一个元素是否在一个集合中.当数据量大且密集时,该方法的空间效率和查询效率都远超一般的算法.
image.png
