（计算机应用技术专业论文）个性化搜索引擎的研究与实现(1).pdf

北京工商大学硕士学位论文 摘要 随着i n t e r n e t 技术的迅速发展，网络提供给人们的信息量越来越大。搜索引 擎作为人们在w w w 上查找、获取信息的重要手段之，在各个领域都已得到 了广泛的应用。为了给用户提供个性化的查询服务，个性化搜索引擎孕育而生。 经过众多研究者的不懈努力，个性化搜索引擎技术已取得了一些进展。本文针对 目前搜索引擎存在的不足以及当前用户个性化查询的要求，在深入研究搜索引擎 及相关技术的基础上，设计了一个基于用户兴趣挖掘的个性化搜索引擎模型。 本文的主要工作是： ( 1 ) 个性化模型的研究与实现 本文深入分析了个性化搜索的特点，研究了搜索引擎及相关技术，设计了一 个基于用户兴趣挖掘的个性化模型。该模型从用户的历史访问页面中提取用户的 兴趣特征，将兴趣相同的页面进行归类，并将用户兴趣按类管理；本文参考了 o d p 的目录层次结构，构建了用户兴趣树来动态地存储用户兴趣，并通过短期 兴趣和长期兴趣相结合的方式来描述用户兴趣特征；为了及时地反映用户的兴趣 变化，本文采用了基于遗忘机制的兴趣更新算法。 ( 2 ) 个性化搜索引擎( 除个性化模型外) 其他模块的研究与实现 本文还研究了与个性化搜索引擎相关的其他模块，包括：中文分诩、查询扩 展、网络蜘蛛、索引建立与更新以及结果排序。在综合考虑了技术的实现难度和 用户个性化查询要求的基础上，本文给出了以上各模块的实现算法。 ( 3 ) 通过实验证明了本文设计的个性化搜索引擎的有效性。实验内容包括两 方面：个性化模型的建立和个性化的搜索。 关键词：个性化模型，用户兴趣挖掘，用户兴趣树 个性化搜索引擎的研究与实现 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e tt e c h n o l o g y , t h en e t w o r kc a np r o v i d e p e o p l em o r ea n dm o r ei n f o r m a t i o n s e a r c he n g i n eh a sb e e nw i d e l yu s e di nm a n y f i e l d s ，w h i c hi st r e a t e da sat o o lt h a tp e o p l ec a ng e ti n f o r m a t i o no nw o r l dw i d ew e b i no r d e rt op r o v i d ep e r s o n a l i z e ds e a r c hs e r v i c ef o ru s e r s ，p e r s o n a l i z e ds e a r c he n g i n e c o m e sf o r t h b e c a u s eo fm a n yr e s e a r c h e r sc o n t r i b u t i o n , p e o p l eh a v em a d eg r e a t p r o g r e s si np e r s o n a l i z e ds e a r c he n g i n e t h i sp a p e rp o i n t so u tt h es h o r t a g eo fc u r r e n t s e a r c he n g i n ea n du s c r sr e q u i r e m e n t so fp e r s o n a l i z e ds e a r c h , d o e ss o m er e s e a r c ho n s e a r c he n g i n ea n di t st e c h n o l o g y , a n dd e s i g n sap e r s o o a l i z e ds e a r c he n g i n em o d e lt h a t i sb a s e do nu s e r si n t e r e s t sm m i n g t h em a i nt a s k so ft h ep a p e ra r ea sf o l l o w s ： f i r s t l y , t h i sp a p e rr e s e a r c h e sa n di m p l e m e n t st h ep e r s o n a lm o d e l t h i sp a p e ra n a l y z e st h ec h a r a c t e r so fp e r s o n a l i z e ds e a r c h , r e s e a r c h e st h es e a r c h e n g i n ea n di t st e c h n o l o g y , a n dd e s i g n sa m o d e lt h a ti sb a s e do nu s f r si n t e r e s t sm i n i n g t h em o d e lg e t su s e r si n t e r e s t sf r o mt h ep a g e st h a th eh a sv i s i t e db e f o r e ，c l a s s i f i e st h e p a g e sa c c o r d i n gt ot h es a m ei n t e r e s t ra n dm a n a g e st h eu s e r si n t e r e s t sa c c o r d i n g t ot h e i n t e r e s tt y p e s a st ot h es t o r a g eo fu s e r si n t e r e s t s , t h i sp a p e rc o n s u l t st h eo d p c a t a l o g s t r u c t u r e ，e s t a b l i s h e su s e ri n t e r e s tt r e et os t o r et h eu s e r si n t e r e s t s ，a n du s e st h es h o r t i n t e r e s ta n dl o n gi n t e r e s tt od e s c r i b et h eu s e r si n t e r e s tc h a r a c t e r s i no r d e rt or e f l e c t u s e r si n t e r e s t sc h a n g i n gi nt i m e ，t h i sp a p e ru p d a t e su s e r si n t e r e s t su s i n gt h e a l g o r i t h mb a s e do nf o r g e t t i n gm e c h a n i s m s e c o n d l y , t h i sp a p e rr e s e a r c h e sa n di m p l e m e n t so t h e rm o d u l e so fp e r s o n a l i z e d s e a r c he n g i n eb e s i d e st h ep e r s o n a lm o d e l t h em o d u l e si n c l u d ec h i n e s es e g m e n t i n g , s e a r c he x t e n d i n g , n e t w o r ks p i d e r , i n d e xe s t a b l i s h m e n ta n du p d a t ea n dr e s u l tr a n k i n g t h i sp a p e rt a k e st h ei m p l e m e n t i n gd i f f i c u l t yo fr e l a t e dt e c h n o l o g ya n du s e r s r e q u i r e m e n t so fp e r s o n a l i z e ds e a r c hi n t oa c c o u n t ，a n db r i n g sf o r w a r dt h ea l g o r i t h m s o ft h em o d u l e sa b o v e a tl a s t , e x p e r i m e n t sa r ec o n d u c t e dt ov e r i t yt h ee f f i c a c yo ft h ep e r s o n a l i z e d s e a r c he n g i f i ed e s i g n e da b o v e t h ec o n t e n t so ft h ee x p e r i m e n ti n c l u d et w op a r t s ：t h e i l 北京工商大学硕士学位论文 e s t a b l i s h m e n to fp e r s o n a lm o d e la n dt h ep e r s o n a l i z e ds e a r c h k e y w o r d s ：p e r s o n a lm o d e i u s e r s i n t e r e s t sm i n i n g u s e r in t e r e s tt r e e 1 1 1 北京工商大学学位论文原创性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下进行的研究工作所 取得的研究成果。除了文中已经注明引用的内容外，论文中不包含其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体， 均己在文中以明确方式标明。本声明的法律后果完全由本人承担。 学位论文作者签名：亟墨霆：日期：御手占月彰日 北京工商大学学位论文授权使用声明 本人完全了解北京工商大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属北京工商大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以采用影印、缩印或其它复 制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 学位论文电子版同意提交后，可于口当年口一年口二年后在学校图 书馆网站上发布，供校内师生浏览。 学位论文作者签名：剖壶望导师签名；心期：卯年占月2 宣 北京工商大学硕士学位论文 1 1 课题研究背景及意义 一、绪论 随着互联网的迅猛发展，各种信息正以几何级数的方式增长，信息量的增多 使得用户很难得到自己所需要的信息。据c 2 s n i c 统计，到2 0 0 4 年6 月已经有 中文w e b 站点将近6 0 6 6 0 0 个【l 】o 为了从互联网上获得信息，用户通常使用搜索 引擎这个网络信息检索工具。 搜索引擎( s e a r c he n g i n e ) 是从1 9 9 5 年开始逐渐发展起来的技术。搜索引 擎以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处 理，并为用户提供检索服务，从而起到信息导航的作用。搜索引孥提供的导航服 务已经成为互联网上非常重要的网络服务。因此，搜索引擎站点也被美誉为“网 络门户”。 人们在进行信息检索时，总希望找到所有与兴趣相关的文档，可是在i n t e r n e t 这个开放的信息空间里实现这个目标非常困难。这就需要能够真正考虑用户的特 点、动机和需求，以用户为中心来构建搜索的方法、技术、结果与过程。个性化 搜索引擎就是基于这样的思想提出来的。本文对个性化搜索引擎技术进行了一些 研究，目的在于探索个性化搜索的方法，提出一种能满足不同用户需求的信息搜 索模型。在该模型的帮助下，人们能更好地在l q t e r n e t 中找到自己所需要的资源。 因此本文的研究具有重要的现实意义。 1 2 本文的研究内容 在深入分析了中文分词、查询扩展、网络蜘蛛、索引建立与更新、结果排序 等搜索引擎核心技术的基础上，并结合用户对检索结果的个性化要求，本文设计 了一个基于用户兴趣挖掘的个性化搜索引擎。该引擎把用户的需求放在第一位： 对用户信息进行管理、对用户历史查询进行跟踪、并对用户的信息进行学习，得 到用户的兴趣所在，再对用户的兴趣进行判断，不断地更新用户兴趣。只有知道 用户兴趣所在，力能针对用户的查询进行个性化信息服务。提高用户的相关度， 个性化搜索引擎的研究与实现 进而提高查准率和查全率。 1 3 本文的组织结构 本文各章节的主要内容是： 第一章是绪论，主要阐述本文的研究背景及意义、研究内容和组织结构； 第二章是搜索引擎的综合研究，主要内容包括：搜索引擎的概念、工作原理、 分类、评价标准、发展现状以及发展趋势： 第三章建立了个性化搜索引擎的理论模型，并研究了个性化搜索引擎的关键 技术； 第四章提出了基于用户兴趣挖掘的个性化模型； 第五章研究了个性化搜索引擎的其他模块( 除个性化模型外) ，并给出了各 模块的实现算法； 第六章通过实验证明了本文设计的个性化搜索引擎满足设计要求； 第七章笔者对全文的工作进行了总结，并提出了本文进一步的研究方向。 北京工商大学硕士学位论文 二、搜索引擎的综合研究 2 1 搜索引擎的概念 搜索引擎( s e a r c he n g i n e ) 是指能够自动地对w w w v 资源进往分析处理， 并通过查询为用户返回匹配资源的系统1 2 】。它包括信息搜集、信息整理和用户查 询三部分。 搜索引擎是一个为用户提供信息“检索”服务的网站，它能够帮助人们在茫 茫网海中搜寻到所需要的信息。 2 2 搜索引擎的工作原理 搜索引擎的工作过程可以简单的描述为：通过网络蜘蛛定期在 n t e r n e t 上爬 行，发现新的网页，并把它们取出来放到本地数据库中，用户查询请求可以通过 查询本地数据库来得到结果。 搜索引擎的工作过程主要有以下几步： ( 1 ) 每个独立的搜索引擎都有自己的网页抓取程序( s p i d e r ) 。s p i d e r 顺着网 页中的超链接，连续地抓取网页。理论上，从一定范围网页出发，就能搜集到绝 大多数的网页。 ( 2 ) 搜索引擎抓到网页后，还要做大量的预处理工作，才能提供检索服务。 其中，最重要的是提取关键词、建立索引文件。此外还包括去除重复网页、分析 超链接、网页评分等。 ( 3 ) 提供检索服务。用户输入关键词进行检索，搜索引擎从索引数据库中找 到匹配该关键词的网页；同时为了便于用户判断，除网页标题和u r l 外，还会 提供一段来自网页的摘要以及其他信息。 2 3 搜索引擎的分类 搜索引擎按其工作方式可以分为三类：目录索引类搜索引擎、全文搜索引擎 和元搜索引擎。 个性化搜索引擎的研究与实现 目录索引类搜索引擎：它虽然有搜索功能，但在严格意义上算不上真正的搜 索引擎，仅仅是按目录分类的网站链接而已。用户完全可以不用进行关键词的查 询，仅靠分类目录也可找到需要的信息。目录索引中最具有代表性的是y a h o o 。 全文搜索引擎：国外具有代表性的有g o o g l e 、a l t a v i s t a 、i a k t a n i 等，国内著 名的有百度。他们都是通过从互联网上提取的各个网站的信息( 以网页文字为主) 来建立起数据库，检索与用户查询条件匹配的相关记录，然后按一定的排列顺序 将结果返回给用户，因此它们是真正的搜索引擎。 元搜索引擎：元搜索引擎在接受用户查询请求时，同时在其他多个引擎上进 行搜索，并将结果返回给用户。著名的元搜索引擎有i n f o s p a c e 、d o g p i l e 等，中 文元搜索引擎中具有代表性的是搜星搜索引擎。在搜索结果排列方面，有的直接 按来源引擎排列搜索结果，如d o g p i l e ：有的按自定义的规则将结果重新排列组 合，如v i v i s i m o 。 2 4 搜索引擎的评价标准 一般来说，搜索引擎的评价标准p h 6 1 主要有收录范围、检索功能、结果显示、 检索效率、用户接口几个方面。 ( 1 ) 收录范围 每秘搜索引擎都有特定的收录对象。选择搜索系统必须先对该搜索引擎简单 了解，知道它是专题型搜索引擎还是综合型搜索引擎。若是专题型搜索引擎，看 它侧重于哪个方面；若是综合型的搜索引擎，则它检索到的信息比较全面。 ( 2 ) 检索功能 每种搜索引擎所提供的检索功能虽略有不同，但大致包含布尔逻辑、词组查 询、相近检索、限制字段等功能，或进一步提供相似性反馈信息、关键词检索、 自然语句输入等较先进功能。 ( 3 ) 检索结果的显示 查询结果的输出方式也是评价的重点之一，因为输出方式不好会阻碍浏览的 效果。一些搜索系统根据资源与查询的相关性柬排序，最相关的资料就会排在前 面，有些系统允许使用者自定义资料显示的数量，可节省浏览时间，另外显示资 料的详细程度也会影响资料的参考价值。 4 北京工商大学硕士学位论文 ( 4 ) 检索效率 在评价检索效率时可从查全率、查准率及反应时间等方面考虑。查全率是系 统在进行某一检索时，检出的相关文献量与系统文献库中相关文献总量的比率， 即：查全率= 检出相关文献量文献库内相关文献总量。查准率是指所检出的相关 文献占所有检出文献的比率。查全率和查准率是衡量检索系统检索效果的两个最 重要的指标，两者结合使用就能反映一个检索系统的基本检索效果。 ( 5 ) 用户接口 用户接口的设计也是评价搜索引擎一个相当重要的因素，因为设计不良，即 使查询功能再多、再好，也可能无法吸引大众使用。界面要简单大方，并提供辅 助说明或系统特性介绍。 2 5 搜索引擎的发展现状 1 9 9 4 年初第一代真正基于w w w 的搜索引擎l y c o s 诞生。第一代搜索引擎 以人工分类的目录分类为主，代表厂商是y a h o o 。其特点是用人工的方式把网站 放在各种目录下，允许用户通过各种方式找到想要的网站，现在这种方式依然存 在。但随着网络应用技术的发展，用户不再满足于这种对网站分类和摘要的简单 查找，更希望对内容进行查找，于是就出现了关键词查询，即第二代搜索引擎。 这时最有代表性的是g o o g l e ，它使用关键词进行网页搜索，内容可以覆盖互联 网大部分的网页内容。与第一代搜索引擎相比，第二代搜索引擎在收录范围、数 据库更新频率，捡索能力、查全率，查准率，响应时间、结果输出，用户负担等 性能方面均有了很大地提高，但仍然存在不少局限性，比如信息丢失、返回过多 无用信息及信息无关等等。在这种背景下，出现了第三代搜索引擎。比如，2 0 0 3 年8 月2 0 日慧聪国际软件推出的慧聪搜索引擎w w w h u i c o n g t o m ( 现已更名为 中国搜索h t t p ：w w w z h o n g s o u c o r n ) 就是第三代搜索引擎的典型代表。它是在第 二代搜索引擎基础上通过其世界领先的文本分析及集合技术进一步优化搜索结 果，实现了人工智能和搜索引擎技术的完美结合。毫无疑问，随着搜索技术的不 断发展，未来第三代搜索引擎的功能会得到不断地加强，能够为用户提供更快、 更准、更方便的查询门。 据n i e l s e n n e t r a t i n g s 的最新数据显示，2 0 0 5 年1 2 月份全球6 5 个搜索引 个性化搜索引擎的研究与实现 擎的搜索总量达5 0 多亿次，其中8 0 以上的搜索量来自三大搜索引擎g o o g l e 、 y a h o o 和m s n 。g o o g l e 已经占据美国在线搜索市场的一半份额；2 0 0 5 年百度 公司的成功上市创造了中文搜索引擎的神话；2 0 0 5 年1 1 月1 7 日c j 0 0 9 t e 公 司的股价一度超过4 0 0 美元。这一切都说明搜索引擎已经成为互联网的第四桶 金嗍。 从1 9 9 4 年起，i n t e r a c t 在中国开始蓬勃发展，到1 9 9 7 年国内开始发展面向 中文信息检索的中文搜索引擎【9 j 。由于中文信息处理较英文信息更为复杂，中文 搜索引擎的研制也是最近几年才兴起，但其发展却十分迅速。据“中文导航及搜 索引擎指南”统计，目前国内较完备的搜索引擎有1 3 1 个，中文繁体搜索引擎2 1 4 个，这些还不包括一些开展信息服务的图书馆等其他信息服务网站。其中，用户 常用的搜索引擎有新浪、搜狐、雅虎中文、天网、百度、网易、悠游等。近年来 国外一些网络企业也开始瞄准中国互联网这一潜在的巨大市场，先后推出了一些 中文版的搜索引擎i l o l 。 我国对中文搜索引擎的研究工作已经全面展开。涉及的领域相当广泛，但专 业性、针对性强的研究成果还不是很多，在很多方面暴露出以下不足： ( 1 ) 语言理解能力差，不能满足用户个性化的需求 当前急需解决的问题是根据用户仅有的几个输入词，来猜测用户要查什么， 即：理解用户的需求和查询的兴趣。 ( 2 ) 查询精度不高 目前搜索引擎在返回精确的查询结果方面不够理想。用户通常为大量的与查 询无关的返回结果所困扰，所以需要加强信息过滤等搜索方法的研究。 ( 3 ) 对动态网页的处理能力弱 目前许多搜索引擎的查找对象仅仅为可访问的页面，有些用于生成动态页面 的后台数据库还不能访问，搜索引擎的搜索范围应扩大到动态页面。 ( 4 ) 查询覆盖面有限 据权威统计，目前搜索页面最多的搜索引擎a l t a v i s t a 也只能达到信息量的 4 0 左右。 6 北京工商大学硕士学位论文 2 6 搜索引擎的发展趋势 搜索引擎已成为一个新的研究、开发领域。因为它要用到信息检索、人工智 能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理 等多领域的理论和技术，所以具有综合性和挑战性。又由于搜索引擎有大量的用 户，有很好的经济价值，所以引起了世界各国计算机科学界和信息产业界的高度 关注，目前的研究、开发十分活跃，并出现了很多值得注意的动向。 ( 1 ) 十分注重提高信息查询结果的精度，提高检索的有效性 用户在搜索引擎上进行信息查询时，并不十分关注返回结果的多少，而是看 结果是否和自己的需求吻合。对于一个查询，传统的搜索引擎动辄返回几十万、 几百万篇文档，用户不得不在结果中筛选。为了解决查询结果过多的问题，目前 出现了几种方法：一是通过各种方法获得用户没有在查询语句中表达出来的真正 意图，包括使用智能代理跟踪用户检索行为，分析用户模型；使用相关度反馈机 制，让用户告诉搜索引擎哪些文档和自己的需求相关( 及其相关的程度) ，哪些 不相关，通过多次交互逐步求精。二是用正文分类( t e x tc a t e g o r i z a t i o n ) 技 术将结果分类，使用可视化技术显示分类结构，用户可以只浏览自己感兴趣的类 别。三是进行站点聚类或内容聚类，减少信息的总量。 ( 2 ) 基于智能代理的信息过滤和个性化服务 信息智能代理是另外一种利用互联网信息的机制。它使用自动获得的领域模 型( 如w e b 知识、信息处理、与用户兴趣相关的信息资源、领域组织结构) 、用 户模型( 如用户背景、兴趣、行为、风格) 知识进行信息搜集、索引、过滤( 包 括兴趣过滤和不良信息过滤) ，并自动地将用户感兴趣的、对用户有用的信息提 交给用户。智能代理具有不断学习、适应信息和用户兴趣动态变化的能力，从而 提供个性化的服务。智能代理可以在用户端运行，也可以在服务器端运行。 ( 3 ) 采用分布式体系结构提高系统规模和性能 搜索引擎的实现可以采用集中式体系结构和分布式体系结构，两种方法各有 千秋。但当系统规模到达一定程度( 如网页数达到亿级) 时，必然要采用某种分 布式方法，以提高系统性能。搜索引擎的各个组成部分，除了用户接口外，都可 以进行分布式处理：网络蜘蛛可以在多台机器上相互合作、相互分工进行信息发 现，以提高信息发现和更新的速度；索引器可以将索引分布在不同的机器上，以 7 个性化搜索引擎的研究与实现 减小索引对机器的要求；检索器可以在不同的机器上进行文档的并行检索，以提 高检索的速度和性能。 ( 4 ) 重视交叉语言检索的研究和开发 交叉语言信息检索是指用户用母语提交查询，搜索引擎在多种语言的数据库 中进行信息检索，返回能够回答用户问题的所有语言的文档。如果再加上机器翻 译，返回结果可以用母语显示。该技术目前还处于初步研究阶段，主要的困难在 于语言之间在表达方式和语义对应上的不确定性。但对于经济全球化、互联网跨 越国界的今天，无疑具有很重要的意义。 北京工商大学硕士学位论文 三、个性化搜索引擎理论模型及主要技术研究 由于传统搜索引擎不能满足用户个性化查询的要求，因此本章提出了个性化 搜索引擎的理论模型。并在此基础上研究了个性化搜索引擎的主要技术。 3 1 个性化搜索引擎的理论模型 本模型的提出主要借鉴的个性化信息检索系统有：s m a r t l l 、o b i w a n l l 甜、 s w r l l 习、w b i 【1 4 j 、p e r s o n a lw e bw a t c h e r l l 5 】、t r e y 1 甜、s y s k i l l & w e b e r t l l 刀等。 幽 一1 概念提取h 查询扩展h c i n t e r 一n e 研 用 1 一网 户 检f c i 接 索 l 索引i 络 1 数据t -蜘 器 【库 蛛 口、 _ _ _ _ _ _ _ _ 风 一结果排序u 图3 1 个性化搜索引擎理论模型 该模型与传统的搜索引擎相比，具有如下优势： ( 1 ) 用户接口具有更大的灵活性。用户可以根据喜好定制感兴趣的内容； ( 2 ) 增加了用户兴趣库，提高了查询结果的用户贴近度，较好地满足了用户 检索的个性化要求。 个性化搜索引擎克服了传统搜索引擎的很多不足。它能智能地理解用户的信 息需求，为用户提供准确、可靠和方便的信息服务。它能够完成如下工作： ( 1 ) 充分了解用户的相关信息，建立并逐步完善用户模型； ( 2 ) 根据用户模型和历史记录，及时地对检索到的信息进行相关性判断； ( 3 ) 自动地更新用户兴趣； 个性化搜索引擎的研究与实现 ( 4 ) 友好的用户界面有助于人机之问的交互。 3 2 个性化搜索引擎主要技术研究 3 2 1 用户接口 用户接口主要负责和用户直接接触的事件。主要功能点包括： ( 1 ) 用户查询界面 查询界面简洁明了，用户想要获得个性化查询结果，必须首先登录系统。 ( 2 ) 用户注册 首次登录系统时，用户要进行注册，系统对用户的相关信息( 如背景知识、 研究领域等) 进行记录，以便对用户兴趣进行后续分析。通过注册，系统会为 每一个用户建立一个唯一的帐号，用户的个人兴趣信息以这个帐号为标识存放在 用户兴趣库中。系统通过一定的个性化、智能化算法对这些数据进行分析，为用 户提供个性化的查询。 ( 3 ) 个性化界面选择 对于注册用户，可以根据用户的定制要求来设置页面，满足不同用户的个性 化要求。 ( 4 ) 个性化内容定制 用户在注册时可以选择自己感兴趣的类型，模型将这些兴趣类存放在用户兴 趣库中，以便为用户提供个性化的查询结果。 ( 5 ) 查询结果显示 结合用户兴趣库对用户兴趣的分析，得到合理的用户结果显示序列。 3 2 2 中文分词 中文分词技术属于自然语言处理技术范畴。对于一句话，人可以通过自己的 知识来明白哪些是词、哪些不是，但让计算机理解则需要一个处理过程。该过程 就是中文分词。 现有的分词算法分为三类：基于字符串匹配的分词方法、基于统计的分词方 法和基于理解的分词方法1 1 8 l 。1 2 0 l 。 1 0 北京工商大学硕士学位论文 3 2 2 1 基于字符串匹配的分词方法 这种方法又叫机械分词方法，它是按照一定的规则将待分析的汉字串与一个 很大的机器词典中的词条进行匹配，若在词典中能找到某个字符串，则匹配成功 ( 识别出一个词) 。按照扫描的方向不同，可以分为正向匹配、逆向匹配和双向 匹配：按照不同长度优先匹配的情况，分为最大匹配和最短匹配。常用的几种机 械分词方法如下： ( 1 ) 正向最大匹配法； ( 2 ) 逆向最大匹配法。 l 、正向最大匹配法 亦称m m 法( m a x i m u mm a t c h i n gm e t h o d ) 。其基本思想是：假设自动分词 词典( 或词库) 中的最长词条是i 个字，则取被处理材料当前字符串序列中的前 i 个字作为匹配字段，查找词典，若词典中存在这样的一个j 字词，则匹配成功， 匹配字段被作为一个词切分出来；否则，匹配字段去掉最后一个字，剩下的字段 重新进行匹配，如此进行下去，直到匹配成功，也就是完成一轮匹配，切分出一 个词为止。 正向最大匹配算法如图3 2 。 个性化搜索引擎的研究与实现 图3 2 正向最大匹配算法 该方法扫描方向是从左到右，从长到短的顺序进行匹配，其原理简单，易于 在计算机上实现，时间复杂度也较低。 正向最大匹配法的缺点： ( 1 ) 忽视“词中有词”的现象，导致切分错误。例如对字符串“幼儿园地节 目”进行切分时，正向最大匹配法的切分结果是“幼儿园，地，节目”，而正确的切 分结果应该是“幼儿园地，节目”； ( 2 ) 最大词的长度难于确定。如果定得太长，则匹配时花的时间多，算法的 时间复杂度明显提高；如果定得太短，则不能切分长度超过它的词，从而导致切 分正确率降低。 2 、逆向最大匹配法 亦称r m m 法( r e v e r s em a x i m u mm a t c h i n gm e t h o d ) 。其基本原理和正向最 大匹配法相同，不同的是切词方向。它从被处理材料的末端开始匹配，每次取最 末端的i 个字作为匹配字段，匹配失败则去掉字段最前面的一个字。 逆向最大匹配法的原理与正向最大匹配法相同，只是扫描方法是自右到左， 在此不再赘述，算法流程图如图3 3 。 1 2 北京工商大学硕士学位论文 图3 3 逆向最大匹配法流程图 3 2 2 ，2 基于词频统计的方法 介绍这种方法之前，先给出两个定义： 定义1 ：按字索引 设一个文本d 可以描述为d = s i $ 2 s 3 s n ，s i 为字符。二元组集合 ( s t ，p o 。 ( s 2 ，p 2 ) ，( s 3 ，p 3 ) ，o o9 ( s n ，p n ) ，称为该文本的按字索引，其中，在二元组 ( s i ，p i ) 中，p i 为s i 在文本中的位置。 定义2 ：字共现 设串s is i + l 所产生的按字索引为 ，( s i 。p i ) ，( s i + l ，p i + 1 ) ，( s i + m ， p i + m ) ， ，具有s i = s t + m ，s = s i + m 1 ，p i + l = p l + 1 ，p i + m + l = p i + m + 1 的特性，则 个性化搜索引擎的研究与实现 称s l s i + 1 为( s i 。，s i + m + 1 ) 为2 字符长度的1 次共现。 依此类推，可以定义：2 字符长度的n 次共现。进一步，可定义：k 字符长 度的n 次共现1 2 1 l 。 基于词频统计的方法不依赖词典，而是对文章中连续出现的字串进行共现频 度统计，将共现频度大于某一标准的字串当作一个词。所谓共现频度是利用词频 统计方法判断字串是否成词的一种度量单位，一般认为共现频度与字串的长度以 及该字串在文章中出现的次数成正比。即w = f x l ，其中w 为字串的频度，f 为 字串在文章中出现的次数，l 为该字串的长度。此时如果设成词的阀值为8 ，则 两字词必须至少出现4 次才能识别出来；三字词必须至少出现3 次才能识别出来， 依此类推。当然，词的长度不能超过某个值，通常认为词的最大长度为6 。共现 频度可以根据语料的范围通过实验来确定，例如也有人定义w = f xl 3 。词频统 计法的分词精度不是很高，但通过这种方法可以很好的提取出入名、地名等一些 词典中不包含的专有名词。对于那些专业性很强的文章，这种分词方法往往能更 有效地提取出那些能反映文章主题的词语。 3 2 2 3 基于理解的分词法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其 基本思想是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理 歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在 总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对 分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大 量的语言知识和信息。由于汉语语言知识的笼统性和复杂性，难以将各种语言信 息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处于试验阶 段。 3 2 2 ，4 其他切词方法 还有一些其他的切词方法： 逐词遍历匹配法：它把词典中的词按照由长到短递减的顺序逐个搜索匹配整 个待处理丰于料，直到把所有的词都切分出来为止。 1 4 北京工商大学硕士学位论文 设立切分标志法：这种方法首先要收集那些标点符号( 称为自然切分标志) 以外的众多非自然切分标志。例如，只充当词首字或词尾字的字，对这些非自然 切分标志进行搜索，根据这些标志，把句子切分为若干较短的字段，然后再使用 m m 或者r m m 等方法进行进一步地切分。准确地说，这种方法并不是一种真正 意义上的分词方法，只不过是自动分词的一种前处理方式而已。而且，这种前处 理并没有提高分词精确度，却要额外消耗时间扫描切分标志，增加分词的时间复 杂度。 正向最佳匹配法和逆向最佳匹配法：最佳匹配法的出发点是在词典中按词频 的大小排列词条，以求缩短对分词词典的搜索时间，达到最佳效果，从而降低分 词的时间复杂度，以加快分词速度。实际上，这是对分词词典预先进行的一种加 工，也不是纯粹意义上的一种分词方法。 3 2 3 查询扩展 查询扩展是指通过利用己建立好的词典库或知识库来进行查询词条扩展，以 提高搜索引擎的召回率和查准率。在对用户的初始查询特征词进行适当分析后， 查询扩展将具有相同概念属性的特征词加入到初始查询词中，形成更加丰富的用 户查询，以提高查询精度。比如：。信息检索”一“信息检索”a n d “搜索引擎”； “电脑”一“电脑”o r “计算机”。 查询扩展的方法分为三类：基于用户注册兴趣的方式、基于用户对结果集操 作反馈信息的方式、基于搜索结果文档集全局信息的方式l 捌。这些方法分别通过 不同的途径扩展用户初始查询，以期提高查询结果的用户贴近度。用户兴趣注册 的方式最准确和易于实现，但用户必须先注册；用户反馈信息挖掘的方式中，用 户不需任何额外的操作，但搜索引擎的工作量会更大，挖掘的准确度也难以控制， 而挖掘本身也涉及用户隐私许可问题；基于搜索结果文档集全局信息的方式目前 已经有很好的实现，在很大程度上解决了查询扩展的问题。 1 5 个性化搜索引擎的研究与实现 3 2 4 网络蜘蛛 3 2 4 。1 网络蜘蛛工作原理 网络蜘蛛例【卅是通过网页的链接地址来寻找网页，从网站某一个页面( 通 常是首页) 开始，读取网页的内容，找到网页中的其它链接地址，然后通过这些 链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓 取完为止。 如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网 上所有的网页都抓取下来。对于搜索引擎来说，要抓取互联网上所有的网页几乎 是不可能的。从目前公布的数据来看，容量最大的搜索引擎也不过是抓取了整个 网页数量的百分之四十左右。这其中的原因一方面是抓取技术的瓶颈，无法遍历 所有的网页，有许多网页无法从其它网页的链接中找到；另一个原因是存储技术 和处理技术的问题，如果按照每个页面的平均大小为2 0 k 计算( 包含图片) ，1 0 0 亿网页的容量是1 0 0 2 0 0 0 6 字节，即使能够存储，下载也存在问题( 按照一台 机器每秒下载2 0 k 计算，需要3 4 0 台机器不停的下载一年时间，才能把所有网 页下载完毕) 。同时，由于数据量太大，在提供搜索时也会有效率方面的影响。 因此，许多搜索引擎的网络蜘蛛只是抓取那些重要的网页，而在抓取候评价重要 性的主要依据是某个网页的链接深度。 3 2 4 2 抓取策略 在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先【z 引。 ( 1 ) 广度优先搜索策略。先搜索一层中的内容，然后再继续搜索下一层。例 如，一个h t m l 文件中的有三个超链，选择其中之一并处理相应的h t m l 文件， 然后不再选择第二个h t m l 文件中的任何超链，而是返回并选择第二个超链， 处理相应的h t m l 文件，再返回，选择第三个超链并处理相应的h t m l 文件等 等。一旦一层上的所有超链都已经选择过，就可以在刚处理过的h t m l 文件中 搜索其他的超链。这就保证对浅层链接首先处理。当遇到一个无穷尽的深层分支 时，不会陷进去。 ( 2 ) 深度优先搜索。这是一种在丌发s p i d e r 早期使用较多的方法，它的目的 北京工商大学硕士学位论文 是要达到被搜索结构的叶子节点( 即不包含任何超链的h t m l 文件) 。在一个 h t m l 文件中，当一个超链被选择后，被链接的h t m l 文件将实行深度优先搜 索，即在搜索其余的超链之前必须先完整地搜索单独的一条链。深度优先搜索适 宜遍历一个指定的站点或者深层嵌套的h t m l 文件集。但是对于规模较大的搜 索，深度优先搜索是一种比较糟糕的搜索方法，因为w e b 的结构很深，一旦进 去，也许就再也出不来了1 2 6 l 。 图3 4 网页抓取顺序图 广度优先搜索： 深度优先搜索： a _ b 、c 、d 、e 、f _ _ h 、g - i a - 】f l _ ( ； a b h i 3 2 4 ，3 网站与网络蜘蛛 有多种方法可以让网站和网络蜘蛛进行交流。一方面让网站管理员了解网络 蜘蛛都来自哪儿，做了哪些操作；另一方面也可以告诉网络蜘蛛哪些网页不应该 抓取，哪些网页应该更新。 每个网络蜘蛛都有自己的名字，在抓取网页的时候，都会向网站表明自己的 身份。网络蜘蛛在抓取网页时会发送一个请求，这个请求中有一个字段为 u s e r a g e n t ；用于标识网络蜘蛛的身份。例如g o o g l e 网络蜘蛛的标识为g o o g l e b o t ， 1 7 个性化搜索引擎的研究与实现 b a i d u 网络蜘蛛的标识为b a i d u s p i d c r ，y a h o o 网络蜘蛛的标识为i n k t o m is l u r p 。 如果在网站上有访问日志记录，网站管理员就能知道，哪些搜索引擎的网络蜘蛛 来过，什么时候来的，以及读了多少数据等等。如果网站管理员发现某个蜘蛛有 问题，就通过其标识来和其所有者联系。 网络蜘蛛进入一个网站，一般会访问一个特殊的文本文件r o b o t s i x t ，该文件 一般放在网站服务器的根目录下，如h t t p ：w w w b l o g c h i n a c o r n r o b o t s t x t 。网站管 理员可以通过r o b o l s t x t 来定义哪些目录网络蜘蛛不能访问，或者哪些目录对于 某些特定的网络蜘蛛不能访问。例如，有些网站的可执行文件目录和临时文件目 录不希望被搜索引擎搜索到，那么网站管理员就可以把这些目录定义为拒绝访问 目录。m b o t s 侄t 语法很简单，例如，对目录没有任何限制，可以用以下两行来描 述： u s e r - a g e n t ： d i s a l l o w ： 当然，r o b o t s 。t x t 只是一个协议，如果网络蜘蛛的设计者不遵循这个协议，网 站管理员也无法阻止网络蜘蛛对某些页面的访问，但一般的网络蜘蛛都会遵循这 个协议，而且网站管理员还可以通过其它方式来拒绝网络蜘蛛对某些网页的抓 取。 网络蜘蛛在下载网页的时候，会去识别网页的h t m l 代码，在其代码部分 会有m e t a 标识。通过这些标识，可以告诉网络蜘蛛：本网页是否需要被抓取， 以及本网页中的链接是否需要被继续跟踪。 现在一般的网站都希望搜索引擎能更全面地抓取自己网站的网页，因为这样 可以让更多的访问者能通过搜索引擎找到此网站。为了让本网站的网页更全面地 被抓到，网站管理员可以建立一个网站地图，即s i t em a p 。许多网络蜘蛛会把 s i t e m a p h t m 文件作为一个网站网页爬取的入口，网站管理员可以把网站内部所 有网页的链接放在这个文 牛中，网络蜘蛛就可以方便地把整个网站抓取下来，避 免遗漏某些网页，也会减小对网站服务器的负担。 3 2 4 ，4 网络蜘蛛内容提取 对于网络蜘蛛来说，抓取下来网页包括各种格式，包括：h t m l 、图片、d o e 、 ， 1 8 北京工商大学硕士学位论文 p a l 、多媒体、动态网页及其它格式等。这些文件抓取下来后，需要把这些文件 中的文本信息提取出来。准确提取这些文档的信息，一方面对搜索引擎的搜索准 确性有重要作用：另一方面对于网络蜘蛛正确跟踪其它链接有一定影响。 对于d o e 、n f 等文档，这种由专业厂商提供的软件生成的文档，厂商都会 提供相应的文本提取接口。网络蜘蛛只需要调用这些插件的接口，就可以轻松地 提取文档中的文本信息和其它相关的信息。 h t m l 等文档则不相同，h t m l 有一套自己的语法，通过不同的命令标识 符来表示不同的字体、颜色、位置等版式。提取文本信息时需要把这些标识符都 过滤掉。过滤标识符并非难事，因为这些标识符都有一定的规则，只要按照不同 的标识符取得相应的信息即可。但在识别这些信息的时候，需要同步记录许多