基于分块链接的网页排序并行算法设计与实现

摘要

网页和纯文本的结构差异性决定了传统的信息检索排序算法不能完全适应网络发展，基于链接分析的网页排序算法便应运而生，并成为现代搜索引擎的关键技术。知名的搜索引擎公司在对搜索结果进行排序时，基本都融合了基于链接分析的排序结果，例如谷歌(Google)使用了著名的PageRank算法，而百度(Baidu)也有自己的链接分析技术。
　　本文通过对经典的网页链接排序算法PageRank和HITS的研究学习，发现传统的PageRank算法只考虑网页之间的链接关系而忽略了网页正文和链接文本的重要性，同时传统的PageRank算法将网页中的链接看作是互不相关的，而实际上网页中的链接通常是以分块的形式存在，分块内的链接在语义和功能上具有很大的相似性。因此本文通过提取网页中的分块链接，引入了分块链接的链接文本与网页正文的相似度，根据该相似度值赋予每个链接不同的权重来实现对PageRank算法的改进。并设计并行的改进PageRank算法，来适用于机群环境。
　　本文的主要研究内容如下：
　　(1)通过分析原始网页，建立网页的DOM树来提取出网页中的分块链接，并使用空间向量模型来计算分块链接中的链接文本与网页正文的相似度，在此基础上实现对经典PageRank算法的改进；
　　(2)设计实现了并行的改进PageRank算法，以便能使用机群来计算每个网页改进的PageRank值；
　　(3)将计算出的改进PageRank值应用于Inar搜索引擎，模拟用户的输入，对经典PageRank算法和改进PageRank算法的排序结果进行分析比较，证明了改进算法的高效与有效性。
　　最后，本系统已成功应用在Inar搜索引擎中。通过实验表明，本文所做研究的内容，有效的提高了Inar搜索引擎性能，达到了很好的预期效果。

目录

基于分块链接的网页排序并行算法设计与实现

DESIGN AND IMPLEMENTATION OF BLOCK-LEVEL LINK BASED PARALLEL WEB PAGE RANKING ALGORITHM

摘 要

Abstract

绪论

1.1 课题背景

1.2 本课题研究的目的及意义

1.3 国内外相关技术发展现状

1.3.1 搜索引擎相关技术介绍

1.3.2 网页链接排序算法研究现状

1.3.3 网页分块提取技术研究现状

1.3.4 并行处理技术的发展现状

1.4 本文主要研究内容及组织

并行网页排序相关技术

2.1 引言

2.2 分块链接提取技术

2.2.1 分块链接介绍

2.2.2 网页结构的提取

2.2.3 网页链接的特点

2.3 链接排序算法

2.3.1 PageRank算法

2.3.2 HITS算法

2.3.3 PageRank算法和HITS算法比较

2.4 并行计算技术

2.4.1 并行体系结构介绍

2.4.2 主要并行编程模型

2.4.3 MPI技术

2.5 本章小结

并行网页排序系统的设计

3.1 系统的设计目标

3.2 系统总体设计

3.3 分块链接的提取和存储

3.3.1 分块链接提取

3.3.2 url的语法解析过滤

3.3.3 网页链接的存储

3.3.4 并行分块链接提取

3.4 改进的PageRank算法

3.5 网页排序并行算法设计与实现

3.5.1 串行的改进PageRank算法

3.5.2 并行的改进PageRank算法的设计

3.6 本章小结

实验结果与分析

4.1 引言

4.2 实验环境

4.3 分块链接提取实验

4.3.1 网页分块的提取

4.3.2 链接的提取

4.3.3 并行分块链接提取

4.4 并行的改进PageRank算法实验

4.4.1 并行算法的效率

4.4.2 排序结果的准确性

4.5 本章小结

结 论

参考文献

攻读学位期间发表的学术论文

哈尔滨工业大学硕士学位论文原创性声明

哈尔滨工业大学硕士学位论文使用授权书

致 谢