中文信息处理报告课题名称搜索引擎中的关键技术及解决学院（系）电子信息与工程学院专业计算机科学与技术学号072337学生姓名张志佳完成时间2009年1月 3 日目前，国内的每个行业，领域都在飞速发展，这中间产生了大量的中文信息资源，为了能够及时准确的获取最新的信息，中文搜索引擎应运而生。

中文搜索引擎与西文搜索引擎在实现的机制和原理上大致相同，但由于汉语本身的特点，必须引入对于中文语言的处理技术，而汉语自动分词技术就是其中很关键的部分，也是进行后续语义或者是语法分析的基础。

汉语自动分词到底对搜索引擎有多大影响？对于搜索引擎来说，最重要的并不是找到所有结果，最重要的是把最相关的结果排在最前面，这也称为相关度排序。

中文分词的准确与否，常常直接影响到对搜索结果的相关度排序。

分词准确性对搜索引擎来说十分重要，但如果分词速度太慢，即使准确性再高，对于搜索引擎来说也是不可用的，在Internet上有上百亿可用的公共Web页面，如果分词耗用的时间过长，会严重影响搜索引擎内容更新的速度。

因此对于搜索引擎来说，分词的准确性和速度，都需要达到很高的要求。

更具体的说，现在的搜索引擎要达到下面的三要求，才能适应当今这样一个信息爆炸的时代，分别是：数据量达到亿，单次查询毫秒级，每日查询总数能支持千万级。

撇开搜索引擎要用到的数量庞大的服务器硬件和速度巨快的网络环境不提，就单单说说搜索引擎中软件部分的三大核心技术。

我个人以为：一个优秀的搜索引擎，它必需在下面三个方面的技术必须是优秀的：中文分词，网络机器人（Spider）和后台索引结构。

而这三方面又是紧密相关的，想要解决中文分词问题，就要解决搜索时间和搜索准确率两方面的难题。

而搜索时间上便是通过网络机器人（Spider）和后台索引结构的改进实现的，搜索准确率则是通过分词本身算法的求精来实现的。

下面的文章将从这两个大的方面来解决这两方面的问题。

为了能够更清楚的来说明现在的搜索引擎是如何解决这几个难题的，首先对搜索引擎的组成及工作原理在这里简要的说明一下。

搜索引擎的工作，可以看做三步：从互联网上抓取网页，建立索引数据库，在索引数据库中搜索排序。

从互联网上抓取网页利用能够从互联网上自动收集网页的Spider系统程序，自动访问互联网，并沿着任何网页中的所有URL爬到其它网页，重复这过程，并把爬过的所有网页收集回来。

下面是搜索引擎的工作原理图：Array搜索引擎工作原理图1搜索引擎工作原理图中的相关术语说明如表1：表1一，搜索引擎中的关键技术介绍在介绍关于搜索引擎中的分词技术是如何解决的，相对搜索引擎中其它的一些关键技术做一下简要的介绍，对谈一下自己对相关技术的一些想法。

其实这些技术和中文分词技术是很有关联性的。

可能给你一片几千字的文章，让你对它进行分词可能你通过编编程序便可以实现，但是搜索引擎要解决的问题是怎样去处理互联网中海量的，且没有规则的信息，要解决的问题就不仅仅是简简单单的分词问题了，可以说下面要介绍的一些关键技术正是分词技术的一个基础，是为分词建立一个良好的搜索环境和数据结构。

1，网络机器人（Spider）的设计为了保证搜索到的信息的实时性与相关性，就要保证在互联网上面搜到的网页获取的很及时。

并且对于互联网上面现在已经有几十亿的网页进行处理，必然要选择一种很好的方法才可以。

搜索引擎是通过两种方式来获得互联网上面的Web页面的，一种是定期（比如Google一般是28天）派出Spider（蜘蛛）程序，抓取网络上面的新页面，将相关的信息记录在数据库中。

另一种方式是网站的拥有者向搜索引擎提交网址信息，同样将相关的信息记录到数据库中。

而上面所说的Spider（蜘蛛）程序，是一种专业的Bot程序，是一个功能很强的Web 扫描程序。

它可以在扫描Web页面的同时，检索相应的超链接并加入扫描队列等待以后的扫描。

我们知道网络上面的超链接的使用是很普遍的，因此一个Spider程序理论上可以扫描互联网上的所有页面。

比如搜索巨头Google公司，就利用网络机器人程序来遍历Web 站点，并实时的更新已经建立的数据库。

从中我们也不难看出，一个网页抓取程序（即Spider）设计的好坏对搜索引擎的性能的影响是很大的。

Spider程序结构网络机器人必须从一个网页迁移到另一个网页，所以必须找到该页面上的超连接。

程序首先解析网页的HTML代码，查找该页面内的超连接然后通过递归和非递归两种结构来实现Spider程序。

非递归结构方法使用队列的数据结构，当Spider程序发现超连接后并不调用自己本身而是把超连接加入到等待队列中。

当Spider程序扫描完当前页面后会根据制定的策略访问队列中的下一个超连接地址。

虽然这里只描述了一个队列，但在实际编程中用到了四个队列，他们每个队列都保存着同一处理状态的URL。

等待队列：在这个队列中，URL等待被Spider程序处理。

新发现的URL也被加入到这个队列中。

处理队列：当Spider程序开始处理时，他们被送到这个队列中。

错误队列：如果在解析网页时出错，URL 将被送到这里。

该队列中的URL 不能被移入其他队列中。

完成队列：如果解析网页没有出错，URL 将被送到这里。

