毕业设计（论文）--搜索引擎语义排序的研究与实现.docx

搜索引擎语义排序的研究与实现摘 要随着互联网的发展，信息检索的环境正发生着重大变化。而基于搜索引擎的排序算法直接关系到用户在信息检索时的用户体验。搜索引擎基于关键字的检索成为网页文本数据检索的主要方法。首先对基本的网页分析算法进行分析综述：如基于广度优先策略和最佳优先策略的网页抓取方法。页面分析算法可以大到从网页以及网页粒度分析甚至网站粒度分析，还有基于内容的网页分析算法。海量网络信息以使传统通用搜索引擎出现各种局限性。当今主流的网页搜索算法是由引文分析算法发展而来的 PageRank 算法。PageRank算法是当今网络搜索引擎巨匠 Google 的核心技术。本文将对国内外搜索引擎的发展背景进行研究分析。在此基础之上，将对 PageRank 进行深入研究，通过网络链接示意图简单阐述 PageRank 算法的核心，并重点研究计算 Pagerank 值，最后研发一个基于 PageRank 的文献检索系统以便于更好的深入理解和研究 PageRank。首先从传搜索引擎的局限性来提出 PageRank 算法，然后从网页中悬挂节点问题出发，引入网页超链接矩阵，提出一种基于悬挂节点的线性系统来计算 PageRank 值。然后引入基于乘幂法的外推插值方法计算 PageRank 值，它是通过计算齐次方程的特征向量，来计算 PageRank 值，然后从线性系统出发，通过递归方式寻找超链接矩阵中的全零行来计算 PageRank 值。最后，将 PageRank 算法应用于文献检索系统，该系统的客户端是基于 Flex4 的 RIA 应用，后台是基于三层架构的 java 程序。随着 Pagerank 不断成熟，它将在更广的领域发挥更大的作用，越来越方便用户定位自己需要的信息，剔除更多的冗余信息。关键词 搜索引擎；排序；PageRank；Google；特征向量全套设计加扣 3012250582i太原理工大学毕业设计(论文)用纸Research and Implementation of Semantic Search Engine RankingAbstractWith the development of Internet, information retrieval environment is undergoing major changes. Based on the search engine ranking algorithm is directly related to the users experience in information retrieval.The search engine has become the main method Webpage retrieval based on text data retrieval keywords.Firstly, the basic Web page analysis algorithm to analyze summary: if based on the breadth first crawl Web page strategies and best first strategy. Page analysis algorithm can be large sites and even particle size analysis from Webpage and Webpage particle size analysis, and content analysis Web page based algorithm. Massive network of information to the traditional limitations of general search engines there.Todays mainstream web search algorithm is PageRank algorithm algorithm evolved by citation analysis . PageRank algorithm is today the Internet search engine giants Googles core technology. Development of domestic and international background paper will study and analyze the search engine . On this basis , PageRank will conduct in-depth research , sketches briefly discusses the core PageRank algorithm through the network link, and focus on computing Pagerank value of PageRank finally developed a system based on the literature search in order to better understand and study in depth PageRank . First, from the limitations of the search engines to put forward pass PageRank algorithm , then hang from a web page starting node problem , introducing web hyperlink matrix , proposed a suspension of nodes based on linear system to calculate PageRank value. Then calculate the PageRank value by introducing a power law interpolation method based on extrapolation , it is by calculating the eigenvectors homogeneous equation to calculate PageRank value, and then starting from the linear system , look for the hyperlink in the matrix of all zeros line to recursively computing PageRank values. Finally, the PageRank algorithm is applied to document retrieval system, the client of the system is based on Flex4 of RIA applications , the background is based on the three-tier java program .As Pagerank continues to mature,it will play a greater role in the broader field, more and more convenient information users to locate their needs, removing more redundant information.Keywords:search; engine; ranking; PageRank; Google; feature; vectori太原理工大学毕业设计(论文)用纸目录摘要.iAbstract.i1.绪论.11.1研究背景和意义.11.2搜索引擎介绍.11.3研究现状.11.4工作内容及组织结构.11.4.1主要内容.11.4.2论文组织结构.22.PageRank 算法.32.1Pagerank 简介.32.1.1通用搜索引擎的局限性.32.2Pagerank 算法过程步骤.32.2.1基本原理.32.3Pagerank 算法的理解.42.3.1算法描述.42.3.2PageRank 算法简单模型.42.3.3PageRank 算法模型.42.4计算 PageRank 值.52.5计算方法原理.52.6举例说明.52.7算法实现.73. 基于 PageRank 算法的文献检索系统.103.1开发背景.103.2可行性分析.103.2.1技术可行性 .103.2.2经济可行性 .103.2.3操作可行性 .103.2.4法律可行性 .113.3需求分析.113.4概要设计.123.4.1系统流程.123.4.2系统架构.143.5详细设计.143.5.1界面设计.143.5.2数据库设计.183.5.3系统实现.193.6系统测试.283.6.1测试的目的.283.6.2测试方法.291太原理工大学毕业设计(论文)用纸3.6.3测试方案.293.6.4测试总结.30结论.31参考文献.32致谢.332太原理工大学毕业设计(论文)用纸1. 绪论1.1研究背景和意义随着人们生活水平的提高和互联网计算机技术的飞速发展，网民数量不断增加，网络信息不断关联着人们生活的方方面面。此时，单独的一个网民个体就如行驶在广袤无际的大海中的一叶孤舟，很难寻找正确的方向，而这个方向就是在这浩瀚无边的网络世界里找到自己此时所需的信息。1998 年，美国斯坦福大学的博士研究生，也就是后来 Google 创始人之一的 Larry Page 发明的算法 Pagerank，作为 Google 公司的最核心算法，它源于学术论文中引文分析的方法，打破了一般的网络搜索引擎中大多数公司基于的关键字匹配方法，因为后者产生的查询质量往往不尽如人意，Pagerank 则是按照网页的重要性来排序查询结果。笔者认为为提高搜索引擎性能，对 Pagerank 算法进行深入研究是十分必要的。1.2搜索引擎介绍搜索引擎是指根据一定的策略、运用特定的计算机程序从互联网上搜集信息，在对信息进行组织和处理后，为用户提供检索服务，将用户检索相关的信息展示给用户的系统。搜索引擎包括全文索引、目录索引、元搜索引擎、垂直搜索引擎、集合式搜索引擎、门户搜索引擎与免费链接列表等。1.3研究现状主要有两大类页面排序的方法，第一种是基于网页内容分析的排序，另外一种是基于超链接结构分析进行排序。前者源于传统的信息检索，因为互联网中产生海量数据，网页检索对传统信息检索提出巨大难题。Google 公司 2005 年统计显示，它搜索的网页是 24 个 billion，Yahoo 2005 年统计的数据是 20 个 billion。基于链接分析的排序将互联网搜索与传统的信息检索区分开来，从而引发了互联网搜索研究的高潮。Google 创始人 Sergey Bin 和 Lawrence Page 于 1998 年提出的 Pagerank 算法是目前被认为最为成功的一种链接分析方法。1.4工作内容及组织结构1.4.1主要内容本来主要对 web 结构挖掘算法一 PageRank 算法做了详细分析研究,并通过实验，重点研究计算 PageRank 值。(1) 从通用搜索引擎的局限性提出 PageRank 算法，然后从网页中悬挂节点问题出发，1太原理工大学毕业设计(论文)用纸引入网页超链接矩阵，提出一种基于悬挂节点的线性系统。(2) 引入基于乘幂法的外推插值方法计算 PageRank 值，它是通过计算齐次方程的特征向量，来计算 PageRank 值，然后从线性系统出发，通过递归方式寻找超链接矩阵中的全零行来计算 PageRank 值。1.4.2论文组织结构第一章为绪论。主要介绍选题背景和研究现状以及论文的组织结构，引出了本文要研究的主要内容为 PageRank 算法。第二章为 PageRank 算法。首先简介 PageRank 算法，然后介绍 PageRank 算法的理论核心，并通过建立超链接矩阵模型，通过幂乘法求 PageRank 值第三章为基于 PageRank 算法的文献检索系统的工程说明书。第四章为总结与展望。总结本文的研究工作,并展望了未来的研究方向。2太原理工大学毕业设计(论文)用纸2.PageRank 算法2.1Pagerank 简介2.1.1通用搜索引擎的局限性对于全球的普通网民或者网络维护人员或者科研人员来说，Google 都是无可争议的首选搜索引擎，Google 每天需要处理的用户搜索请求次数高达数亿，ComScore 在2009 年5 月的搜索引擎市场数据批露，Google 的市场占有率已经达到65%，雅虎，ask,微软 bing 等远远落后于它,顺便说一下，百度仅仅是在大陆作为中文搜索引擎出现，在全球所占份额远远小于 Google，虽然它现在开始进军日本和韩国市场。这里要提到的局限性就是语言的局限性，英语和汉语，简直是两个无法逾越的文字障碍，这一障碍严重妨碍了搜索引擎在互联网中的作用。传统的搜索工具也有一些无法规避无法解决的问题：(1) 由于汉语的博大精深，一词多义或不同的词被赋予同一含义等等因素，以及不同行业的用户往往有不同的侧重点，这样得到的结果大多数都是无用的。(2) 由于网络正在无限扩张，大量的数据散落在互联网中，通用搜索引擎所在的服务器的计算能力毕竟有限，这样无形中降低了网页抓取范围，犹如逆水行舟，不进则退。(3) 由于页面中的数据格式越来越多，mp3,rm,doc,avi,mp4 等等，而大量信息又会嵌入这里面，目前搜索技术还无法智能区识别这些信息，比如一个名为：2012的电影可能介绍了很多玛雅文化，而这些计算机搜索引擎是无论如何都无法猜到的。(4) 如今搜索引擎都是简单机械识别字面意思，无法深层次去提取语意。2.1.2Pagerank 的介绍互联网发展早期的搜索引擎, 对 Web 页面的排序, 是根据搜索的词组(短语)在页面中的出现次数(Occurence) ,并用页面长度和 HTML 标签的重要性提示等进行权重修订。链接名气(Link Popularity) 技术通过其它文档链接到当前页面(InboundLinks)的链接数量来决定当前页的重要性, 这样可以有效地抵制被人为加工的页面欺骗搜索引擎的手法。PageRank 算法是通过对互联网络超链接拓扑结构的挖掘,获取互联网络中的权威网页, 在用户查询时将相关领域内的权威网页作为查询结果推荐给用户, 提高用户查询的质量。2.2Pagerank 算法过程步骤2.2.1基本原理PageRank 有效地利用了 Web 所拥有的庞大链接构造的特性。例如, 从网页 A 导向网页 B 的链接被看作是对页面 A 对页面 B 的支持投票, Google 根据这个投票数来判断页面的重要性。可是 Google 不单单只看投票数(即链接数) ,对投票的页面也进行分析。重要性高的页面所投的票的评价会更高, 因为接受这个投票页面会被理解为重要的物3太原理工大学毕业设计(论文)用纸品。根据这样的分析, 得到了高评价的重要页面会被给予较高的 PageRank , 在检索结果内的名次也会提高。PageRank 是 Google 中表示网页重要性的综合性指标, 而且不会受到各种检索(引擎)的影响。因此 PageRank 就是基于对使用复杂的算法而得到的链接构造的分析, 从而得出的各网页本身的特性。2.3Pagerank 算法的理解2.3.1算法描述PageRank 是基于从许多优质的网页链接过来的网页, 必定还是优质网页的回归关系,来判定所有网页的重要性。PageRank 在具体实现时会忽略掉 Web 页面上的文本和其它内容, 只考虑页面间的超链接, 把Web 看成是一个巨大的有向图G = (V, E), 结点v 代表一个 Web 页面, 有向边(p,q)代表从结点 p 指向结点 q 的超链接, 结点 p 的出度是指从页面 p 出发的超链接(Outlink)的总数, 而入度是指所有指向结点p 的超链接(Inlink)的总数。设 V 为该有向图结点的集合, N = |V|, Fi 是页面 i 指向的所有页面的集合。对每个出度不为 0 的结点 S, 可以将结点 S 所具有的 PageRank 值均匀地传递给页面集合 FS。2.3.2PageRank 算法简单模型R(u) = R(u)uB(u)| u |Bu = 所有链接到页面 u 的页面|u| = 页面 u 的超链接总数其中 R(u)为网页 u 的 PageRank 值。由此可见, 这个算法不以站点排序, 页面的网页级别由一个个独立的页面决定; 页面的网页级别由链向它的页面的网页级别决定, 但每个链入页面的贡献的值是不同的。如果 Ti 页面中链出越多, 它对当前页面 A 的贡献就越小。A 的链入页面越多, 其网页级别也越高。2.3.3PageRank 算法模型但是, 存在一些网页不链接任何网页, 即此网页的出度(Outdegree)为 0, 这种网页存为摇摆网页(Dangling Web)。摇摆网页的存在将使得递归过程中 Rank 值会比实际值小。解决这个问题的方法很简单, 依据用户虽然在许多场合都顺着当前页面中的链接前进,但时常会跳跃到完全无关的页面里, 这样的随机浏览模型。通常将时常固定为 15%来计算。即用户在 85%的情况下沿着链接前进, 但在 15%的情况下会突然跳跃到无关的页面中去。R(u) = R(u) +（1- c）*(1/ n)uB(u)| u |n 为页面总数。4太原理工大学毕业设计(论文)用纸2.4计算 PageRank 值一般地说为了使得像 Web 那样的超级链接构造能够反映在排列次序上, 需要在计算机上建立超级链接构造的数字模型。但是如果应用图表理论来观察超级链接构造的话,最终常常回到线形代数考虑方法上去。这对于 PageRank 也是一样的。2.5计算方法原理作为最基本的考虑方法, 就是用行列阵的形式来表达链接关系。从页面 i 链接到另一张页面 j 的时, 将其成分定义为 1, 反之则定义为 0。即, 行列阵 A 的成分 aij 可以用, aij = 1 if (从页面 i 向页面 j有链接的情况)0 if (从页面 i 向页面 j没有链接的情况)来表示。文件数用 N 来表示的话, 这个行列阵就成为 NN 的方阵。这个相当于在图表理论中的邻接行列。也就是说, Web 的链接关系可以看作是采用了邻接关系有向图表 S。总而言之, 只要建立了链接, 就应该有邻接关系。PageRank 的行列阵是把这个邻接行列倒置后(行和列互换) ,为了将各列(Column)矢量的总和变成 1(全概率) ,把各个列矢量除以各自的链接数(非零要素数)。这样得到的行列被称为推移概率行列, 含有 N 个概率变量, 各个行矢量表示状态之间的推移概率。倒置的理由是, PageRank 并非重视链接到多少地方而是重视被多少地方链接。PageRank 的计算, 就是求属于这个推移概率行列最大特性值的固有矢量Ax =x这是因为, 当线性变换系 t渐近时, 我们能够根据变换行列的绝对价值最大的特性值和属于它的固有矢量将其从根本上记述下来。换句话说, 用推移概率行列表示的概率过程,是反复对这个行列进行乘法运算的一个过程, 并且能够计算出前方状态的概率。求特性值和固有矢量的值是能够严密分析的一种基础的数学手段。我们能够自由地给矢量的初始值赋值, 但是因为不断地将行列相乘, 得到的矢量却会集中在一些特定数值的组合中。我们把那些稳定的数值的组合称为固有矢量, 把固有矢量中特征性的标量(Scalar)称为特性值, 把这样的计算方法总称为分解特性值, 把解特性值的问题称为特性值问题。2.6举例说明如表 2-1 所示，我们用简单的例子来试着逐次计算 PageRank。首先考虑一下有像下面邻接列表表示的那样的链接关系的 7 个 HTML 文件。并且, 这些 HTML 文件间的链接关系只是闭合于这 17 的文件中。也就是说, 除了这些文档以外没有其它任何链接的出链接源 ID 链接目标 ID 入。5太原理工大学毕业设计(论文)用纸表 2-1 HTML 文件引用关系1234572131242355134661575以这个邻接列表中所表示的链接关系的邻接行列 A 是以下这样的 77 的正方行列。一个仅有要素 0 和 1 位图行列。横向查看第 i 行表示从文件 i 正向链接的文件 ID。A = 0, 1, 1, 1, 1, 0, 1;1, 0, 0, 0, 0, 0, 0;1, 1, 0, 0, 0, 0, 0;0, 1, 1, 0, 1, 0, 0;1, 0, 1, 1, 0, 1, 0;1, 0, 0, 0, 1, 0, 0;0, 0, 0, 0, 1, 0, 0;PageRank 式的推移概率行列M, 是将A 倒置后将各个数值除以各自的非零要素后得到的。即以下这个 77 的正方行列。横向查看第 i 行非零要素表示有指向文件 i 链接的文件 ID(文件 i 的反向链接源)。请注意, 各纵列的值相加的和为 1(全概率)。M = 0, 1, 1/2, 0, 1/4, 1/2, 0;1/5, 0, 1/2, 1/3, 0, 0, 0;1/5, 0, 0, 1/3, 1/4, 0, 0;1/5, 0, 0, 0, 1/4, 0, 0;1/5, 0, 0, 1/3, 0, 1/2, 1;0, 0, 0, 0, 1/4, 0, 0;1/5, 0, 0, 0, 0, 0, 0;表示 PageRank 的矢量 R(各个的页面的等级数的队列),存在着 R=cMR 的关系(c 为定量)。在这种情况下, R 相当于线形代数中的固有矢量, c 相当于对应特性值的倒数。为了求得 R, 只要对这个正方行列 M 作特性值分解就可以了。以上就是 PageRank 的基本原理。Google 做的就是大规模地处理这样的非常特性值问题。6太原理工大学毕业设计(论文)用纸2.7算法实现本算法的核心是使用迭代法求值；迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法，即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。以下是本算法的核心代码（java 源码）：package com.tyut.pagerank.service;public class PageRank/s为初始google矩阵，n为节点数，alpha为阻尼系数public float pageRankTest(float s, int n, float alpha)float q0 = new float n;float q1 = new float n;float e = 0;int iterationCount = 0;/初始化for(int i=0;in;i+)q0i = 1;/中间结果float alpha_s = new float nn; float belta = (1-alpha)/(float)n; float google = new float nn;/alpha*sfor(int i=0;in;i+)for(int j=0;jn;j+)alpha_sij = alpha * sij;/alpha*s+(1-alpha)*u/n 即google矩阵 for(int i=0;in;i+)for(int j=0;jn;j+)googleij = alpha_sij + belta;7太原理工大学毕业设计(论文)用纸System.out.println(按照PageRank算法迭代的过程为：); /迭代求解q1do for(int i=0;in;i+)q1i = 0;for(int j=0;jn;j+)q1i = q1i + q0j*googleij;/输出中间迭代过程for(int i=0;in;i+)System.out.print(第+iterationCount+次迭代：+q1i+);System.out.println();/判断迭代是否收敛e=0;for(int i=0;in;i+)e= e + Math.abs(q0i-q1i);/将求得的q1重新赋给q0for(int i=0;i0.000000001 & iterationCount=50);return q1;/* 归一化处理*/public float normalization(float array) float num = 0;for(int i = 0;i array.length;i+) num += arrayi;for(int i = 0;i array.length;i+) 8太原理工大学毕业设计(论文)用纸arrayi= arrayi/num;return array;9太原理工大学毕业设计(论文)用纸3. 基于 PageRank 算法的文献检索系统3.1开发背景文献检索系统是指根据特定的信息需求而建立起来的一种有关信息搜集、加工、存储和检索的程序化系统，其主要目的是为人们提供信息服务。而文献检索结果的排序直接影响到系统的用户体验，并且，文献之间的参考也是基于一个网络拓扑的，所以将 PageRank 算法应用于文献检索中是十分必要的，也是可行的。3.2可行性分析可行性研究是在项目开发前期对项目的一种考察和鉴定，对拟议中的项目进行全面的、综合的调查研究，其目的是要判断项目可行与否。信息系统技术可行性研究要从系统开发的计划出发，论述系统开发力量的可行性，同时论证系统方案中所采取的各种技术手段上是否可以实现。信息系统经济可行性研究主要是对项目进行经济评价，分析系统建设投资的可能性以及评价系统运行之后给组织带来的效益。信息系统营运可行性研究要给出的方案是否可以从人力、物力、组织工作等方面保证项目按计划完成实施，还要说明项目开发后在经济、技术和环境等方面能否保证系统正常运行。由于系统建设是一项投资大、涉及面广、工程复杂的系统工程，因此必须充分的进行可行性论证，以确保投资的准确无误，而且信息系统建设是一项整体工程，必须站在系统的角度论证它的可行性才有说服力，才有意义。可行性研究的目的是用最小的代价，在尽可能短时间内确定问题是否能够解决，它的目的不是解决问题，而是确定问题是否值得去解决，可行性从以下四个方面来考虑。3.2.1技术可行性该系统是基于 PageRank 的 RIA 应用，在对 PageRank 算法做了深入的理解分析后，从技术上来说，开发这个系统的技术难题是不多的。3.2.2经济可行性本系统是自主研发的，经济成本可忽略不计。3.2.3操作可行性参照其它的系统，该系统在技术上完全可以实现与用户的良好交互作用，并且作为开发者，我也尽可能地减少让用户难以操作或是难以理解的交互方式。10太原理工大学毕业设计(论文)用纸3.2.4法律可行性本系统开发不会侵犯他人、集体或国家利益，不存在侵权等问题，不违反国家法律，因此具有法律可行性。综上所述，从技术上、经济上、法律上、可操作性上都是可行的,而且要求不高，所以该系统的开发是可行的。3.3需求分析传统网络程序的开发是基于页面的、服务器端数据传递的模式，把网络程序的表示层建立于 HTML 页面之上，而 HTML 是适合于文本的，传统的基于页面的系统已经渐渐不能满足网