（计算数学专业论文）互联网信息搜索排序算法研究——统一开放的排序公式.pdf

摘要 当前的互联嘲已经达到数十亿网页的规模，并且正在以每r 数百万恻页的海 量速度增长。由于其规模如此之庞大的，用户在查洵资料的时候，经常面对搜索 引擎所返回的几千甚至几万个嘲页，用户很难准确找到自己所需要的内容。冈此， 搜索引擎如何优化搜索和排序算法，如何在解决搜索速度和查全率的基础上，提 高查准率，并且把最恰当的，最可信的链接放在返回结果的最前面成为互联删搜 索的关键问题。 本文分析了现有的互联网搜索和排序算法，特别是深入探讨了当前排序算法 中的相关度分析和链接分析的优缺点，也研究了网络蜘蛛的算法和中文分词技术 的应用。存此基础上，本文提出了统一丌放的排序公式。该公式把小同的排序算 法整合在一起，用户可以根据不唰的搜索要求动态调整排序算法，解决当前排序 算法的互不兼容刚题。本文在最后给出了该公式的一个简单的心用实例。 关键词：搜索引擎、排序算法 a b s t r a c t t h ew o r l dw i d ew e b ( w 脚) i ss t i l le x p e n d i n ga tar a t eo fm i l l i o n sp a g e s p e rd a yw h i l et h e r e a r eb i l l i o n so fp a g e sa 1r e a d y b e c a u s eo fi t sh u g e s i z e ，w e bu s e r so f t e nc a n n o tf i n dp r e c is e l yw h a tt h e ya r es e a r c h i n gr o r w h e nf a c in go v c r w h e l m i n gn u m b e r so fp a g e sr e t u r n e db ys e a r c he n g i n e t h e r e f o r e ，i tb e c o m e sav i t a lp r o b l e mf o rs e a r c he n g i n e st oo p t i m i z e s e a r c h i n gt h ew w wa n ds o r t i n gt h er el u r n e dr e s u l t s ，w h i c hi n c l u d e sis s u e s o ft h es e a r c hs p e e d ，m i s s i n gr e s u l t sv s t h ew h o l er e s u ls e l ，a c c u r a c y ， t h eq u a l i t vo ft h ep a g e sr e t u r n e df i r s t t h i se s s a ya n a l y z e st h e1 w ws e a r c ha n dr e s u lt s o r t i n ga l g o r it h m so f t o d a y ，e s p e c ia l1 yt h a to fr e l a t i v i t ya n dl i n ka n a l y s e s t h i sp a p e ra ls o d i s c u s s e st h ea l g o r i t h m so f w e bs p i d e r sa n dt h et e c h n i q u et os p l i tw o r d i nc h i n e s e f u r t h e r m o r e ，t h i sp a p e rp r e s e n t sag e n e r a lf o r m u l at oc o m b i n e t h e s ea l g o r i t h m st o g e t h e rf o ru s e r st oc h a n g er e s u l ts o r t i n ga l g o r it h m d y n a m i e a ll ya c c o r d i n gt od ir f e r e n ts e a r c hr e q u i r e m e n t s o n ea p p i i c a t i o n e x a m p l eo ft h i sf o r m u l ai sa l s op r e s e n t e d k e y w o r d ：s e a r c he n g i n e ，s o r ta l g o r i t h m s 第一章绪论 1 1 互联网搜索排序算法研究的意义 当前的互联网已经达到数f 亿网页的规模，并且j f 在以每八个月增加一倍 的速度增长。由_ 丁其规模如此之庞大的，用户在查询资料的时候，经常面对搜 索引擎所返回的几千甚至几万个刚页的链接( 根据加州m o u n t a i nv w 2 0 0 4 年2 月1 7 口的报导，著名的搜寻引擎g o o g l e 索引了4 2 8 亿网页，8 8 亿幅图， 8 4 5 亿个论坛信息，共6 0 亿项) ，而当用户点击这些链接后发现： 1 ) 某些网页的确包含用户输入的搜索词，可是嘲页的主题并非是相关的， 例如用户输入“老虎”，结果进入“老虎队”的网负。某些不道德的嘲 页甚至会在不可见的区域增加一大堆热门词汇，从而引诱用户进入他们 的网页。 2 ) 某些网页早己更新，并非用户查洵的主题甚至此网页已不存在。 3 ) 某些网页的信息己十分陈旧，已失去意义。 4 ) 某些刚页确有用广所需要的资料，但足质量十分差，如内容不可信，作 者水平低；或并非用户所要的层次，如用户在做博士研究时查到初级的 资料。 人们当然期望他们所点击的最初若干链接最能满足他们的需要。对搜索引 擎来说，如何在解决搜索速度和查全率的基础上，提高查准率，优化查询结果， 把最恰当的，最可信的链接放在返回结果的最前面成为最关键的问题。因此， 对搜索引擎的搜索和排序算法进行深入的研究，具有i 分重要的意义。 1 2 搜索引擎发展史 1 9 9 0 年以前，没有任何人能搜索互联删。 所有搜索引擎的祖先，是1 9 9 0 年由m o n t r e a l 的m c g i l l 大学的学生a l a ne m t a g e 等发明的a r c h i e 。虽然当时w o r l d w i d e w e b 还未出现，但网络中文件传输还是相 当频繁的，由于大量的文件散布在各个分散的f 1 甲丰机巾，查询起来非常不便， 因此a l a ne m t a g e 等想到了开发1 个可以用文件名查找文件的系统，f 是便有了 a r e h i e 。a r c h i e 是第一个自动索引互联网 ：匿名f r p 网站文件的程序，但它还不 是真正的搜索引擎。 1 9 9 3 年，匠联嘲卜出现了最早的w e b 浏览器m o s a i c ，次年n e t s c a p e 推m 了 n a v i g a t o r 。浏览器的发展促使w e b 得到迅速推广，站点数r 以惊人的速度增加， 人们再也彳i 能用传统记忆方式来应付与只俱增的站点。为此，人们在w w w 搜索 弓1 擎巾引入了c o m p u t e rr o b o t 技术。c o m p u t e rr o b o t 是某个能以人类无法达到的 速度不断重复执行某项任务的自动程序。由于专门用于检索信息的r o b o t 程序象 蜘蛛( s p i d e r ) 群在刚络间爬来爬去，因此，搜索引擎的r o b o t 程序被称为s p i d e r 程序。世界卜第一个s p i d e r 程序，是m 玎的w w w w a n d e r e r ，用于追踪互联网 发展规模。刚开始它只用来统计互联网上的服务器数量，后来则发展为也能够捕 获网址( u r l ) 。 随着互联网的迅速发展，使得检索所有新出现的网页变得越来越困难，凶此， 在w a n d e r e r 基础上，一些编程者将传统的s p i d e r 程序工作原理作了些改进。其设 想是，既然所有网页都可能有连向其他网站的链接，那么从一个网站开始，跟踪 所有网页上的所有链接，就有可能检索整个互联网。至1 j 1 9 9 3 年底，一些基于此原 理的搜索引擎开始纷纷涌现，其中最负盛名的是s c o t l a n d 的j u m p s t a t i o r t r 。 1 9 9 4 年4 月，s t a n f o r d 大学的两名博士生，美籍华人杨致远和d a v i df i l o 共同创 办了y a h o o 。随着访问量和收录链接数的增长，y a h o o 目录开始支持简单的数据 库搜索。因为y a h o o ! 的数据是手工输入的，所以不能真正被归为搜索引擎，事实 上只是一个可搜索的目录。w a n d e r e r 只抓取u r l ，但u r l 信息含量太小，很多信 息难以单靠u r l 说清楚，搜索效率很低。y a h o o ! 中收录的网站，因为都附有简介 信息，所以搜索效率明显提高。 1 9 9 4 年春天，l y c o s 的出现是搜索引擎史上又一个重要的进步。它将s p i d e r 程 序接入到其索引程序中，除了相关性排序外，l y c o s 还提供了前缀匹配和字符相 近限制，l y c o s 第一个在搜索结果中使用了网页自动摘要，而最大的优势还是它 远胜过其它搜索引擎的数据量。 1 9 9 5 年，出现了一种新的搜索引擎形式元搜索引擎。用户只需提交一次 搜索请求，由元搜索引擎负责转换处理后提交给多个预先选定的独立搜索引擎， 并将从各独立搜索引擎返回的所有查询结果，集中起来处理后再返回给用户。可 惜到目前为止，元搜索引擎实际的搜索效果还是没能超过链接分析。 1 9 9 5 年1 2 月才登场亮相的a l t a v i s t a 是第一个支持自然语言搜索的搜索引擎， 也是第一个实现高级搜索语法的搜索引擎，它第一次改变了搜索引擎的定义。 1 9 9 8 年9 月g o o g l e 公司正式成立，g o o g l e 在p a g e r a n k 、动态摘要、网 页快照、d a i l y r e f r e s h 、多文档格式支持、地图股票词典寻人等集成搜索、多语 言支持、用户界面等功能上进行革新，以其搜索准确性而备受赞誉，在一段时 期内几乎成为搜索引擎的代名词。 如今，搜索引擎的发展进入了黄金时代，搜索引擎家族不断发展壮大，逐渐 分布到信息世界的各个角落，它们的种类、技术也在不断地发生变化。 1 3 搜索引擎的分类 尽管目前存在数量众多的搜索引擎，但按照它们信息搜集方法和服务提供 方式的不同，可以大致划分为三大类型。 1 、全文检索搜索引擎 全文搜索引擎是名副其实的搜索引擎，国外具代表性的有g o o g l e 、y a h o o 、 a l l t h e w e b 等，国内著名的有百度、中搜等。它们都是通过从互联网上提取的 各个网站的信息而建立的数据库，检索与用户查询条件匹配的相关记录，然后 按一定的排列顺序将结果返回给用户，也是目前常规意义上的搜索引擎。 2 、目录搜索引擎 目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅 仅是按目录分类的网站链接列表而已。用户完全可以不用进行关键词查询，仅 靠分类目录也可找到需要的信息。国外比较著名的目录索引搜索引擎有y a h o o 、 o p e nd i r e c t o r yp r o j e c t ( d m o z ) 、l o o k s m a r t 等。国内的搜狐、新浪、网易搜索 也都具有这一类功能。 2 3 、元搜索引擎 元搜索引擎在接受用户查询请求时，同时在其它多个引擎上迸行搜索，并 将结果返回给用户。著名的元搜索引擎有d o g p i l e 、v i v i s i m o 等，国内元搜索引 擎中具代表性的有搜星( s o s e e n ) ，优客( y o k ) 等。在搜索结果排序方面，有 的直接按来源引擎排列搜索结果，如d o g p i l e ，有的则按自定的规则将结果重新 排列组合，如v i v i s i m o 。 其他的像新浪、网易等搜索引擎都是调用其它全文检索搜索引擎，或者在 其搜索结果的基础上做了二次开发。 1 4 搜索引擎的系统架构 搜索引擎的实现原理，可以看作四步：从互联网上抓取网页一建立索引数 据库一在索引数据库中搜索一对搜索结果进行处理和排序。 1 、从互联网上抓取网页 利用能够从互联网上自动收集网页的网络蜘蛛程序，自动访问互联网，并沿 着任何网页中的所有u r l 爬到其它网页，重复这过程，并把爬过的所有网页下 载到服务器中。 2 、建立索引数据库 由索引系统程序对收集回来的网页进行分析，提取相关网页信息( 包括网页 所在u r l 、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、 与其它网页的链接关系等) ，根据一定的相关度算法进行大量复杂计算，得到每 一个网页针对页面内容中及超链中每一个关键词的相关度( 或重要性) ，然后用 这些相关信息建立网页索引数据库。 3 、在索引数据库中搜索 当用户输入关键词搜索后，分解搜索请求，由搜索系统程序从网页索引数据 库中找到符合该关键词的所有相关网页。 4 、对搜索结果进行处理排序 所有相关网页针对该关键词的相关信息在索引库中都有记录，只需综合相 关信息和网页级别形成相关度数值，然后进行排序，相关度越高，排名越靠前。 最后由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返 回给用户。 下图是一个典型的搜索引擎系统架构图，搜索引擎的各部分都会相互交错 相互依赖。其处理流程按照如下描述： 3 “网络蜘蛛”从互联网上抓取网页，把网页送入“网页数据库”，从网页中 “提取u r l ”，把u r l 送入“u r l 数据库- 7 9 “蜘蛛控制”得到网页的u r l ， 控制“网络蜘蛛”抓取其它网页，反复循环直到把所有的网页抓取完成。 系统从“网页数据库”中得到文本信息，送入“文本索引”模块建立索引， 形成“索引数据库”。同时进行“链接信息提取”，把链接信息( 包括锚文本、 链接本身等信息) 送入“链接数据库”，为“网页评级”提供依据。 “用户”通过提交查询请求给“查询服务器”，服务器在“索引数据库”中 进行相关网页的查找，同时“网页评级”把查询请求和链接信息结合起来对搜 索结果进行相关度的评价，通过“查询服务器”按照相关度进行排序，并提取 关键词的内容摘要，组织最后的页面返回给“用户”。 1 5 搜索引擎关键技术和本文研究重点 搜索引擎专注于提升用户的体验度，用户体验度反映在三个方面：快、全、 准，即搜索速度、查全率和查准率。其中最易达到的是搜索速度，因为对于搜 索耗时在1 秒以下的系统来说，访问者很难辨别其快慢了，更何况还有网络速 度的影响。因此，对搜索引擎的评价就集中在了前两者：全、准。 搜索引擎的“全”则需保证不遗漏某些重要的结果，而且能找到最新的网 页，这需要搜索引擎有一个强大的网页收集器，一般称为“网络蜘蛛”或者“网 页机器人”。 搜索引擎的“准”，需要保证搜索的前几十条结果都和搜索词十分相关，这 需由“分词技术”和“排序技术”来决定。 本文的第二、第三章分别对网络蜘蛛算法和中文分词技术进行分析，而第 四章则重点研究了当前搜索引擎排序算法的优缺点，并在此基础上提出了一种 全新的统一开放的排序公式。 4 第二章网络蜘蛛 搜索引擎首先搜索，然后排序，搜索是排序的前提和基础。 搜索引擎进行搜索时使用网络蜘蛛技术来抓取网站的网页，而不是在搜索 者输入关键词后再把那些需要的结果抓取过来的根本原因在于效率问题，搜索 引擎不可能在搜索时实时去检查每个网页，而是需要把网页先抓取下来，按照 关键词建立好索引，每次搜索的结果都会直接从搜索引擎建立好索引的数据库 中查找，然后把结果返回给访问者。 网络蜘蛛技术并不是一项十分高深的技术，但要做一个强大的网络蜘蛛， 却非易事。在目前磁盘容量已经不是瓶颈的时候，搜索引擎一直在扩大自己的 网页数量。最大的搜索引擎g o o g l e 从2 0 0 2 年的1 0 亿网页增加到现在近4 0 亿 网页；最近雅虎搜索引擎号称收录了4 5 亿个网页；国内的中文搜索引擎百度的 中文页面从两年前的七千万页增加到了现在的两亿多。据估计，整个互联网的 网页数达到1 0 0 多亿，而且每年还在快速增长。因此一个优秀的搜索引擎，需 要不断的优化网络蜘蛛的算法，提升其性能。 2 1 基本原理 网络蜘蛛即w e bs p i d e r ，是一个很形象的名字。把互联网比喻成一个蜘蛛 网，那么s p i d e r 就是在网上爬来爬去的蜘蛛。网络蜘蛛是通过网页的链接地址 来寻找网页，从网站某一个页面( 通常是首页) 开始，读取网页的内容，找到 在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这样一直 循环下去，直到把这个网站所有的网页都抓取完为止。如果把整个互联网当成 一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。 对于搜索引擎来说，要抓取互联网上所有的网页几乎是不可能的，从目前 公布的数据来看，容量最大的搜索引擎也不过是抓取了整个网页数量的百分之 四十左右。这其中的原因一方面是抓取技术的瓶颈，无法遍历所有的网页，有 许多网页无法从其它网页的链接中找到；另一个原因是存储技术和处理技术的 问题，如果按照每个页面的平均大小为2 0 k 计算( 包含图片) ，1 0 0 亿网页的容 量是1 0 0 x 2 0 0 0 g 字节，即使能够存储，下载也存在问题( 按照一台机器每秒 下载2 0 k 计算，需要3 4 0 台机器不停的下载一年时间，才能把所有网页下载完 毕) 。同时，由于数据量太大，在提供搜索时也会有效率方面的影响。因此，许 多搜索引擎的网络蜘蛛只是抓取那些重要的网页，而在抓取的时候评价重要性 主要的依据是某个网页的链接深度。 在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先( 如 下图所示) 。广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后 再选择其中的一个链接网页，继续抓取在此网页中链接的所有网页。这是最常 用的方式，因为这个方法可以让网络蜘蛛并行处理，提高其抓取速度。深度优 先是指网络蜘蛛会从起始页开始，一个链接一个链接跟踪下去，处理完这条线 路之后再转入下一个起始页，继续跟踪链接。这个方法有个优点是网络蜘蛛在 设计的时候比较容易。两种策略的区别，下图的说明会更加明确。 5 广度恍先的抓取顺序： a 一1 3c d e f h g i 深度恍先的抓取顺序 a f g e h i 由于不可能抓取所有的网页，有些网络蜘蛛对一些不太重要的网站，设置 了访问的层数。例如，在上图中，a 为起始网页，属于o 层，b 、c 、d 、e 、f 属于第1 层，g 、h 属于第2 层，i 属于第3 层。如果网络蜘蛛设置的访问层数 为2 的话，网页i 是不会被访问到的。这也让有些网站上一部分网页能够在搜 索引擎上搜索到，另外一部分不能被搜索到。对于网站设计者来说，扁平化的 网站结构设计有助于搜索引擎抓取其更多的网页。 网络蜘蛛在访问网站网页的时候，经常会遇到加密数据和网页权限的问题， 有些网页是需要会员权限才能访问。当然，网站的所有者可以通过协议让网络 蜘蛛不去抓取，但对于一些出售报告的网站，他们希望搜索引擎能搜索到他们 的报告，但又不能完全免费的让搜索者查看，这样就需要给网络蜘蛛提供相应 的用户名和密码。网络蜘蛛可以通过所给的权限对这些网页进行网页抓取，从 而提供搜索。而当搜索者点击查看该网页的时候，同样需要搜索者提供相应的 权限验证。然而在用g o o g l e 搜索h t t p ：w w w , s e a r c h e n g i n e w a t c h c o m 一时，笔者发 现若点击g o o g l e 的本地高速缓存链接，就可以看到付费内容。 网络蜘蛛需要抓取网页，不同于一般的访问，如果控制不好，则会引起网 站服务器负担过重。因此，网络蜘蛛必须按照一定的规则和网站进行交流。一 方面让网站管理员了解网络蜘蛛都来自哪儿，做了些什么，另一方面也告诉网 络蜘蛛哪些网页不应该抓取，哪些网页应该更新。 网络蜘蛛在下载网页的时候，会去识别网页的h t m l 代码，在其代码的部 分，会有m e t a 标识。通过这些标识，可以告诉网络蜘蛛本网页是否需要被抓 取，还可以告诉网络蜘蛛本网页中的链接是否需要被继续跟踪。例如：表示本 网页不需要被抓取，但是网页内的链接需要被跟踪。 现在一般的网站都希望搜索引擎能更全面的抓取自己网站的网页，因为这 样可以让更多的访问者能通过搜索引擎找到此网站。为了让本网站的网页更全 面被抓取到，网站管理员可以建立一个网站地图，即s i t em a 口。许多网络蜘蛛 6 会把s i t e m a p h t m 文件作为一个网站网页爬取的入口，嘲站管理员可以把网站内 部所有网页的链接放在这个文件里面，那么网络蜘蛛可以很方便的把整个网站 抓取下来，避免遗漏某些网页，也会减小对网站服务器的负担a 2 2 内容提取 搜索引擎建立网页索引，处理的对象是文本文件。对于网络蜘蛛来说，抓 取下来网页包括各种格式，包括h t i i l l 、图片、d o c 、p d f 、多媒体、动态网页及 其它格式等。这些文件抓取下来后，需要把这些文件中的文本信息提取出来。 准确提取这些文档的信息，方面对搜索引擎的搜索准确性有重要作用，另一 方面对于网络蜘蛛正确跟踪其它链接有一定影响。 对于d o c 、p d f 等文档，这种由专业厂商提供的软件生成的文档，厂商都会 提供相应的文本提取接口。网络蜘蛛只需要调用这些插件的接口，就可以轻松 的提取文档中的文本信息和文件其它相关的信息。 h t m l 等文档不一样，h t m l 有一套自己的语法，通过不同的命令标识符 来表示不同的字体、颜色、位置等，提取文本信息时需要把这些标识符都过滤 掉。过滤标识符并非难事，因为这些标识符都有一定的规则，只要按照不同的 标识符取得相应的信息即可。但在识别这些信息的时候，需要同步记录许多版 式信息，例如文字的字体大小、是否是标题、是否是加粗显示、是否是页面的 关键词等，这些信息有助于计算单词在网页中的重要程度。同时，对于h t m l 网页来说，除了标题和正文以外，会有许多广告链接以及公共的频道链接，这 些链接和文本正文一点关系也没有，在提取网页内容的时候，也需要过滤这些 无用的链接。例如某个网站有“产品介绍”频道，因为导航条在网站内每个网 页都有，若不过滤导航条链接，在授索“产品介绍”的时候，则网站内每个网 页都会搜索到，无疑会带来大量垃圾信息。过滤这些无效链接需要统计大量的 网页结构规律，抽取一些共性，统一过滤；对于一些重要而结果特殊的网站， 还需要个别处理。这就需要网络蜘蛛的设计有一定的扩展性。 对于多媒体、图片等文件，一般是通过链接的锚文本( 即，链接文本) 和 相关的文件注释来判断这些文件的内容。例如有一个链接文字为“x x 明星照 片”，其链接指向一张b m p 格式的图片，那么网络蜘蛛就知道这张图片的内容 是“x x 明星的照片”。这样，在搜索“x x 明星”和“照片”的时候都能让搜 索引擎找到这张图片。另外，许多多媒体文件中有文件属性，考虑这些属性也 可以更好的了解文件的内容。 动态网页一直是网络蜘蛛面临的难题。所谓动态网页，是相对于静态网页 而言，是由程序自动生成的页面，这样的好处是可以快速统一更改网页风格， 也可以减少网页所占服务器的空间，但同样给网络蜘蛛的抓取带来一些麻烦。 由于开发语言不断的增多，动态网页的类型也越来越多，如：a s p 、j s p 、p h p 等。 这些类型的网页对于网络蜘蛛来说，可能还稍微容易一些。网络蜘蛛比较难于 处理的是一些脚本语言( 如v b s c r i p t 和j a v a s c r i p t ) 生成的网页，如果要完善 的处理好这些网页，网络蜘蛛需要有自己的脚本解释程序。对于许多数据是放 在数据库的网站，需要通过本网站的数据库搜索才能获得信息，这些给网络蜘 蛛的抓取带来很大的困难。对于这类网站，如果网站设计者希望这些数据能被 搜索引擎搜索，则需要提供一种可以遍历整个数据库内容的方法。 对于网页内容的提取，一直是网络蜘蛛中重要的技术。整个系统一般采用 7 插件的形式，通过一个插件管理服务程序，遇到不同格式的网页采用不同的插 件处理。这种方式的好处在于扩充性好，以后每发现一种新的类型，就可以把 其处理方式做成一个捅件补充到插件管理服务程序之中。 2 3 更新周期 由于网站的内容经常在变化，因此网络蜘蛛也需不断的更新其抓取网页的 内容，这就需要网络蜘蛛按照一定的周期去扫描网站，查看哪些页面是需要更 新的页面，哪些页面是新增页面，哪些页面是已经过期的死链接。 搜索引擎的更新周期对搜索引擎搜索的查全率有很大影响。如果更新周期 太长，则总会有一部分新生成的网页搜索不到；周期过短，技术实现会有一定 难度，而且会对带宽、服务器的资源都有浪费。搜索引擎的网络蜘蛛并不是所 有的网站都采用同一个周期进行更新，对于一些重要的更新量大的网站，更新 的周期短，如有些新闻网站，几个小时就更新一次；相反对于一些不重要的网 站，更新的周期就长，可能一两个月才更新一次。 一般来说，网络蜘蛛在更新网站内容的时候，不用把网站网页重新抓取一 遍，对于大部分的网页，只需要判断网页的属性( 主要是日期) ，把得到的属性 和上次抓取的属性相比较，如果一样则不用更新。 网络蜘蛛在搜索引擎中占有重要位置，对搜索引擎的查全、查准都有影响， 它不仅决定了搜索引擎数据容量的大小，还直接影响搜索结果页中的死链接( 即 链接所指向的网页已经不存在) 的个数。目前如何发现更多的网页、如何正确 提取网页内容、如何下载动态网页、如何提高抓取速度、如何识别网站内内容 相同的网页等都是网络蜘蛛需要进一步改进的问题。 8 第三章中文分词 众所周知，英文是以词为单位的，词和词之间是靠空格隔开，而中文是以 字为单位，句子中所有的字连起来才能描述一个意思。中文分词的准确与否， 直接影响到中文搜索结果的准确性。 3 1 中文分词算法 中文分词技术属于自然语言处理技术范畴，对于一句话，人可以通过自己 的知识来明白哪些是词，哪些不是词，但如何让计算机也能理解? 其处理过程 就是分词算法。 现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的 分词方法和基于统计的分词方法。 1 、基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与 一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则 匹配成功( 识别出一个词) 。按照扫描方向的不同，串匹配分词方法可以分为正 向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大( 最长) 匹 配和最小( 最短) 匹配；按照是否与词性标注过程相结合，又可以分为单纯分 词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下： 1 ) 正向最大匹配法( 由左到右的方向) ： 2 ) 逆向最大匹配法( 由右到左的方向) ； 3 ) 最少切分( 使每一句中切出的词数最小) 。 还可以将上述各种方法相互组合，例如可以将正向最大匹配方法和逆向最 大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹 配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向 匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误 率为1 1 6 9 ，单纯使用逆向最大匹配的错误率为1 2 4 5 。但这种精度还远远不能 满足实际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段， 还需通过利用各种其它的语言信息来进一步提高切分的准确率。 一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中 识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为 较小的串再来进机械分词，从而减少匹配的错误率。另一种方法是将分词和词 类标注结合起来，利用丰富的词类信息对分词决策提供帮助，并且在标注过程 中又反过来对分词结果进行检验、调整，从而极大地提高切分的准确率。 2 、基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。 其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息 来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控 部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语 义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方 9 法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以 将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统 还处在试验阶段。 3 、基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上f 文中，相邻的字同时出现 的次数越多，就越有可能构成个词。因此字与字相邻共现的频率或概率能够 较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行 统计，计算它们的互现信息。定义两个字的互现信息，计算两个汉字x 、y 的 相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高 于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料巾 的字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统汁取词 方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是 词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多的”等，并且 对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部 基本的分词词典( 常用词词典) 进行串匹配分词，同时使用统计方法识别一些 新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率 高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。 到底哪种分词算法的准确度更高，目前并无定论。对于任何一个成熟的分 词系统来说，不可能单独依靠某一种算法来实现，都需要综合不同的算法。著 名的“海量科技”的分词算法就采用“复方分词法”，所谓复方，相当于用中药 中的复方概念，即用不同的药才综合起来去医治疾病，同样，对于中文词的识 别，需要多种算法来处理不同的问题。 3 2 分词中的难题 有了成熟的分词算法，是否就能容易的解决中文分词的问题呢? 事实远非 如此。中文是一种十分复杂的语言，让计算机理解中文语言更是困难。在中文 分词过程中，有两大难题一直没有完全突破。 1 、歧义识别 歧义是指同样的一句话，可能有两种或者更多的切分方法。例如：表面的， 因为“表面”和“面的”都是词，那么这个短语就可以分成“表面的”和“表 面的”。这种称为交叉歧义。像这种交叉歧义十分常见，由于没有人的知识去理 解，计算机很难知道到底哪个方案正确。 交叉歧义相对组合歧义来说是还算比较容易处理，组合歧义就必需根据整 个句子来判断了。例如，在句子“这个门把手坏了”中，“把手”是个词，但在 句子“请把手拿开”中，“把手”就不是一个词；在句子“将军任命了一名中将” 中，“中将”是个词，但在句子“产量三年中将增长两倍”中，“中将”就不再 是词。这些词计算机又如何去识别? 如果交叉歧义和组合歧义计算机都能解决的话，在歧义中还有一个难题， 是真歧义。真歧义意思是给出一句话，由人去判断也不知道哪个应该是词，哪 个应该不是词。例如：“乒乓球拍卖完了”，可以切分成“乒乓球拍卖完了”、 也可切分成“乒乓球拍卖完了”，如果没有上下文其他的句子，恐怕谁也不 知道“拍卖”在这里算不算一个词。 2 、新词识别 1 0 新词，专业术语称为未迸录词。也就是那些在字典中都没有收录过，但又 确实能称为词的那些词。最典型的是人名，除了人名以外，还有机构名、地名、 产品名、商标名、简称、省略语等都是很难处理的问题，而且这