该队列中的URL 不能被移入其它队列中。

Spider 程序的非递归处理过程以上的图表示了队列的变化过程，在这个过程中，当一个URL 被加入到等待队列中时Spider 程序就会开始运行。

只要等待队列中有一个网页或Spider 程序正在处理一个网页，程序就会继续他的工作。

当等待队列为空并且当前没有任何网页时，Spider 程序就会停止它的工作。

2，索引数据库设计技术大型搜索引擎的数据库储存了互联网几十亿的网页索引，数据量达到几千个G 甚至几万个G 。

为了充分的为后面考虑在后面查询中能够跟快捷，更准确。

搜索引擎在分析索引系统程序对收集回来的网页进行分析，提取相关网页信息，根据一定的相关度算法进行大量复杂计算，得到每一个网页针对页面内容中及超链中每一个关键词的相关度，然后用这些相关信息建立网页索引数据库。

当用户输入关键词搜索后，由搜索系统程序从网页索引数据库中找到符合该关键词的所有相关网页。

因为所有相关网页针对该关键词的相关度早已算好，所以只需按照现成的相关度数值排序，相关度越高，排名越靠前。

最后，由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。

3，网页评级（PageRank ，HillTop ）技术由于互联网上面的Web 页面的数据量大，用传统的方法来确定检索表达式和网页的相关度会花太多的时间，不能够满足用户的需求。

采用网页评级技术可以保证系统能够快速的反应，并把重要的的网页返回给用户。

Google 每天要处理的网页高达2亿次，占全球的搜索量的1/3。

Google 却能够提供快速的搜索速度和高命中率搜索结果，完全取决于它所使用的复杂的文本匹配算法及其搜索程序所使用的Pagerank 技术。

Pagerank 技术是用来计算页面的重要性，对于每一个链入赋予不同的权值，链接提供的页面越重则此链入权值就越高，也就是说当前页面的重要程度是由其他的页面来决定的。

下面是PageRank 的算法：∑=+-=+++-=n i Ti C Ti PR d d Tn C Tn PR T C T PR d d A PR 1)()()1()(/)())1(/)1(()1()(其中，PR(A)是页面A 的级别，PR(Ti)是页面Ti 的级别，页面Ti 链向页面A ，C(Ti)是页面Ti 链出的链接数量，d 是阻尼系数，取值在0～1之间。

从这个公式，我们可以直观的描述：一个来自PageRank 3拥有7个外向链接页面上的链接，要比一个PageRank9拥有200个外向链接页面上的链接，更有价值。

链接到你网页的页面的PageRank 非常重要，不过其页面上链接的个数同样重要。

一个网页上的链接数越多，你所能够从这个网页获取的价值就越少。

从上面的式子可以看出来，当要计算某个页面的网页级数时，由于互联网上面的页面几乎都是可以相互链接的，因此要得到某一个页面的网页级数，就要即一个超大维数的方程组。

这对于现在的计算机的性能来说，完全是不现实的。

Google 采用的是一种近似的迭代方法来计算网页的级别，也就是先给每一个网页一个初值，然后在调用上面的公式，循环进行运算来得到网页的级别。

根据研究实际要进行100次的迭代才能得到整个互联网满意的页面级别值。

不过前面已经说过搜索引擎在获取网页时是定期的，所以总的来说这种方法在现在的Web 搜索来说还算可以。

下面的一种图片便是用Pagerank 算法来进行对网页评级的一个结果。

从中我们也不难发现像Google 这样的大型热门网站获得网页级别是处在金字塔的顶端的，Swingline 等网站获得的网页级别就比较低。

图1 Pagerank 算法对网页评级的结果但是这种方法也并不是完善的，当你仔细的思考一下，就会发现，在互联网中，像Google ，百度这样的热门网站中，会在很多的网站中都有链接。

但你在查询框中查询“篮球”时，就会有很多这样不相关的网页指向它，从而得到较高的级别。

而事实上他们与“篮球”不太相关，而对于这种特俗的情况，我们可以在上面的计算公式中添加一些限制因素，来避免这种情况的出现。

比如在计算是可以将链入的的网页的内容和本网页进行匹配一下，根据相关程度来决定这种链入是否有效。

通过对由超过50，000万个变量和20亿个词汇组成的方程进行计算，PageRank 能够对网页的重要性做出客观的评价。

使得在对互联网中海量的Web网页的搜索节省了时间，同时也使得搜索的结果更接近用户的期望值。

从上面的分析中我们也看到Pagerank算法仍然存在着不足。

近几年来也有一些新的排名算法出现，比如HillTop算法，它集成了Pagerank，HITS，相关性算法的优点于一身，是Google核心排名算法之一。

HillTop算法是一种查询相关性链接的分析算法，它克服了的Pagerank的查询无关性的缺点。

简单的说HillTop算法是针对热门查询词来对Web网页进行重新排序的技术。

而只针对热门关键词，是因为HillTop算法运行效率较比较低的限制。

我们可以看到HillTop算法通过不同等级的评分确保了评价结果对关键词的相关性，通过不同位置的评分确保了主题的相关性，通过可区分短语数量防止了关键词的堆砌。

在HillTop算法中存在着一种博弈的思想，在链接方面同类型的网站时，既需要竞争又需要合作，只有被对方“认可”的网站，对热门关键关键词的查询才会被排在搜索结果的前面。

HillTop使得那些小的网站不能够在此便处于劣势，除非你对热门关键词能够提前预知出来，然而即使预制出来了，这种持续也会很短。