（计算机软件与理论专业论文）个性化搜索引擎模型的研究与改进.pdf

哈尔滨工程大学硕士学位论文 摘要 通过使用搜索引擎，人们可以方便快捷的从大量信息中查找出自己需要 的内容。比起曾经功能单一的搜索引擎，现在的搜索引擎已经有了很大的发 展。但是，现有的搜索引擎技术仍然存在有不够智能化，不能够在大量的搜 索结果中挑选出用户真正感兴趣的结果的问题。而这正是本课题要研究改进 的问题。 针对用户对搜索引擎个性化服务的需要，作者阐述了一种个性化搜索引 擎页面排序算法的实现思想：采用基于w e b 数据挖掘的方法从用户动作中判 断用户是否对网页有“兴趣；在对原有搜索引擎排序技术进行研究与分析的 基础上，采用聚类的方法对网页进行分类；建立用于存储用户兴趣信息的关 键字用户兴趣表，同时建立了网页类型表作为支撑：通过分析国内外关 于个性化搜索的著作，提出一种适合个性化排序的权值计算公式，通过对存 储在用户兴趣表中的用户兴趣信息进行分析得到符合用户兴趣的排序结果。 同时，基于这个排序算法本文建立了一种个性化搜索引擎模型，并对各部分 的实现进行分析设计。在模型中加入个性化分析模块以及网页类型分析模块， 目的是提高搜索引擎的个性化分析能力，使搜索结果更符合用户需要，提高 用户对个性化搜索引擎的满意度。 最后，作者通过对比传统搜索引擎的实验验证了采用个性化排序算法的 搜索引擎模型具备较高的用户满意度。分析了可能存在的问题，并指出可以 继续研究的方向。 关键词：搜索引擎；排序算法；满意度；用户兴趣；个性化 哈尔滨工箨大学硕士学位论文 a b s t r a c t t h r o u g hs e a r c he n g i n e ，p e o p l ec o u l de a s i l yg e tt h ec o n t e n tw h a tt h e yn e e d 。 c o m p a r e d 训t l l t h eo l do n e ，t h es e a r c he n g i n e t o d a yh a sa l a r g ed e v e l o p m e n t b u t ， t h e r ea r ea l s os o m ep r o b l e m s ，f o re x a m p l e ，t h es e a r c he n g i n ei sn o ti n t e l l i g e n t e n o u g h ，t h e yc a l ln o tg e tt h er e a l l yi n t e r e s t e da n s w e r so ft h eu s e r sf r o ma m o u n to f s e a r c h i n gr e s u l t s 。a n di ti sj u s tt h ea t t i t u d eo f t h er e s e a r c h 。 i na l l u s i o nt ot h en e e do fs e a r c he n g i n e sp e r s o n a l i z e ds e r v i c e ，t h ea u t h o r p u t sf o r w a r dt h er a n k i n gp a g e sa l g o r i t h mo fp e i s o n a l i z e ds e a r c he n g i n e ：t h e t h e s i sj u d g e dw h e t h e rt h eu s e rw 。a s ，i n t e r e s t e di nt h ew e bt h r o u g ht h eu s e r sa c t i o n b a s e do nt h ew e bd a t a - m i n i n gm e t h o d t h ea u t h o rc h e e s ec l u s t e r i n gt oc l a s st h e w e b p a g e ，b a s e do nt h ea n a l y s i sf o ro r i g i n a ls e a r c he n g i n et e c h n o l o g y t h et h e s i s b u i l do nak e y w o r da n du s e r - i n t e r e s tt a b l ef o rt h eu s e r - i n t e r e s tm e s s a g e s s t o r i n g ，a n db u i l do naw e b t y p et a b l et os u p p o r tt h eu s e r - i n t e r e s tt a b l e t h r o u g h a n a l y z e dt h ew o r k s ，t h ea u t h o rg i v ear a n kf o r m u l aw h i c hc o u l dg e tt h ep r o p e r r e s u l tt h r o u g ht h eu s e r - i n t e r e s tm e s s a g es t o r i n gi nt h eu s e r - i n t e r e s tt a b l e 。a tt h e s a m et i m e ，t h i st h e s i sb u i l du pam o d e lo fp e r s o n a l i z e ds e a r c he n g i n ea n dt h e r e a l i z a t i o no fe a c hp a r to ft h es y s t e ma r ea n a l y z e da n dd e s i g n e d 。t h ep u r p o s ef o r a d d i n gp e r s o n a l i z e d a n d p a g e - t y p ea n a l y z i n g m o d e li st o i m p r o v e t h e p e r s o n a l i z e da n a l y z i n ga b i l i t y , t om a k et h es e a r c h i n gr e s u l t sc o n f o r mu s e r s n e e d a n di m p r o v eu s e r s s a t i s f a c t i o nf o r 氇ep e r s o n a l i z e ds e a r c he n g i n e 。 a tl a s t ，t h ea u t h o rh a sc o n f i r m e dt h eb e r e ru s e r s s a t i s f a c t i o no ft h em o d e lb y e x p e r i m e n t sc o m p a r e dw i t ht h et r a d i t i o n a ls e a r c he n g i n e a l s o ，t h ea u t h o rb r i n g s f o r w a r dt h ed i r e c t i o no ft h en e x ts t e po fr e s e a r c ha n ds o m ep o t e n t i a lp r o b l e m s k e y w o r d s ：s e a r c he n g i n e ；r a n k i n ga l g o r i t h m ；s a t i s f a c t i o n ；u s e r - i n t e r e s t ； p e r s o n a l i z a t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 ， f 本声明的法律结果由本人承担。 作者( 签字) ：乏垫丝 i 日期：姗客年i 胃1 0 匿 哈尔滨工程大学硕士学位论文 1 1 引言 第1 章绪论 自从互联网诞生的那一刻起，搜索引擎便注定了要与互联网的发展紧密 联系在一起。互联网上的知识浩如烟海，如何在最短的时间内，获取到人们 真正感兴趣的知识是每个互联网服务提供商都在不断思索的问题。二十一世 纪是信息爆炸的时代，全世界互联网用户数呈几何级数不断增长。每一个连 在互联网上的计算机都可以看作是互联网的一个组成部分，都是这个互联网 的一个小的知识库，都可以发布在互联网上由所有的互联网用户共享。这使 得互联网上的信息过于庞杂，而且具有不稳定和变动快的特点，没有也不可 能有一个权威机构能对这些信息进行全面的整理和归类。因此，面对缤纷复 杂的网络空间，面对信息的海洋，用户往往感到无所适从，不知道如何去获 取自己需要的内容。正是为了解决这个问题，搜索引擎诞生了。 通过使用搜索引擎，人们可以方便快捷的从信息的海洋中查找出自己需 要的信息。通常说来，搜索引擎是一种专门为互联网提供信息检索的一个专 门的公共服务站点。它通过不断在互联网上寻找有用的信息和资源，并且把 他们以某种形式按照一定的规则保存下来，以方便互联网用户的检索。 目前的搜索引擎一般都采用基于关键词匹配的方式来进行信息检索，这 种方式往往不能揭示信息之间的语义信息，导致系统的查全率和查准率不是 很高，对用户的一个查询请求，搜索引擎系统会返回大量无关的匹配信息， 用户需要在这个返回结果中进行二次查找，负担比较重。如何更好地理解用 户查询，改善查询关键词与网页的相关性，使搜索引擎具有个性化，将是以 后搜索引擎技术发展的一个主要方向。 哈尔滨| t 程大学硕士学位论文 1 2 搜索引擎的发展及国内外研究现状 上世纪九十年代以前，没有人能够搜索互联网，不存在任何互联网搜索 引擎网站。1 9 9 0 年，加拿大麦吉尔大学( m c g i l lu n i v e r s i t y ) 的三个学生发明 了a r c h i e 系统怔1 。1 9 9 3 年，m a t t h e wg r a y 开发了w o r l dw i d ew e bw a n d e r e r 扭1 ， 第一个利用了h t m l 网页之间的链接关系检测万维网规模的程序。一开始， 它只是局限于统计网络上服务器的数量，到了后来，它发展成能够捕获网址 的程序。1 9 9 4 年7 月，斯坦福大学的两名博士生，d a v i df i l o 和美籍华人杨 致远共同创办了超级目录索引y a h o o ，经过不懈的努力，y a h o o 获得了巨大 的成功，从此搜索引擎进入了高速发展时期。目前，在国外，比较著名的搜 索引擎主要有n e w sn o w 和g o o g l e “。n e w sn o w 在国内外拥有超过3 0 0 ，0 0 0 用户，它的新闻搜索范围包括了超过十五种语言的各个国家的重要在线刊物、 新闻。g o o g l e 更是一种为广大互联网用户所熟知的搜索引擎，首先，它采用 了先进的网页级别技术，它的搜索结果常常比别的搜索引擎来的更准确，用 户可以进行多关键词的搜索，另外，它还具有很多方便快捷的附加服务。在 国内，比较知名的搜索引擎就是百度搜索引擎。百度搜索引擎是目前国内搜 索引擎中最出色的一款，它实时的收集各大新闻网站的消息，任何新消息， 新信息在数分钟之内就能够被检索。平均来说，百度搜索对单个用户检索请 求的响应时间小于1 秒。百度搜索引擎采用分布式体系结构，同时使用多台 机器分布写作，并行完成搜索、分析、索引、检索等任务，具有很强的可扩 展性。 随着互联网内容指数级的增长，如何满足各种用户不同的个性化需求等， 是新的信息服务系统面临的挑战性课题。个性化服务是i n t e m e t 信息增长的 必然结果。一个好的个性化服务系统，要能自动判断哪些信息是用户感兴趣 的，哪些是用户不感兴趣的，对于用户不感兴趣的信息则阻止反馈给用户。 1 9 9 9 年，c h a k r a b a r t i ”作了较完备的搜索引擎的模型。系统使用y a h o o 的分类层次目录，由用户在感兴趣的领域作出标记，作为搜索引擎的主题。 用户可以在浏览的时候标识感兴趣的网页，然后按照分类将该网页分入对应 类别中作为样本。该搜索引擎主要由三部分组成：搜集器，分类器和被作者 2 哈尔滨工程大学硕士学位论文 称之为“蒸馏器”( d i s t i l l e r ) 的进程。这种搜索引擎已经具备了一定的智能 性，可以在用户的“指引下给用户提供相应的查询结果。 2 0 0 1 年，北京大学的朱华”1 对中文搜索引擎的结构进行了研究，并将中 文搜索引擎结构按照功能的不同划分为四个模块：网页搜集模块、网页索引 模块、查询模块以及用户界面等四个部分，在国内大多数中文搜索引擎也正 是以这种划分为基础不断进行着深入的研究和改进。 在个性化搜索方面j 目前国内外对个性化搜索的研究主要体现在信息的 自动分类m ，、数据挖掘旧1 、语义网“、全文语义检索。等方面，也取得了可喜 的成果，但是在具体应用上仍然存在着很多的不足。 为了在未来的搜索引擎市场占有一席之地，各大搜索引擎公司纷纷推出 了自己的个性化搜索引擎产品，如百度、g o o g l e 公司就先后推出了自己的个 性化搜索产品，在满足用户需要的同时，也为未来的发展做技术方面的探索。 但是，这些所谓的个性化搜索引擎其原理都是通过某种界面与用户交互，接 受用户查询请求，然后将用户查询的特定信息分解成若干关键词进行分析， 再在索引数据库中进行匹配，挑出符合条件的信息，按照匹配程度的高低进 行排序，最后将结果返回给用户“。 1 3 搜索引擎存在的不足 随着互联网的飞速发展，传统搜索引擎以及目前带有智能化特征的搜索 引擎的许多缺点不足显现在了用户面前，这些不足也制约了互联网的发展， 限制了人们希望从互联网上获取知识的愿望。目前搜索引擎存在的不足之处 主要体现在以下几个方面： ( 1 ) 用户进行检索时无法用简单有效的几个关键字清晰的表达所查找对 象。由于搜索引擎通常采用的是关键词搜索方式，用户提出查找的请求时， 难以用简单的关键词以及它们的简单逻辑关系来真正表达出自己需要的信息 内容，使得搜索难以实现。 ( 2 ) 搜索引擎无法在一次搜索的基础上做出更细的二次搜索。用户的反 馈信息不能够得到及时的响应，用户不能在原有的查询结果上通过进一步的 搜索得到更加精确的结果。降低了检索的效率，同时也影响了用户的满意程 3 哈尔滨工程大学硕士学位论文 度。 ( 3 ) 目前的搜索引擎无法提供个性化的搜索结果。例如：用户输入关键 词a p p l e 进行搜索，众所周知，a p p l e 这个单词既有水果苹果的意思，同时，它 也是a p p l e 品牌电脑的名称，在这种情况下，搜索引擎无法判断用户所要查找 的究竟是水果的一种苹果，还是与电脑品牌有关的那个苹果。也就是说，不 同的用户输入同样的关键字进行查找的时候，搜索引擎给出的结果总是完全 一样的，无法根据用户的特点、喜好给出有关基于用户兴趣的个性化搜索结 果。 ( 4 ) 搜索结果过多，用户无法精确选择适合自己的网址。通过某个关键 字或者简单关键字的组合，用户往往能够得到成百上千条的搜索结果记录。 通常来说，用户往往对处于前三页的搜索结果可以进行浏览，余下的搜索结 果几乎不予理会。所以，现在迫切需要种好的方法可以把根据用户的爱好 搜索出的结果优先显示出来，使得用户能够快速获取到自己真正想得到的搜 索结果。 1 4 本文研究意义及主要内容 比起曾经那些功能单一的搜索引擎，现在的搜索引擎技术已经有了很大 的发展。但是，正如前面提到的，现有的搜索引擎技术仍然存在有很多不完 善、急需要改进的地方。比如说搜索引擎的不够智能化，不能够在大量搜 索结果中主动挑选出用户真正感兴趣的结果。本文就是在对原有搜索引擎实 现思想进行研究与分析的基础上，对个性化排序的实现思想进行了改进，并 提出了相适应的个性化搜索引擎的模型结构。目的是充分的发挥计算机及互 联网的优势，使得用户的搜索结果更加符合用户的真正需要，提高用户对搜 索引擎的满意度。 1 5 本文的组织结构 本论文内容组织如下g 第1 章分析课题的研究背景以及国内外研究现状，阐述该课题研究的热 4 哈尔滨工程大学硕士学位论文 点与难点，并介绍课题研究的内容。 第2 章分析搜索引擎的工作原理以及搜索引擎各过程的实现方法，对整 个设计中将用到的技术给予阐述。 第3 章论述个性化搜索引擎的核心个性化排序算法的实现思想。首 先阐述用户兴趣库的结构以及对用户兴趣的获取方法，然后又对网页类型库 的结构以及网页类型的获取技术进行了说明。 第4 章提出基于个性化搜索引擎排序算法的个性化搜索引擎模型结构， 并在此基础上提出改进方案。 第5 章通过对比传统搜索引擎的具体实验来验证搜索引擎模型改进方案 的优越性。 哈尔滨工程大学硕士学位论文 第2 章理论基础 搜索引擎从诞生伊始，就以低廉的成本，快捷的信息反馈迅速成为广大 企业的主要网络推广形式。可是，伴随着互联网的发展、互联网用户要求的 日益提高，传统的搜索引擎暴露出了越来越多的不足，越来越不能满足挑剔 的用户们的需求。为此，更“聪明的搜索引擎，也就是一种智能的提供给 使用者更精确搜索结果的搜素引擎成为了互联网用户们的迫切要求。 2 1 传统搜索引擎的工作原理 搜索引擎是收录网页全文索引的数据库。当使用搜索引擎时，实际上是 在检索这些被搜索到的网页的数据库，而不是检索网络本身。为了使搜索引 擎数据库能够快速的提供结果，对它们进行了精心的设计。但是，如果让搜 索引擎实时的检索数十亿网页则是不可能的。搜索引擎类似于电话白页，但 它包括姓名和地址的简单列表。与按类别组织并经常包括很多有关企业的描 述性信息的黄页不同，白页能够提供最简明的信息。但是，它们都以某种方 式编排，只要使用一个或几仓关键字，就能够很容易的查找到一个地址n ”。 传统搜索引擎主要由搜索器：索引器、语义分析系统以及排序器构成。 搜索器不断的在互联网上“爬行 ，将“有用”的新信息获取下来。索引器则 负责从搜索器获取的新信息中提取出索引项，并将相关信息保存在索引库中， 以方便响应日后互联网用户提出的搜索要求。用户的搜索请求由语义分析器 分析理解成若干关键字的组合，并提交给索引库中进行搜索。最后，在索引 库中搜索的结果由排序器进行最后的排序，将结果呈现给用户。传统搜索引 擎工作原理图如图2 1 所示。 6 哈尔滨工程大学硕士学位论文 w e b 信息 搜索模块 搜索模块负责不断从网络上获取 ，w e b 信息 由嘉瓣雾 语义分析器将用户输入的 搜索请求分解为可以在索 引库中进行查找的关键字 排序模块ll 语义分析 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 一i - li 模块 l 排序模块将索引结果 下 l 进行排序 l 用户 图2 1 传统搜索引擎工作原理 2 1 1 搜索模块 上世纪初，“机器人 一词在计算机界很是流行，用于形容某种能够以人 类所不能达到的速度和精度执行某种任务的软件程序。由于专门用于检索网 络信息的“机器人”像蜘蛛一样，在网络上爬来爬去，不断分析下载有用的 信息，因此，作为网络搜索器的“机器人又被称为“网络蜘蛛”。“网络蜘 蛛 的功能就是在互联网上不断漫游，发现和搜集信息。作为一个计算机程 序搜索器日夜不停的运行，尽可能多、尽可能快的搜集各类新信息，并定期 更新已经搜集过的旧信息，以避免出现死链接和无效链接u “。 搜索器通常以两种策略之一运行： 策略一：从一个起始u r l 集合开始，顺着这些u i 也中的超链，以宽度 优先、深度优先或启发式方法循环的在互联网中发现相关信息。这些起始的 u p , 3 。可以是任意的u p , l ，但往往优先采用一些非常流行、包含很多链接的站 点。 策略二：将网络空间按照域名、i p 地址或国别域名划分成子空间，让每 7 哈尔滨工程大学硕士学位论文 i i im lm | , , m i 盲j 宣皇嗣重e 暑昌宣宣暑宣i i 宣i 暑i 蔷暑i i 嗣 一个搜索器负责一个子空间的穷尽搜索。 搜索器常常用分布式、并行计算技术来实现，以提高信息发现和更新的 速度。目前，搜索器能处理的信息类型也多种多样，包括h t m l 、x m l 、f t p 文件，n e w s g r o u p 文章，w o r d 等字处理文档，各种图象文件，m p 3 音乐文件 以及多媒体信息等n “。 2 。1 。2 索引模块 搜索器不断的在互联网上搜索新的有用的信息，信息越来越多，索引模 块的作用就是将搜索器在互联网上获取的信息，按照一定的规则从中抽取索 引项，生成索引表，放到索引库中，以方便用户对信息的搜索。大型搜索引 擎的索引器，往往还包含其他一些模块，比如说桶、字典、文件索引等。索 引器在处理信息时，一般要给单个的索引项附一个权值，用来表示这个索引 项的“重要程度 ，这样在用户进行搜索查询的时候，某个关键词的重要程度 就可以表示出来。 2 1 3 排序模块 顾名思义，排序模块的主要功能就是把经过搜索数据库的的结果进行排 序以最合适的方式呈现给用户。一种搜索引擎是否智能，是否能够满足用户 的要求，最主要就看它的排序器功能是否合适，是否可以分析用户的个人特 点并制定相应的“对策 ，给出最合适的排序。一种排序器能否具有“智能 ， 就取决于它的实现算法。目前，很多种排序算法都在使用中，每种算法都有 它们各自的优点，但同时，也都存在自身的不足之处。目前比较流行的排序 算法主要有词频位置加权排序法、d i r e c th i t 算法n ”、p a n g e r a n k 算法、竞价 排名服务以及h i t s 算法n 制等等。 2 1 4 语义分析模块 机器和人不一样的地方就在于人可以直接理解词的意思，句子的意思， 从而理解整个文章的意思，但是机器不能。比如说，一看到西红柿，人们就 会想到那个圆圆的、红红的、口感有点儿酸的水果，但是搜索引擎却不能从 8 哈尔滨工程大学硕士学位论文 感性上理解，只有通过人们不断给其充实“知识”。但是，搜索引擎可以通过 一定的算法分析来掌握词之间的关系，这就是语义分析。 用户的搜索请求是否可以被精确的响应，主要在于语义分析模块是否可 以准确的将用户的查询语句分解成若干个关键词的组合。 2 1 5 相关技术 ， 随着互联网的不断发展，用户们对搜索引擎的要求也是越来越高，相应 的也出现了很多搜索引擎的各功能实现的算法。这些算法各有各的好处，同 时也各有各的不足。 搜索引擎一直重视提升用户的满意程度，而用户的满意程度主要体现在 三个方面：准、快、全。用专业的语言来形容就是：查准率、搜索速度和查 全率。其中最容易达到的就是搜索速度，因为只要人们能够把搜索时间控制 在一秒钟以下，用户就很难判断其快慢了，更何况还有网络速度快慢的因素 在里面。所以，对搜索引擎好坏的评价主要体现在两个方面：查准率和查全 率。 1 网络信息搜集技术 中文搜索引擎的“全需要保证搜索不遗漏某些重要的结果，这就需要 搜索引擎拥有一个强大的网络搜集器。如果把互联网比作一个蜘蛛网，那么 搜索器就是网上爬来爬去的蜘蛛，它是通过网页的链接地址来寻找网页，通 过一个网页上的其他链接来寻找下一个网页，如此往复。 网络蜘蛛主要有深度优先和广度优先这两种搜索方式，广度优先是指先 抓取初始网页链接中的所有网页，然后再选择其中一个网页继续抓取次网页 中的所有链接。这种方法的好处是可以令搜索器进行并行处理，提高搜索速 度。而深度优先则是从起始页开始，一个链接一个链接的搜索下去，直到搜 索完这条线路后再转入另一个起始页。这种方法的优点是搜索器设计比较容 易。 网络蜘蛛进入一个网站，一般会访问一个特殊的文本文件r o b o t s t x t ，这 个文件一般会放在网站服务的根目录下，如： h t t p ：w w w b l o g c h i n a c o m r o b u s t t x t 。网站管理员可以通过r o b o t s t x t 来定义哪 9 哈尔滨工程大学硕士学位论文 i i _ _ 昌_ _ i i 皇| 皇皇_ 宣_ 暑| 蕾_ 宣宣昌宣i 暑；i i ；i ；i ；i ；亏芦；i i i i i i i ；i i i 置昌i j _ 皇置i 昌昌i i i i i i i 萱 些目录网络蜘蛛不能访问，或者哪些目录对于特定的搜索器不能访问。例如 有些网站的可执行文件目录和临对文件目录不希望被搜索引擎搜索到，那么 网站管理员就可以把这些目录定义为拒绝访问目录。 一般的网络蜘蛛都会遵循这些协议，而且网站的管理员还可以通过其他 方式来拒绝网络蜘蛛对信息的获取“”。 对于搜索引擎来说，需要获取的网页包括很多格式，比如：h t m l 、图 片、d o c 、p d f 、多媒体、动态网页等等。从这些格式的文件中提取出有用 的信息，这对搜索引擎的准确性有着重大的作用。 d o c 、p d f 这样格式的文档，是由专业厂商提供的软件生成的，这些软 件里大多提供了响应的文本内容提取的接口，因此，它们的内容比较容易获 得。但是，对于其它的一些格式就不是这样了。h t m l 文档有自己的一套语 法，因此，在这种文档中提取信息，要注意根据标识符去掉无用的字体、颜 色、位置等版式信息，同时，也要注意去掉许多广告链接以及公共的频道链 接。对于多媒体、图片等文档，通常是通过链接的锚文本和相关的文件注释 来判断文件的内容。目前还不能直接通过图片内容来判断文件的内容。对于 搜索器来说，比较难处理的是动态网页。动态网页是相对于静态网页来说的， 是程序自动生成的页面。它的好处是可以很快的更改网页风格、内容。但是， 由于没有一定的规律，搜索器很难从中获取到相应的信息。尤其是对于一些 脚本语言产生的网页，搜索器还需要拥有相应的脚本解释程序。 2 语义分析技术众所周知，英文是以词为单位的，词和词之间是靠空格 隔开，而中文是以字为单位，句子中所有的字连起来才能描述一个意思。例 如，英文句子ir i l las t u d e n t ，用中文则为：我是一个学生”。计算机可以很 简单通过空格知道s t u d e n t 是下个单词，但是不能很容易明白 学】、【生】两个 字合起来才表示一个词。把中文的汉字序列切分成有意义的词，就是中文分 词，有些人也称为切词。就目前语义分析技术成熟度来说，英文语义分析技 术已经发展的很成熟，而中文语义分析由于中文语言结构的特异性，仍然处 于大规模研究阶段。 中文搜索引擎的“准”需要保证搜索的前几页结果要和搜索词十分相关， 这就需要拥有值得信赖的语义分析技术。语义分析主要运用了自然语言处理 技术，主要包括分词、句法分析以及语义理解等技术。 1 0 哈尔滨工程大学硕士学位论文 ( 1 ) 分词。最容易想到的，也是最简单的分词办法就是查字典。这种方 法最早是由北京航天航空大学的梁南元教授提出的。用“查字典”法，其实 就是把一个句子从左向右扫描一遍，遇到字典里有的词就标识出来，遇到复 合词( 比如“上海大学) 就找最长的词匹配，遇到不认识的字串就分割成单 字词，于是简单的分词就完成了。这种简单的分词方法完全能处理上面例子 中的句子。八十年代，哈尔滨正业大学的王晓龙博士把它理论化，发展成最 少词数的分词理论，即一句话应该分成数量最少的词串。这种方法一个明显 的不足是当遇到有二义性( 有双重理解意思) 的分割时就无能为力了。比如， 对短语“发展中国家 正确的分割是“发展中国家 ，而从左向右查字典的 办法会将它分割成“发展中国家”，显然是错了。另外，并非所有的最长匹 配都一定是正确的。比如“上海大学城书店”的正确分词应该是“上海大学 城书店， 而不是“上海大学城书店”。九十年代以前，海内外不少学者试 图用一些文法规则来解决分词的二义性问题，都不是很成功。9 0 年前后，清 华大学的郭进博士用统计语言模型成功解决分词二义性问题，将汉语分词的 错误率降低了一个数量级。分词技术主要体现在把用户提供的一整句搜索语 句分割成一个个分离的词语。中文与英文不同，英文可以通过词与词之间的 间隔来判断一个词，而中文的词与词之间没有间隔。目前中文分词主要有三 种方法，分别是基于字符串匹配的分词方法、基于理解的分词方法以及基于 统计的分词方法。 基于字符串匹配的分词方法又叫做机械分词方法，按照一定策略将搜索 语句与一个很大的机器词典中的词进行匹配，如果找到相同的词，则说明匹 配成功。但是，显而易见，这种匹配方式的精度很差，常常会出现歧义的现 象，因此不常采用。 基于理解的分词方法就是让计算机模拟人对句子的理解方法，以达到识 别词的效果。它主要是在分词的同时，进行语法分析和语义分析，利用语法 分析和语义分析得到的信息来处理歧义现象。但是，这种方法受限于汉语的 庞大和复杂性，目前仍处于实验阶段。 基于统计的分词方法利用了词的稳定性这一特点。在上下文中，相邻的 字出现越多，就越有可能是一个词。因此，字与字相邻出现的频率能够反映 出是否可以构成一个词。可以对常常出现的文章中的各个字之间的组合频率 1 1 哈尔滨工程大学硕士学位论文 来判断是否是一个词。但这种方法也有它的不足之处：有一些汉字常常连用， 但它们并不是一个词，而且这种方法要占用很大的时间开销。在实际的应用 中，常常利用一部常用的分词词典来协助进行匹配分词，同时利用统计方法 识别一些新词。也就是说把基于字符串匹配和基于统计的两种方法联合使用。 到底那种分词方法的效率高、歧义少，目前并没有一个定论，但明显的 是，一种高效的分词技术不是单一某种分词方法来构成的，都需要综合不同 的分词方法。目前流行的一些分词方法有：清华大学的s e g 分词系统、清华 大学的s e g t a c 分词系统、国家语委文字所应用语法分析技术的汉语自动分 词、复旦分词系统、哈工大统计分词系统、北大分词系统等。 ( 2 ) 句法分析。所谓句法分析，就是将一个句子分解成一些小的组成部 分( 词、短语等等) 以后，了解这些部分之间的关系，从而帮助人们把握这 个句子的意义。语言的研究一般而言存在四个层面：词法层、句法层、语义 层和语用层。因此，语言的分析也存在四个层面：词法分析、句法分析、语 义分析和语用分析。汉语在形式上，并没有“词 这一个单位，汉语的语素、 词、短语、甚至句子之间( 词也可以直接成句，称为独词句) ，都没有明确的 界限。汉语是一种孤立语，与作为曲折语和黏着语的其他一些语言相比，汉 语在语法上有自己的特点，如果仅仅从形式上看，这种特点主要体现在这几 个方面：首先，汉语的基本构成单位是汉字而不是字母。常用汉字就有3 0 0 0 多个，全部汉字达数万之多；第二，汉语的词与词之间没有空格分开，也可 以说，从形式上看，汉语中没有“词”这个单位；第三，汉语词没有形态上 的变化，同一个词在句子中充当不同语法功能时，形式是完全相同的；最后， 汉语句子没有形式上唯一的谓语中心词。这些特点对汉语的分析造成了一定 的影响，使得汉语分析呈现出和英语不同的特点。 汉语句法分析的作用是了解词之间的关系，所以，汉语和英语及其他语 言，所面临的问题相差不大。汉语和英语句法分析所采用的技术也是大致相 同。句法分析一般都依赖于某种语法体系，语法体系的形式丰富多彩，各种 语法都有各自的特点，如乔姆斯基层次体系。不同的语法体系产生的语法结 构的形式也大不相同。比较常见同时也很直观的语法结构形式要属语法树了， 另外，其他的形式主要有依存关系树、有向图、特征结构等等“。 但是，总体而言，目前的完全句法分析技术目前并不成熟，得到的结果 1 2 哈尔滨工程大学硕士学位论文 也往往不令人满意，还需要人们进一步的探索研究。 ( 3 ) 语义理解。语义理解即找出词义、结构意义及其结合意义，最终得 到目标语言所要表达的真正意义。它的功能在于可以将经过句法分析的中文 文本进一步理解，得到进一步的语义，最终将句子的语义表示成o w l ( 本体 描述语言) 形式语句。通过语义理解，可以对文本进行进一步的知识获取。 语义理解组建需要一个汉语语义词库和一个汉语语法规则库的支持。汉语词 库和汉语汉语语法规则库搭建在关系数据库上。词库中每个词有一个词义字 段，这个字段是用x m l 语言定义的一个个字符串，这些字符串最终定义了词 的每个词性及其所对应的词义。在接下来的语义理解过程里，分析系统会自 动的根据实际的语言环境选择出最合适的词义。所以，汉语语法规则库中的 语法规则正是为了句法分析后，将汉语句子或短语进行匹配而设置的。 3 排序算法 搜索引擎是否智能，是否能够满足用户的要求，最主要就看它的排序器 功能是否合适，是否可以分析用户的个人特点并制定相应的“对策 ，给出最 合适的排序。一种排序器能否具有“智能”，就取决于它的实现算法。目前， 很多种排序算法都在使用中，每种算法都有它们各自的优点，但同时，也都 存在自身的不足之处。目前比较流行的排序算法主要有词频位置加权排序法、 d i r e c th i t 算法、p a g e r a n k 算法、竞价排名服务以及h i t s 算法等等。 ( 1 ) p a g e r a n k 算法。目前，g o o g l e 尸, 经成为全世界最著名的搜索网站之 一，除了它的功能全、易用性高等特点外，g o o g l e 出众的搜索结果也是其中 重要的原因。p a n g e r a n k 算法，作为g o o g l e 搜索引擎核心的排序算法，越来越 得到学者专家们的重视。 p a g e r a n k 算法是斯坦福大学计算机系的l a w r e n c ep a g e 博士开发设计的 一种对网页进行排序的算法。g o o g l e 收集的每一个网页数据都拥有自己的 p a g e r a n k 。搜索引擎用户使用g o o g l e 进行查找后，搜索引擎按照关键词匹配 进行查找，首先根据词频位置加权排序算法将查找结果排序，然后再用 p a g e r a n k 值的大小对排序进行调整，将调整好的排序结果返回给用户。 p a g e r a n k 公式“气 p r ( a ) = ( 1 一d ) + d ( p r ( t , ) c ( 瓦) + + p 尺( 乙) c ( l ) ) ( 2 - 1 ) 其中，p r ( a ) ：页面a 的网页级别。 1 3 哈尔滨工程大学硕士学位论文 即( z ) ：页面z 的网页级别，页面z 链向页面。 c ( t 。) ：页面z 链出的链接数量。 d ：阻尼系数，取值在0 1 之间。 改进的p a g e r a n k 公式“引： p r ( a ) = ( 1 一d ) n + d ( 瞅( 互) c ( 互) + + p r ( t ) c ( ) ) ( 2 - 2 ) 其中，是互联网上所有网页的数量。 由此，所有页面的网页级别形成的一个概率分布，所有页面的网页级别 之和是l 。在式( 2 1 ) 中，随枫访问某个页面的概率由互联网的总页数决定， 在式( 2 2 ) 中，网页级别是一个页面被随机访问的期望值。 很显然，p a g e r a n k 也注重信息内容的质量，因为只有质量好的信息才能 被别的网页“引用。p a g e r a n k 的不足则主要表现在“链接欺骗”上，在 w e b 开始的阶段，指向链接( b a c k l i n k ) 的确意味着“推荐弦一个网页，但 随着网络的发展，这种推荐作用在下降。由于链接的多少直接影响网站的 p a g e v i e w 和商机，因此一些商业公司网站之间相互链接，带来商业上的互利； 另一方面，一些w e b m a s t e r 在知道p a g e r a n k 的计算方法之后，为了提高自 己网站在g o o g l e 中的排名，在设计网站的结构时，故意使用一些链接方法来 提高重要页面的p a g e r a n k 。正因为上述原因，目前p a g e r a n k 在g o o g l e 排序 时占的重要程度正在呈下降的趋势n 。 ( 2 ) h i t s 算法。1 9 9 f f 年，k l e i n b e r g 提出了h i t s ( h y p e r l i n k i n d u c e d t o p i c s e a r c h ) 算法。h i t s 算法是一种依赖于查询的主题精选算法，用 以评定网页内容的重要性，并以次解决搜索引擎的检索结果相关度排序问题。 k l e i n b e r g 认为，一个网页的重要性应该取决于用户的查询请求，而对于每一 个网页，应该把由网页链出决定的a u t h o r i t y 权重和由网页链入决定的h u b 权重 分开考虑。即：一个“好的”权威页面理应被许多“好的 中心页面所链接， 一个“好的”中心页面理应链接到许多“好的”权威页面。这两种页面之间 的关系可以通过图2 2 中两种页面关系之间的比较来解释。 1 4 哈尔滨工程大学硕士学位论文 图2 2 两种页面关系的比较 将查询词提交普通的基于相识度的搜索引擎，搜索引擎返回n 个页面，把 这n 个页面作为根集s 。由根集进一步扩展，加入所有由根集中的页所指的页， 以及所有指向根集页的页，扩展为一个更大的集合基本集t 。基本集中 的所有h u b 页面为集合v l ，所有a u t h o r i t y 页面集合为v 2 。k l e i n b e r g 认为得到的 理想的基本集t 应具有以下特点：t 相对较小，t 中的相关网页丰富，t 中包含 多数最有价值的a u t h o r i t y 页面汹。 h i t s 算法思想如下： 给定一个宽主题搜索查询q ，。将该查询q 提交给传统的基于关键字匹配的 搜索引擎，搜索引擎会返回很多网页。从这些网页中提取排序分值最高的一 组构成一个根集( r o o t s e t ) ，把这个根集用s 来表示。s 满足三个条件：s 中 的网页数量相对较少，s 中网页大多数是与q 相关的网页，s 中的网页大多是 权威的网页。用s 中页面的邻近页面( 即s 中页面链接的所有页面和有超链指 向s 中页面) 来扩充s ，形成一个页面基集( p a g e b a s e s e t ) ，把这个页面基集 用t 来表示。扩充时可忽略仅因同一站点的内部链接加入的页面，当然还可 以通过分析u r l 忽略因非信息链而加入的页面。 以t 中的h u b 网页为定点集v 1 ，以a u t h o r i t y 网页为顶点集v 2 ，v 1 中的网页 至f j v 2 中的网页的超链接为边集e ，从页面基集t 导出页面邻域图s g = ( y ，e ) ( s g 中结点表示t 中的页面) 。用h v 】表示网页v 的h u b 值，用a i r 】表示网页v 的a u t h o r i t y 值，h i t s 算法对邻域图s g = ( v ，e ) 中每个结点v 赋予两种排序分 值：a u t h o r i t y 值a v 】与h u b 值h v 】。前者用于度量一个页面的权威性，而后者 1 5 哈尔滨工程大学硕士学位论文 用于度量一个页面的中心性。任一结点v 的a u t h o r i t y 值和h u b 值分别用以下两 种操作计算如图2 。3 所示。 ，操作：a ( ，】= ( a c a ，v ) )d 操作：组v 】- ( g ( ，g ” 图2 3i 操作与o 操作 图2 3 中，2 个结点的权威与中心分值分别构成两个n 维( 列) 向量a s 。和 h s i l 。为打破两种分值计算时的循环关系，需要一个迭代过程来计算向量口 和h ：( 1 ) a 和h 初始化为向量z = ( 1 ，l ，1 ) ，z s l i ；( 2 ) 对向量a 和h 进行反复迭代计算，即交替地在h 上运用i 操作来计算a ，在口上运用o 操 作来计算h ，每次迭代后对a 和h 进行单位化，使它们成为s l 上的单位向量 ( u n i tv e c t o r ) ；( 3 ) 分别将s g 中c 个( 典型地，设置c = 5 1 0 ) 具有最大a 和 h 坐标值( 即最高a u t h o r i t y 值和h u b 值) 的结点分别作为a u t h o r i t y 和h u b 输出”。 通过h u b 页和a u t h o r i t y 页的相互作用，h i t s 算法能够更好的描述互联网的 一种重要组织特点：a u t h o r i t y 页之间的关联通常是通j 吐h u b 页发生的。但是， 值得注意的是，虽然p a n g e r a n k 算法与h i t s 算法都是通过迭代的方法计算相 邻矩阵的特征向量。h i t s 算法所针对的不是整个互联网结构图，而是特定查 询主题的互联网子图。规模上的极大减少可以使h i t s 算法的迭代收敛速度比 p a g e r a n k 要快得多，但因为与查询相关，所以查询过程需要考虑排序的代价。 另外，除非为h i t s 算法中所考虑的链接赋予适当的权值，否则相邻矩阵的主 特征向量并不能反映最合理的网页价值度排列。并且即便对子图中的边赋予 了适当的权重，如果子图的相邻矩阵是一个可约减的矩阵( 例如图中有多个 不连通的部分) ，那么很多有价值的网页仍将无法在主特征向量中得到体现。 更为严重的是，在对很多广义主题进行查询时，h i t s 算法会错误地将许多与 主题无关的网页赋予很高的价值度。例如，当查询“电影奖 时，得到的结 果却是许多电影公司的主页。这是因为和“电影奖 有关的网页通常会链接 1 6 哈尔溪程大学硕士学位论文 i 电影公司的主页，由于电影公司主页的商业性，大量的链接会发生在这些公 司主页之间，从而