（计算机软件与理论专业论文）一种轻量级个性化搜索引擎的研究.pdf

哈尔滨工程大学硕士学位论文 摘要 如今网络搜索引擎成了人们获取信息的一个重要途径，人们在希望搜索 引擎能够提供全面的信息资源的同时，也对搜索引擎的服务提出了更高的要 求。如何能通过一种有效的方式获取最有用的信息是用户所需要的，也是个 性化搜索引擎必须提供的一种服务。 用户往往希望搜索引擎能够根据自己的实际情况来定制，这反应到信息 检索领域便是个性化的搜索服务。目前传统的基于服务器端的搜索引擎虽然 能够为用户解决兴趣搜索的需求，然而用户需要频繁地与行为数据库通信， 这将造成行为数据库的超负荷运行。 基于此，本文提出一种新式的搜索结构轻量级个性化搜索引擎，以 减少服务器端开销为目的，同时能够很好的解决因客户端存储限制的缺点造 成的排序误差。这模式结合了客户端存储资源与服务器端用户兴趣库，同时 引进了客户端服务代理技术，在一定程度上减少了服务器端用户兴趣库的访 问瓶颈。另外客户端、服务器端与客户端服务代理三者的松耦合连接方式增 加了个性化搜索引擎的灵活性。本文着重研究客户端、客户端服务代理与服 务器端的通信规则，详细研究了在为用户提供高质量兴趣搜索服务的基础上 如何减少三者之间的通信流量的问题。同时给出了客户端、客户端服务代理 与服务器端用户兴趣的获取与更新算法。最后通过实验系统验证了轻量级个 性化搜索引擎的可行性并与传统的基于服务器端的个性化搜索引擎进行了性 能比对分析。实验证明轻量级个性化搜索引擎在服务器性能方面得到了一定 程度的改善。 关键词：搜索引擎；个性化；用户模型；代理 哈尔滨工程大学硕士学位论文 a b s t r a c t u s i n gw r e bs e a r c he n g i n eh 缸b e c o m ea ni m p o r t a n tw a yf o ru s e r st og e t i n f o r m a t i o nf r o mt h ei n t e r n e t u s e r sh o p et h a tt h es e a r c he n g i n ec a np r o v i d e a l l a r o u n di n f o r r n a t i o nr e s o u r c e s h o wt o g e tt h em o s tv a l u a b l ei n f o r m a t i o n t h r o u g ha l le f f e c t i v ew a yf o ru s e r si sb e c o m i n gm o r ea n dm o r en e c e s s a r y , w h i c hi s a l s ob e c o m i n ga l li n d i s p e n s a b l es e r v i c et h a tt h ep e r s o n a l i z e ds e a r c he n g i n eh a v e t op r o v i d e u s e r s e x p e c t m i o no fs e a r c he n g i n ei st of i n daw a yf o rc u s t o m i z i n gt h e e n g i n ea c c o r d i n gt ot h e i ro w ni n t e r e s t s ，w h i c hi sa ni s s u eo fh o was e a r c he n g i n e c a np r o v i d ep e r s o n a l i z e ds e r v i c ei nt h er e a l mo fi n f o r m a t i o ns e a r c h a l t h o u g ht h e t r a d i t i o n a ls e r v e r - b a s e ds e a r c he n g i n ec a nm e e tu s e r s d e m a n d so fp e r s o n a l i z e d s e a r c hs e r v i c e 。i tc a u s e st h ep r o b l e mo fu s e r s b e h a v i o rd a t a b a s eo v e r l o a di nt h a t u s e r ss h o u l df r e q u e n t l yc o m m u n i c a t ew i t ht h ed a t a b a s eo nt h es e r v e rs i d e b a s e do nw h a th a sb e e nd i s c u s s e da b o v e ，t h i st h e s i sp r o v i d e dan e ws t y l e s e a r c hs t r u c t u r e ，al i g h t w e i g h tp e r s o n a l i z e ds e a r c he n g i n e ，t oa c h i e v et h ea i mo f r e d u c i n gt h es e r v e r s l o a d t h i sk i n do fs e a r c hs t r u c t u r ec a l la l s os o l v et h e p r o b l e mo ft h es o r te r r o rc a u s e db yc l i e n t s o r t e du s e r s i n t e r e s t s t h i sl d n do f s t r u c t u r ec o m b i n e st h ec l i e n ts t o r a g er e s o u r c e sa n ds e r v e r - s i d eu s e r s i n t e r e s t s d a t a b a s e ，a n dt h ec l i e n t s i d ea g e n tt e c h n o l o g yi si n t r o d u c e dt os o l v et h ep r o b l e m o ft h es e r v e r s o v e r l o a d i na d d i t i o n ，t h el o o s e c o u p l e dc o n n e c t i o no ft h ec l i e n t t h e c l i e n t - a g e n ta n dt h es e r v e rc a l li m p r o v et h ea g i l i t yo fp e r s o n a l i z e ds e a r c h e n g i n e t h i s t h e s i s e m p h a s i z e s t h ec o m m u n i c a t i o nr u l eo ft h ec l i e n t ，t h e c l i e n t - a g e n ta n dt h es e r v e ra n dt h ei s s u eo fh o wt or e d u c et h ec o m m u n i c a t i o n t r a 伍ca m o n gt h e mi sd i s c u s s e di nd e t a i l t h et h e s i sg i v e st h eu s e r s i n t e r e s t s m o d e lu p d a t i n ga l g o r i t h mo nt h ec l i e n t ，t h ec l i e n t a g e n ta n dt h es e r v e r f i n a l l y , a l l e x p e r i m e n ti su s e d t op r o v et h e f e a s i b i l i t yo ft h el i g h t w e i g h tp e r s o n a l i z e ds e a r c h e n g i n e t h r o u g ht h ec o m p a r a t i v ea n a l y s i sb e t w e e nt h el i g h t w e i g h tp e r s o n a l i z e d s e a r c he n g i n ea n dt h et r a d i t i o n a ls e a r c he n g i n e ，t h i sk i n do fs e a r c hs t r u c t u r ec a n r e a l l yh e l pi m p r o v et h es e r v e r sp e r f o r m a n c et oa c e r t a i ne x t e n t k e y w o r d s ：s e a r c he n g i n e ；p e r s o n a l i z a t i o n ；u s e rm o d e l ；a g e n t 哈尔滨工程大学 学位论文原创性2 声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体己 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均己在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 哈尔滨t 程大学硕十学f 节论文 第1 章绪论 1 1 课题研究的目的和意义 如今的因特网对多数人已不再陌生，网络搜索引擎成了人们获取信息的 一个重要途径，人们在希望搜索引擎能够提供全面的信息资源的同时，也对 搜索引擎的服务提出了更高的要求，这是搜索引擎设计的一种挑战，也是未 来搜索引擎的发展趋势。 纵观目前因特网上流行的搜索引擎，普遍是基于关键字的查询，用户的 每次搜索都是相互独立的，不能根据用户的兴趣给出适应用户需求的查询结 果。而如今社会分工的细化与个人兴趣的不同，决定了不同领域的用户，不 用社会群体对信息需求的不同。于是现在的搜索引擎应该能够根据用户的不 同需求来对查询结果进行排序，也就是针对不同用户的个性化定制，使搜索 结果根据用户需求收敛，使搜索引擎趋向于反映用户的偏好。 为了适应这种需求，人们提出了个性化的搜索引擎n ，的设计思想，通过增 加用户行为数据库来跟踪用户的兴趣或需求。但是，这需要在服务器端建立 庞大的用户信息库与用户行为库，用户每次访问都需要频繁地与数据库服务 器通信，在如今面向因特网的搜索来说，这种开销限制了这种方法的可行性， 此外通过用户登录搜索的方式，对于公共搜索引擎的用户来说，也不是一种 方便的信息查询方式。但是完全将用户行为存储在客户端又会因为客户端存 储有限，无法真正反映用户兴趣，造成搜索结果的片面。 基于此，本课题的研究着重于一种轻量级的个性化搜索引擎的设计思想 与实现方法。所谓轻量级是指在搜索引擎的客户端存储部分用户兴趣记录， 同时结合服务器端的用户兴趣库，客户端与服务器端按需交换信息，减轻服 务器负载，充分利用客户端的资源来实现个性化的搜索。通过客户端的存储 与服务器端的用户行为跟踪引擎的结合，本文给出了针对用户不同需求，符 合用户兴趣的个性化搜索引擎的解决方案。 哈尔滨f ：程人学硕十学位论文 1 2 国内外研究现状 目前对个性化搜索的研究的技术主要是信息检索技术、推荐技术、用户 聚类与用户建模技术等。随着因特网的发展，人们在对个性化信息服务的研 究过程中逐渐意识到，个性化服务的质量不仅仅取决于具体的检索技术或是 推荐技术，大部分还取决于对用户兴趣记录和使用偏好的挖掘。而对这些信 息的可计算描述在如今追求个性化服务的网络中显示尤为重要。 近年来在个性化搜索的研究中，对用户模型的研究显得比较突出。用户 建模技术已经开始从具体的个性化服务形式中脱离出来，作为个性化信息服 务中的基础技术来研究。 国外学者对于个性化信息检索的用户模型研究的主要成果有： l i e b e r m a n 提出了信息代理l e t i z i a t ”，l e t i z i a 可准确地监控用户浏览行为自 动形成一个用户模型。它用于在用户浏览时向用户建议其可能感兴趣的链接， 这些链接与用户当前访问的页而内容相关。系统不要求用户进行显示的评价， 主要是通过分析用户的浏览行为确定用户的兴趣爱好。 c h a n 提出w e b m a t e ，它是帮助用户有效浏览和搜索w e b 的代理，w e b m a t e 通过多维加权变量记录用户在不同领域的兴趣。 m e t a c r a w l e r 系统“1 是w a s h i n g t o n 大学开发的基于i n t e r n e t 中八个搜索引擎 的元搜索引擎系统。它提供了统一的接口，用户将查询请求提交给 m e t a c r a w l e r ，已在通过成员调度策略转给其他各个搜索引擎，最后把结果以 统一的形式返回给用户。通过在实际的信息和用户之间生成统一的用户过滤 处理层，提高了系统的灵活性。 p e r s o n a lw e bw a t c h e r 晦l 同样提供个性化服务，通过适应用户的变化要求从 而更新了用户的偏好。通过学习用户认为感兴趣的链接得到链接，如果系统 认为某些链接是用户感兴趣的，则加亮显示他们，但不足之处在于系统地建 议被限制在一个页面存在的链接上。 a m a l t h a e a 系统l s 一是一个信息发现的个性化系统，能根据用户的兴趣从分 布的结点上发现有用的信息，进行筛选以摘要的形式提交给用户。在运行过 程中，如果用户的兴趣发生改变，根据用户的反馈来修改用户模型。 哈尔滨i ：样人学硕十学位论文 i l l 近几年来，国内对个性化信息检索用户模型也进行了研究，具体集中在 用户模型的表示方法、用户建模方法、用户建模技术、用户模型优化等问题 的研究。 国内主要代表性的研究有一南京大学研究的d o u r i a g e n t ，。南京大学 多媒体技术研究所经三年努力，推出了一种个性化信息搜索引擎 d o l t r i a g e n t 。该系统将主体技术应用于网络信息搜索，其主要的特征是具 有一定学习功能，能够在信息交互中获取用户的信息，包括用户的兴趣、爱 好和思维方式，在此前提下，系统可以主动、定期为用户查找信息，根据用 户搜索信息的变化调整“知识库 中的通用字和关键字，使之能够有效地适 应专门领域的信息管理。系统的本地信息库还可以对搜索到的信息进行分类 存储和管理，同时具有与其它系统的协作功能。 国内相关研究还有n t ：复旦大学吴立德教授和黄首普博士等人参加的 t r e c 9 会议信息过滤f i l t e r i n g 子项目，取得了较好的效果。东北大学的姚天 顺教授和林鸿飞博士等人在他们提出的过滤模型中，用户需求采用基于实例 文本的主题词表示。中国科学院软件研究所的阮彤、冯东雷等博士在其信息 过滤研究中，提出了基于贝叶斯网络的信息过滤模型b m i f ，描述了信息过滤 系统的基本结构。研究发现，虽然国外在信息过滤领域的研究比较领先，但 是系统的服务质量不高，并且目前尚不能处理中文文献。国内该领域的研究 虽然也有很大进展，但是信息过滤的技术难度大，特别是中文信息处理的特 殊性，更增加了关键技术研究的难度。 1 3 论文的主要内容及结构 在上述研究背景下，本文的研究工作主要是研究同时利用客户端与服务 器端资源，引进客户端代理，减少传统个性化搜索引擎服务器端开销，以实 现一种轻量级的个性化搜索引擎。 本文首先介绍论文研究背景。接着将现有搜索引擎技术进行综述，结合 文献资料对国内外研究现状进行分析。之后对实现个性化搜索引擎所需要的 技术作一个简单的介绍。着重讨论本文提出的提供个性化信息检索服务的新 模式轻量级个性化搜索引擎的设计。最后以实验系统的结果分析来结束 1 哈尔滨f 程人学硕七学位论文 本文。 本文分为五部分，其组织结构如下： 第1 章对课题背景、论文研究内容、论文结构和组织进行介绍。 第2 章介绍文中所涉及的基础理论知识，包括搜索引擎结构、分类以及 工作机制。 第3 章介绍个性化搜索引擎用户模型。包括个性化搜索引擎用户模型的 表示及建立方法。 第4 章详细介绍本文提出的个性化搜索引擎的设计。 第5 章对本文研究的搜索引擎给出实现的代码与结果。 最后，对本文进行了总结，并提出了进一步的研究工作。 4 哈尔滨。i ：程人学硕十学何论文 第2 章搜索引擎技术综述 2 1 搜索引擎概述 搜索引擎( s e a r c he n g i n e ) 是指能够自动对万维网中的资源进行分析处 理，响应用户查询返回匹配结果的系统。现在流行的搜索引擎一般以w e b 站 点的形式存在，它的主要任务是在互联网上主动抓取因特网上的各种信息， 如h t m l 网页，w o r d 文档，p d f 文件等，并将这些文件建立索引。这些索 引将以一定格式存储在文件系统中，为了提高查询速度，一般这些信息分布 式存储在不同服务器中。当用户输入关键字( k e y w o r d ) 查询时，搜索引擎 对该关键字进行分析( a n a l y z e ) ，之后据此在索引中查找相关信息，若在索 引中有匹配的信息，则将信息反馈给用户；若没有则通过一定方式如使用用 户输入纠错提醒或相似关键字提示，在一定时间内向用户返回查询结果。 对于各种搜索引擎，它们一般包括信息获取程序、文件索引程序和查询 接口三部分，。信息获取程序根据给定的网址获取h t m l 网页，同时获取该 页面上的网址，以广度或深度优先方式访问这些页面，将每个页面中的信息 分析后建立索引，存储至服务器上。查询接口通过索引为用户的查询请求提 供服务。 2 2 搜索引擎分类 目前的搜索引擎主要有以下几种类型”，： 1 基于客户的搜索引擎 基于客户的搜索引擎用w e b 客户机中的周游软件。它们从一组已知的 文档出发，检索w w w 上的文档并传送这些文档。然后用文档中的超文本链 接找到更多的文档，直到满足要求。基于客户的搜索引擎不需要第三方检索 接口，因此可改善用户界面。因为基于客户的搜索是实时的，它可以搜索到 5 哈尔滨：程人学硕士学位论文 i i 最新的资料，但搜索速度慢，网络负载和服务器负载都太大。 2 基于目录的搜索引擎 基于目录的搜索引擎将收集到的信息分类到某一个类中。典型的基于目 录的搜索引擎有y a h o o 。但这类搜索引擎有两大问题：( 1 ) 分类是按分类者 或分类软件的分析而定，不一定与用户的意见一致；( 2 ) 如果查找的信息没 有对应的分类项，则无法进行搜索。 3 基于机器人的搜索引擎 基于机器人的搜索引擎从一组已知的文档出发，通过这些文档的超文本 链接确定新的检索点，然后用索引机器人周游这些新的检索点，标志这些检 索点上的新文档，将这些新文档加入到索引数据库。以后搜索引擎可以用这 个索引数据库去回答用户的提问。搜索方法有深度优先和广度优先两种。广 度优先算法先标引新服务器上的新文档，然后标引己知服务器上的新文档。 即找到尽量多的服务器。它保证一个服务器上至少有一篇文档加入索引数据 库。它能降低同一服务器被访问的频率，缺点是不能深入文档。深度优先的 算法能较好地发掘文档结构，如相互参照的链接结构，而且相对比较稳定， 缺点是有可能进入无限循环。数据检索方法有基于全文和基于标题两类。基 于机器人的搜索引擎常被批评为不安全及产生大的网络负载和服务器负载。 常用的基于机器人的搜索引擎有a l t a v i s t a 等。 4 多元搜索引擎 多元搜索引擎将用户查找要求递交给其他搜索引擎。他的注意力放在改 进用户界面和用不同的方法过滤从其他搜索引擎接收到的相关文档，包括消 除重复信息。多元搜索引擎设计简单，但网络的负载太大。典型的多元搜索 引擎有m e t a c r a w l e r 等。 2 3 搜索引擎结构 整个搜索结构由“信息抓取模块”，“信息检索模块 和“用户个性分析 模块三部分。其中“信息抓取模块”由“抓取程序”和“索引程序”组成； “信息检索模块 与“用户个性分析模块”结合提供个性化检索服务。整体 结构图如图2 1 所示，可以看出虚线左侧负责搜索引擎数据的抓取，虚线右 6 哈尔滨j i ：程火学硕十学位论文 侧负责搜索引擎的搜索。 图2 1 系统结构图 ( 1 ) 信息抓取模块从w e b 库( 配置了需要抓取的u r l ) 中获取抓取列 表，提交给抓取程序，通过抓取程序抓取因特网信息资源提交给索引程序， 同时根据需要更新w e b 库内容。 ( 2 ) 信息检索模块是用户与搜索引擎的个接口，它可以获取用户的查 询请求，提取用户客户端的兴趣记录，同时可以把查询结果返回给用户。信 息检索模块将用户兴趣记录与查询关键字同时提交给用户个性分析模块；用 户个性分析模块生成用户特征向量提交给索引器；索引器查询分析器根据索 引库中的信息与用户特征向量结合得到查询结果；最后通过信息检索模块( 搜 索接口) 返回给用户。 2 4 搜索引擎工作机制 从搜索引擎的定义来看，一般搜索引擎主要由网络蜘蛛、索引与检索三 大模块构成。 网络蜘蛛1 是一个可以浏览网页的程序，它会定期地自动地在网上漫游， 首先打开一个网页，然后再通过网页上的链接去浏览其他不同的网页，如此 7 哈尔滨i ：程人学硕十学位论文 往复。对于一些新出现的网站或在自动搜索中有所遗漏的站点，用户也可以 自行向搜索引擎提交网站地址，使得站点内容能被及时得以搜索。在决定访 问链接顺序的过程中，最常见算法有：深度优先、广度优先、有限深度广度 策略。 索引：网络蜘蛛将遍历得到的页面和地址存放在网页数据库中。为了提 高检索的效率，需要建立索引。索引模块总的来说是通过分析获取的网页， 首先排除h t m l 等语言的标志符号，将出现的字或词全部提取出来，然后记 录每个字词的出现u r l 及相应的位置，最后将结果存入索引数据库。索引数 据库实际上就是一个很大的查询表，上面记录着某个特定字词在互联网上出 现的一级位置信息。 对于英文搜索引擎，由于是以单词为语言的基本单位，因此一般建立索 引采用的都是词表法，即首先建立一个词表，然后将对应单词的出现位置记 录下来，而检索的时候就是以这些词语作为检索入口，并通过位置匹配可以 实现多个词语的组合检索。但对于中文搜索引擎nz ，来说，由于语言的基本单 位是汉字，在最底层往往采用的是字表法。和词表法相似，先建立一个汉字 字表，然后对于网页中出现的汉字均记录在相应的字表项内，当检索的时候， 采取字索引之间的位置匹配完成词语的检索，为了提高检索速度，一般还会 在字索引的基础上建立一些词索引，有的是根据用户的提问动态生成已检索 词的词索引，有的则是建立一个常用词表，然后生成这些词的索引。另外， 无论是中文系统还是英文系统都还会建立一个停用词表，以提高检索效率。 检索：该软件用来筛选索引中无数的网页信息，挑出符合查询要求的网 页并将它们分级排序，与查询关键字关联越大的排得越前，然后将分级排序 后的结果显示给查询用户。具体来说，当用户进行检索的时候，一般使用的 是纯自然语言词汇或者是自然语言词汇组成的布尔逻辑式。对于前者，可以 直接利用检索算法查询索引数据库中的词索引，或者是利用单字索引进行位 置匹配，以获得检索结果。而对于后者，则首先要分析检索式的逻辑关系， 分别对检索式中的各个检索词进行检索，最后再通过逻辑运算获得最终结果。 由于网络上信息数量非常庞大，可能会产生一个相当大的结果集，那么如何 精简结果以及如何将最重要的结果首先返回用户就显得十分重要。最常用的 方法是将结果按相关度进行排序，把引擎认为最相关的结果放在最前面。相 8 哈尔滨l ：程入学硕十学位论文 关度计算有很多的算法，其中一个很重要的算法就是词频法，即通过计算网 页中的检索词的出现频率来决定该网页的相关程度，检索词出现次数越多则 说明该网页越重要，虽然这种算法有很多缺陷，往往不能达到最好的效果， 但由于计算网页中一个词的词频十分简单，使得该算法很容易实现。 2 5 个性化搜索引擎 随着w w w 的迅速发展和普及，搜索引擎已经成为目前互联网上第二位 应用最广的服务。但是，一般的搜索引擎存在着很大的不足，它们不考虑用 户信息偏好和用户的不同，对所有用户提供一样的界面和服务，检索出成千 上万、良荞不齐的结果，使用户在寻找有用信息时如大海捞针。同时，用户 要获取最新的信息，只能重复同样的查询命令，浪费了用户大量的时间。当 前，搜索引擎正经历着从“数量累积阶段 向“质量精炼阶段 的变革，我 们急需创新搜索引擎观念和技术，创建更为有效的搜索引擎系统，从根本上 解决这些问题。有效的信息检索系统应该能够充分表达用户需求，在检索过 程中可以提供针对用户的友好界面和帮助信息，根据用户对获取信息的处理 情况动态调整其知识库，实现用户需求驱动检索，并且即时将系统中对用户 有用的信息推送给用户。 下一代更为有效的搜索引擎，首先就要具备个性化功能，即“搜索引擎 的个性化“，。它应该能够根据用户背景、兴趣爱好、行为、检索目的、任 务等，提供给每个用户一个他自己的信息查询环境，这包括用户有自己喜欢 的检索界面，使用自己熟悉的检索方法和词语充分表达信息需求，在检索过 程中提供针对用户的帮助信息，检索出适量的、高质量的、比较令人满意的 查询结果；可以将用户的过往行为模式记录下来，作为此用户下一次搜索的 参考。如此一来，在搜索引擎“学习 到用户的行为模式后，理论上会越来 越符合使用者的需求。 个性化搜索引擎最大的用处就在于针对不同兴趣爱好、不同职业、不同 学科领域的各种类型用户提供相应的需求信息，通过用户使用信息的过程和 行为与用户进行交互追捕了解用户的真实意图。 9 哈尔滨下稃大学硕+ 学位论文 2 6 搜索引擎中文分词 英文中，表达信息的单词之间用空格划分，所以英文搜索引擎只需要将 文档中的文本按空格划分了各个独立的单元作为索引的关键字。而汉语中， 没有像英文中的空格那样对文档进行关键字的提取，所以中文关键字的提取 要比英文复杂得多，对中文文档中关键字的提取叫做中文分词。现今搜索引 擎技术已非常流行，随之出现的便是对非西欧文字的分析，其中中文分词技 术n 2 一正是一种目前普遍研究的课题。 比如，英文中一个句子，“ig r a d u a t e df r o mh a r b i n e n g i n e e r i n g u n i v e r s i t y ”，这个句子在英文分析之后可以很容易的知道u n i v e r s i t y 是其中一 个关键字。而表达同样一个意思的汉语句子“我毕业于哈尔滨工程大学”又 如何让计算机程序知道大学是其中一个关键字呢? 这些中文字之间没有没有 表达各不同意群的分隔标志。中文分词需要解决的是诸如如何将“我毕业于 哈尔滨工程大学 的句子切分成有中文中有意义的词的问题。 将中文句子切分成各个关键字的程序称为分词算法。现在流行的分词算 法有以下三类“2 一：机械分词算法、基于理解的分词算法和基于统计的分词算 法。 1 机械分词算法 机械分词方法按照一定的算法将待分析的中文句子与中文词库( 中文词 库是一个包括各种常用汉字词组的机器词典，其表现形式可是文本文档或是 数据库) 中的词条进行匹配，若在词库中找到某个字符串，则匹配成功。所 以，机械分词方法也称叫做基于字符串匹配的分词算法。按照匹配时扫描的 方向不同，机械分词算法可以分为正向匹配分词算法与逆向匹配分词算法； 按照不同长度优先匹配的情况，可以最长匹配分词算法与最短匹配分词算法； 按照是否与词性标注过程相结合，又可以分为单纯分词算法与分词标注相结 合的一体化方法。 以上介绍的常用机械分词算法如下： ( 1 ) 最长匹配分词算法 最长匹配算法是目前使用最为广泛的分词算法，最长匹配算法按照匹配 1 0 哈尔滨丁程人学硕士学位论文 时扫黄的方向分为正向最长匹配分词算法与逆向最长匹配分词算法。正向最 长匹配分词算法中对句子中短语扫描的顺序为从左到右，逆向最长匹配分词 算法中对句子中短语扫描的顺序为从右到左。 正向最长匹配分词算法可以表示为： 获取词库中最长词条的长度m 和最短词条长度m 。 从被处理文本中的起点取出小于等于m 个汉字的字符串作为待匹配 串。 在词库中查找待匹配串，若匹配成功，则得到一个成功匹配串( 设串 长度为n ) ，将被处理文件后移1 1 个汉字长度作为下一次分词扫描的起点，转 步骤。 如果在词库中未找到待匹配串，则去除匹配字段的最后一个字符，作 为新待匹配串，若待匹配串长度 = m ，则转步骤；若待匹配串长度= m 1 ， 则将该待匹配串作为未登录词处理，后移m 1 个字符作为下一次分词扫描的 起点，转步骤。 逆向最长匹配分词算法可以表示为： 获取词库中最长词条的长度m 和最短词条长度m 。 从被处理文本中的起点取出小于等于m 个汉字的字符串作为待匹配 串。 在词库中查找待匹配串，若匹配成功，则得到一个成功匹配串( 设串 长度为n ) ，将被处理文件前移n 个汉字长度作为下一次分词扫描的起点，转 步骤。 如果在词库中未找到待匹配串，则去除匹配字段的最前一个字符，作 为新待匹配串，若待匹配串长度 = m ，则转步骤；若待匹配串长度= m 1 ， 则将该待匹配串作为未登录词处理，前移m 1 个字符作为下一次分词扫描的 起点，转步骤。 ( 2 ) 最少切分算法 最少切分算法使每一句中切出的词条数最小。这需要将正向最大匹配算 法与逆向最大匹配算法结合起来一起使用，从而构成双向匹配算法。由于汉 语成词固有的特点，正向最小匹配方法与逆向最小匹配方法一般很少使用。 经统计表明，单纯使用正向最大匹配分词算法分词的正确率为9 9 4 1 ，单纯 1 1 哈尔滨t 程大学硕十学位论文 使用逆向最大匹配分词算法分词的错误j 下确率为9 9 5 9 ，由此可见，逆向匹 配分词算法分词的精度略高于正向匹配分词算法。 其实，最算是9 9 5 9 正确率的分词算法还远远不能满足搜索引擎的实际 需要。目前流行搜索引擎使用的分词系统，一般是将机械分词算法作为一种 初分手段，还需要利用各种其他的语言信息来进一步提高分词的精度，除此 之外有些商业搜索引擎将分词技术作为一项商业机密不对外界公开。 一种改进的方法是改变分词时的扫描方式，称为特征扫描或标志切分。 这种算法优先在待匹配串中识别出和切分出一些带有明显特征的词条，这些 词条通常是一些流行的短语或是人名地名，然后以这些词条为分隔点，将待 匹配串分为较小的子串来进行机械分词，从而减少匹配的错误率。另一种方 法是将分词和词类标注结合起来，利用丰富的词类信息对分词决策提供支持， 并且在此过程中反过来对分词结果进行检验、调整，从而在很大程度上提高 分词的正确率。 2 基于理解的分词算法 ， 这种分词算法是通过让计算机程序模拟人类对汉语句子的理解，以达到 识别词条的目的。但是这种方法需要计算机具有大量的词法、句法和语义知 识。基于理解的分词算法基本原理是在分词的同时进行句法、词法和语义分 析，利用这些信息来处理识别过程中的岐义现象。基于理解的分词算法的分 词系统通常包括总按系统、分词子系统和句法语义子系统三个部分。在总控 系统的协调下，分词子系统可以获取有关词、句子等的句法和语义信息来对 分词过程的歧义进行判断。这一过程模拟了人类对句子的理解过程，可见这 种分词方法需要使用大量的语言知识和语义信息。由于汉语语言知识的复杂 性，计算机程序很难将各种语言信息组织成计算机可以直接读取的形式，这 过程中需要一定的人工智能才能完成，因此目前基于理解的分词系统还处在 试验阶段。 3 基于统计的分词算法 从形式上看，词是汉语中稳定的字的组合。因此，在汉语中，文档上下 文里相邻的字同时出现的次数越多，这两个相邻的字就越有可能构成一个词。 所以，字与字相邻共现的频率或概率可以体现出构条一个词的可信度。 基于统计的分词算法对文档中相邻共现的各个字的组合的频度进行统 1 2 哈尔滨1 ：稃人学硕十学位论文 i i 计，计算它们的相邻共现频率。定义两个字的相邻，计算两个汉字a 、b 的 相邻共现概率。相邻共现频率体现了汉字之间结合关系的紧密程度。当紧密 程度高于某一个阈值时，便可认为这些字的组合可能构成了一个词。这种方 法只需对文档中的相邻共现的字进行统计，不需要中文词库，因而又叫做无 词库分词法或统计取词方法。但这种方法也有一定的局限性，单纯利用该算 法分词会经常切分出一些共现频度高、但并不是词的常用词条，例如“那个”、 “我和 、“你的”、“这一”等。同时单纯利用该算法分词对常用词识别的正 确率并不理想，由于需要记录整个文档所有相邻字出现的频率，分词时需要 的时间与空间开销都很大。实际应用的统计分词系统都要使用一部基本的分 词词库( 常用词词库) 进行机械分词，同时使用统计方法识别一些新的词， 即将基于字符串匹配的分词算法和基于统计的分词算法结合起来，既发挥机 械分词切分速度快、效率高的特点，又利用了无词库分词结合上下文识别生 词、自动消除歧义的优点。 对于以上介绍的各种分词算法的优劣目前并无定论。目前商业搜索引擎 中的分词系统不可能单独采用某一个分词算法来实现。为了达到较好的分词 效果，一般都需要综合不同的分词算法，取长补短，尽可能地降低分词错误 率，以提高分词的精度。 2 7 本章小结 本章主要是对当前搜索引擎技术的综述，描述了现今搜索引擎一些研究 的内容、搜索引擎的分类、搜索引擎的结构和工作机制，之后对本文涉及的 搜索引擎中的一项内容即个性化搜索作一个简单的介绍，最后介绍了中文搜 索引擎必不可少的中文分词问题。 哈尔滨一f ：稗人学硕十学位论文 第3 章个性化搜索引擎用户模型 3 1 用户模型概述 用户模型【- 3 ，是针对用户的个人兴趣建立的模型，也称为“个性化模型 和“用户兴趣模型”。用户模型常被理解为对用户在某段时间内相对稳定的信 息需求的描述。 用户模型不仅仅是对用户兴趣的准确描述，作为以计算机平台为依托的 个性化服务系统，可计算性是其对用户模型的基本要求。也就是说，个性化 服务系统中的用户模型不是对用户个体的一般性描述，而是一种面向算法的， 具有特定数据结构的形式化的用户描述。相应的，用户建模是指从有关用户 兴趣和行为的信息如背景知识、浏览内容，浏览行为等等中归纳出可计算的 用户模型的过程。 作为个性化信息服务的基础与核心，用户模型的质量直接关系到个性化 信息服务的质量。个性化信息服务的形式多种多样，包括个性化推荐服务“”、 个性化检索服务等。但无论何种形式，都需要首先建立对用户的描述，然后 才能据此提供针对不同用户的个性化信息服务。 用户模型的应用领域是广泛的，在搜索引擎中引入用户模型，有利于实 现自适应的检索，即提供个性化、智能化的检索服务。通过对用户历史检索 行为的记录和学习，使对用户的检索提问的分析更为准确，实质上就是提高 检出的结果与用户需求之间的相关性，通过提高用户相关度来提高用户的满 意度。同时用户模型也有助于预期定位用户的需求，进行主动服务。 用户模型从不同角度可以有多种分类方式“3 ，：( 1 ) 按照建模的对象划分， 可以分为组用户模型和单个用户模型：( 2 ) 按照信息源划分，可以分为显式 模型和隐式模型；( 3 ) 按照时间尺度划分，可以分为长期模型和短期模型； ( 4 ) 按照更新方式划分，可以分为静态模型和动态模型；( 5 ) 按照表现形式 划分，可以分为基于属性的模型和基于知识的模型等。 1 4 哈尔滨+ t ：稗人学硕十学位论文 3 2 用户模型信息的获取 通常，用户模型信息的获取方法“引可以划分为两种。一种是显式的，另 一种是隐式的非入侵的。显式方法主要是通过直接询问用户有关的兴趣和偏 好或允许用户自己定义和修改用户模型来实现，而隐式方法则是通过跟踪用 户的行为和交互来评估和推测用户模型。前者透明度高，获取信息直接，花 费时间相对较少，可靠性较高，但过多的询问会占用用户大量的浏览时间， 有时甚至会令用户厌烦，灵活性也比较差。后者获取信息比较隐蔽，往往是 在用户的不知不觉中，但由于透明度不高，所获取的信息有时会有比较大的 偏差，基于此建立的用户模型经常无法完全让用户满意。因此在个性化服务 用户建模中，最常用的方式是将两种方法结合起来，通过显式方式来获取静 态用户信息，通过隐式方式来获取动态用户信息。具体来说，用户建模的信 息来源主要有“引： ( 1 ) 用户输入搜索引擎的查询关键词。 ( 2 ) 用户浏览的页面。 ( 3 ) 用户浏览的行为包括用户在每个页面上驻留的时间，对每个页面进 行的操作，鼠标和键盘的操作。 ( 4 ) 服务器同志可以分为代理服务器日志和网站服务器日志。用户对网 站的访问会被服务器记录下来，包括用户的、访问时间、用户所在的时区、 访问页面的大小等信息。代理服务器r 志记录用户对所有网站的访问，网站 服务器日志只记录用户对本网站的访问。 ( 5 ) 用户下载保存的页面和资料等。 ( 6 ) 用户手工输入的其他信息。 在以上多种信息来源中，用户浏览页面和浏览行为最能全面地反映用户 兴趣；服务器日志也能较好地体现用户的兴趣用户b o o k m a r k 的和保存整理 的文档虽然不一定能全面地反映用户的兴趣，但能很好地反映用户很关注的 信息。用户输入搜索引擎的查询关键词不应单独用于用户建模。 1 5 哈尔滨t 样人学硕十学位论文 3 3 用户模型的表示 根据获取方法和应用理论的不同，用户模型的表示方法“叫可以分为主题 表示方法、收藏夹表示法、关键词列表法、矢量空间模型表示法、兴趣度表 示法、概念模型表示法等。 1 主题表示法 主题表示法是指以用户感兴趣的信息主题来刻画用户的兴趣特征。例如 用户对科技和体育类信息感兴趣，则用户描述文件表示为科技，体育，这种 表示方法往往与具体的应用领域相结合。个人网页服务的用户描述文件就是 利用用户选择的网站栏目来表示的，当用户定制了“科技和“体育”栏目， 就将这一定制记录下来作为用户描述文件，用户再次登录时，则根据保存的 用户描述文件显示用户定制的信息。 2 收藏夹表示法 用户在浏览信息的过程中常会把感兴趣的重要站点或页面添；o h - n 收藏夹 中，即将相应的网页保存在收藏夹中以方便以后浏览，因此用户的收藏夹可 用来反映用户感兴趣的主题。 3 关键词列表法 关键词列表法是指以用户感兴趣信息的关键词来刻画用户的兴趣特征。 如用户对足球赛感兴趣，则用户描述文件可以表示为英超，意甲，西甲，罗 纳尔多，贝克汗姆，菲戈等。关键词可以由用户指定，也可以通过学习算法 得到。通过学习算法得到的关键词在本质上与文本分类中的特征选择问题相 似，都是通过训练样本得到一个较小的特征集合。采用关键词列表法的个性 化服务系统要求用户输入自己感兴趣的关键词，以便在用户浏览的过程中向 用户推荐页面。 4 向量空间模型表示法 向量空间模型表示法是指用关键词矢量空间中的矢量来表示用户的兴趣 特征。向量空间模型表示法的基础是向量空间模型。向量空间模型( v e c t o r s p a c em o d e l ，简称v s m ) 是表示文档的常用方法，在这种方法中，用户的个 性化模型用两个向量表示，一个是用户感兴趣的词条构成的向量丁( f ，f 2 j 。) ， 1 6 骱尔溟：i ：群人学硕十学位论文 另一个是由用户对对应词条的兴趣度构成的向量肜( w 。，w 2 w n0 每个文档表 示为( o 。，w 。f ：，w ：1 t 。，w n ) ) ，其中f ，为第i 个单字。m 为单字在文档中的权 重。 t l , t ：。t 。可以是文档中出现的全部单字，也可以是选择出来表示用户兴趣 的关键词。采用所有单字及其权重作为用户描述文件的方法一般对应于直接 用整篇文档描述用户兴趣。由于大量的用户感兴趣文档中的单字对表现用户 兴趣主题没有直接益处，而且随着用户感兴趣文档的增加，用户描述文件会 不断增大，这种用户描述文件需要大量的物理空间和计算丌销。相比而言， 采用选择出来的关键词及权重构成用户描述文件具有更好的性能，但关键词 的选择是其中的关键。 当需要对未知文档和用户兴趣模式进行比较时，就通过计算文档的特征 向量y 。，v ：。虬) 和用户兴趣度向量( m ，w 2 w n ) 之间的夹角0 来度量，夹角 0 越小，则说明文档和用户兴趣的匹配程度越高。 文档和用户兴趣的匹配度算法如式( 3 1 ) 。 罗w k s i m ( v ，w ) = c o s ( v ，) ；下鱼f ( 3 1 ) 荟y 叫荟以 5 兴趣度表示法 兴趣度表示法根据用户感兴趣信息的粒度又分为粗兴趣粒度和细兴趣粒 度表示法，粗兴趣粒度只区分感兴趣和不感兴趣两类，细兴趣粒度还要进一 步区分用户的兴趣主题。粗、细兴趣粒度表示法常与上述表示法结合起来使 用。由于粗兴趣粒度表示法实现起来较为简单，可以借鉴成熟的机器学习方 法，现有的个性化服务系统大多数采用粗兴趣粒度表示法表达用户描述文件， 但是细兴趣粒度表示法更能细致地刻画用户的兴趣和偏好，也有利用用户描 述文件的维护，能提供更高质量的个性化服务。 6 概念模型表示法 概念模型表示法是根据描述用户兴趣词条之间的语义关系，把用户个性 化模型描述成一种树形结构。这种表示方法的基础是本体论( o n t o l o g y ) m 1 。 本体论是从哲学领域借鉴过来的术语，原意是指一种存在的系统化解释，借 哈尔滨j j i 稃人学硕十学何论文 鉴到知识工程领域之后，本体论是对概念化对象的明确表示和描述。由于本 体论对特定领域对象的表示与描述具有规范性、可重用性、可靠性等特点， 有些研究者将本体论应用于信息检索领域，对文档、用户兴趣进行描述，以 提高系统的联想能力和精确性。 本体论招”作为领域概念化模型，描述了该领域中的术语、术语的含义以及 各个术语之间的语义网络等基本信息。这种形式的用户个性化模式通过依托