排序优化的 木棉搜索引擎
郭立山 蔡斌 欧健文
华南理工大学 信息网络工程研究中心
系统需求 系统设计
整体设计 原始数据分析 Pagerank 索引 搜索
搜索结果
主题搜索 导航搜索
总结
系统需求
功能需求: 将90G的天网原始数据进行索引、排序, 然后再根据给出的关键字搜索出相匹配的网页. 性能需求:要求在10天内完成对90G数据的索引、 排序和搜索. 所以,本搜索引擎的关键之处在于索引算法、排 序算法、搜索算法、数据存储方式和并行设计.
系统需求 系统设计
整体设计 原始数据分析 Pagerank 索引 搜索
搜索结果
主题搜索 导航搜索
总结
整体设计
针对系统需求中提到的关键点,分别采用了以下设计: 索引算法:采用Lucene全文索引系统,进行单字索引. 排序算法:根据Pagerank算法 各网页的得分;根据关键字 匹配度、内容重要性等 得分; 搜索算法:采用整词搜索、分词搜索、二次搜索等提高精确性. 数据存储方式:采用Berkely DB的数据存储格式,提高I/O效率. 并行设计:支持多线程数据分析、分布式索引和分布式搜索.
系统流程
系统需求 系统设计
整体设计 原始数据分析 Pagerank 索引 搜索
搜索结果
主题搜索 导航搜索
总结
原始数据分析
天网原始数据以文件形式存储，每个文件包 含若干个网页记录。每个记录的格式是严格定义 的。因此能很方便地提取出天网抓取的原始网页 内容。 原始数据分析器采用多线程，以提高分析效 率。对于每个原始网页，提取其url、网页内的链 接url和链接文字、去除tag标记后的网页内容， 并记录每个网页在文件中的具体偏移位置。
所有输出数据都以Berkely DB的格式存储，以节省 I/O开销。 链接数据库：通过提取网页内的链接url生成的， 记录各URL之间的链接关系，用于 Pagerank。 网页数据库：记录了每个网页的pagerank得分值等 一些属性。 标题、链接文字内容：用于文本索引。 去掉tag标记的网页内容： 用于文本索引。两者权 重不同。
系统需求 系统设计
整体设计 原始数据分析 Pagerank 索引 搜索
搜索结果
主题搜索 导航搜索
总结
 Pagerank
Pagerank的核心思想即是当前页的重要性，是由其 链入页面的数量以及链入页面的重要性决定的。 其计算公式为： PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) 其中：PR(A):页面A的pagerank得分, PR(Ti)：页面Ti的pagerank得分，页面Ti链向页面A， C(Ti)：页面Ti链出的链接数量， d：阻尼系数，取值在0－1之间.
 Pagerank的步骤如下： 1)所有网页的Pagerank得分值都赋初始值 2)遍历网页数据库。对于每一个页面，通过查 找链接数据库，得到当前页面所有的链出页 面。再将当前页面的Pagerank得分值平分 给每个链出的页面。 3)重复步骤2，迭 次，直至收敛。 对于90G的天网数据，由于其之间的网 页链接关系比较松 大概迭代5次，可以 得到比较合理的Pagerank得分。
系统需求 系统设计
整体设计 原始数据分析 Pagerank 索引 搜索
搜索结果
主题搜索 导航搜索
总结
索引
直接采用开源代码Lucene提供的API，对文本进行索 引。 Lucene是基于关键词搜索的一种倒索引，有几个核 心概念： 索引是一系列文 Document）的集合 文 一系列字段（Field）的集合 字段是一系列术语（Term）的集合 术语则是字符串，它可以是单字，可以是标准词 库中的词语等。

下一页