（计算机应用技术专业论文）搜索引擎排序算法研究.pdf

摘要 摘要 搜索引擎是现在最常使用的互联网应用之_ ，随着科技的发展，原先决定 搜索引擎命运的网页覆盖率问题已经逐步得到解决。如何在这么大的资源库中， 快速找到并且返回用户真正需要的信息已经成为搜索引擎研究重点。一个好的 排序算法可以在为搜索引擎公司带来丰厚利润的同时，大大节约用户查找信息 的时间。 本文在充分研究搜索引擎排序算法的基础上，提出了一种利用浅层语法分 析和用户兴趣分类对搜索引擎的排序进行改进的方法。在用户提交查询以后， 系统首先利用条件随机场模型对用户的问句进行浅层语法分析，得到各个关键 字在问句中的角色，从而重新分配关键字之间的权重。同时，记录用户的浏览 信息，分析出用户的长期兴趣，短期兴趣和时段兴趣，影响网页的排序结果。 实验证明，上述方法可以有效的改善搜索引擎排序策略。 关键词：排序算法；浅层语法分析；条件随机场；兴趣分类 a b s t r a c t s e a r c he n g i n ei so n eo ft h em o s tf i e q u e n t l yu s e da p p l i c a t i o n so nt h ei n t e r n e t w i t ht h ed e v e l o p m e n to ft e c h n o l o g y , t h ec o v e r a g eo fs i t e s ，w h i c hu s e dt ob et h ek e y i s s u eo ft h es e a r c he n g i n e ，h a sb e e ns o l v e dt a r d i l y t h ep r o b l e m ，h o wt of i n dt h em o s t p r o p e ri n f o r m a t i o ni ns u c hah u g ed a t a b a s e ，b e c a m et h em o s ti m p o r t a n to n e a n e x c e l l e n tr a n k i n gs y s t e mc , a nn o to n l yb r i n gt h es ec o m p a n yh u g ep r o f i t ，b u ta l s o s a v et h et i m eo ft h el 1 s e t s an e wa p p r o a c h , u s i n gl o w l e v e l g r a m m a ra n a l y s i s a n du s e ri n t e r e s t c l a s s i f i c a t i o n , i sp r o p o s e dt oi m p r o v et h er a n k i n gs y s t e m c o n d i t i o n a lr a n d o mf i e l d s ( e r r ) i su s e d t og r a l i l i n a ra n a l y z ea f t e rq u e s t i o n sa r es u b m i t t e d w e i g h t sa r e r e a l l o c a t e db e t w e e nt h ek e y w o r d st ot h er o l e st h e yp l a yi nt h eq u e s t i o n n es y s t e m a l s ot r a c k st h eu s 豇 s a c t i o n s ，a n dt h e i rl o n g - t e r mi n t e r e s t , s h o r t - t e r mi n t e r e s ta n d t i m e di n t e r e s ti sp u l l e do u t t h e yc a na f f e c ts o r t i n gp a g e s e x p e r i m e n t sp r o v et h a tt h o s em e t h o d sc a ni m p r o v et h es e a r c he n g i n er a n k i n g s y s t e me f f e c t i v e l y k e yw o r d s ：r a n k i n gs y s t e m ；l o w l e v e lg r a m m a ra n a l y s i s ；c o n d i t i o n a lr a n d o m f i e l d s ( c r f ) ；u s e ri n t e r e s tc l a s s i f i c a t i o n 学位论文版权使用授权书 本人完全了解北京机械工业学院关于收集、保存、使用学位论文 的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和 电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、 缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以 及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向 国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目 的的前提下，学校可以适当复制论文的部分或全部内容用于学术活 动。 学位论文作者签名：奄胁 加g 年f 月多佃 ( 注：非保密论文无需签字) 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月日年月日 硕士学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：缕狠档签名：李弧私 沙盯年月力ye t 第1 章引言 1 1 选题背景 第1 章引言 随着科技的发展，互联网的时代已经到来，信息技术在发生着巨大的变化。 互联网上的信息每年都以几何级数在增长。2 0 0 7 年7 月1 8 日，中国互联网络信息 中一t = l ： ( c n n i c ) 在京发布第2 0 次中国互联网络发展状况统计报告【1 1 。报告显示， 截止2 0 0 7 年6 月3 0 日，我国网民总人数达到1 6 2 亿，半年来平均每分钟就新增近 1 0 0 个网民，半年的增长接近去年全年的增长量，互联网普及率也达到了1 2 3 。 目前我国上网计算机数达至j j 6 7 1 0 万，比2 0 0 6 年末增长了7 7 0 万台。截至2 0 0 7 年6 月，中国网站数量已经达到1 3 1 万个，半年内增加了4 7 万个，比2 0 0 6 年同期增加 了5 2 万个，年增长率达至1 j 6 6 4 。 如此庞大的一个网络规模，对于我们可以说既是机遇，又是一个巨大的挑 战。不可否认，它是一个非常巨大的知识宝库，它包含着人们需要的各种各样 的知识。但是对于我们来说，如何在这么大的信息库中找到我们需要的信息将 是一个更大的挑战。搜索引擎正式在这样的背景下，应运而生的。通过搜索引 擎，用户可以迅速在网络的信息海洋中定位自己要查找的信息。报告显示， 搜索引擎的网民使用比例已达7 4 8 ，成为仅次于新闻的网络第二大应用。但是， 在与互联网发展成熟的美国( 9 1 ) 相比，搜索引擎还有非常大的发展空间。 1 2 搜索引擎的发展历史 现代意义上的搜索引擎的祖先，是1 9 9 0 年由蒙特利尔大学学生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 t p 主机中，查询起来非常不便， 因此a l a n a r c h i e i 作原理与现在的搜索引擎已经很接近，它依靠脚本程序自动搜 索网上的文件，然后对有关信息进行索引，供使用者以一定的表达式查询。由 于a r c h i e 深受用户欢迎，受其启发，美国内华达s y s t e mc o m p u t i n gs e r v i c e s 大学 于1 9 9 3 年开发了另一个与之非常相似的搜索工具，不过此时的搜索工具除了索 第1 章引言 引文件外，已能检索网页。 l y c o s ( c a m e g i em e l l o nu n i v e r s i t yc e n t e rf o rm a c h i n et r a n s l a t i o na n n o u n c e s l y c o s ) 是搜索引擎史上又一个重要的进步。c a r n e g i em e l l o nu n i v e r s i t y 的m i c h a e l m a u l d i n 将j o h nl e a v i t t 的s p i d e r 程序接入到其索引程序中，创建了l y c o s 。1 9 9 4 年7 月2 0 日，数据量为5 4 ，0 0 0 的l y c o s i e 式发布。除了相关性排序外，l y c o s 还提供了 前缀匹配和字符相近限制，l y c o s 第一个在搜索结果中使用了网页自动摘要，而 最大的优势还是它远胜过其它搜索引擎的数据量。从此搜索引擎进入了高速发 展时期。雅虎，e x c i t e ，i n f o s e e k 等一批真正的商业化的搜索引擎开始投入使用。 搜索引擎的技术也随着商业的驱使不断发展起来，搜索引擎包含的信息量也随 着技术的更新而不断增大。1 9 9 8 年诞生的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 、多文档格式支持、地图股票词典寻人等集成搜索、多语言支 持、用户界面等功能上的革新，再一次永远改变了搜索引擎的定义，成为当今 世界上搜索引擎市场占有率最高的搜索引擎。【2 】 在国内，搜索引擎技术也不断发展。北大天网是国家“九五”重点科技攻 关项目“中文编码和分布式中英文信息发现 的研究成果，由北大计算机系网 络与分布式系统研究室开发，于1 9 9 7 年1 0 月2 9 日正式在c e r n e t 上提供服务。 2 0 0 0 年初成立天网搜索引擎新课题组，由国家9 7 3 重点基础研究发展规划项目基 金资助开发，收录网页约6 0 0 0 万，利用教育网优势，有强大的却搜索功能。 2 0 0 0 年1 月，超链分析专利发明人、前i n f o s e e k 资深工程师李彦宏与好友徐勇 ( 加州伯克利分校博士) 在北京中关村创立了百度( b a i d u ) 公司。2 0 0 1 年8 月发布 b a i d u c o m 搜索引擎b e t a 版，2 0 0 1 年l o 月2 2 日正式发布b a i d u 搜索引擎。b a i d u 虽然 只提供中文搜索，但它拥有最大的中文数据库。b a i d u 搜索引擎的其它特色包括： 网页快照、相关搜索词、错别字纠正提示、新闻搜索、f l a s h 搜索、信息快递搜 索。 2 0 0 7 年中国搜索引擎市场调查报告显示，c n n i c 报告显示，在用户首选 ( 最优先使用) 的搜索引擎中，百度首选市场份额，达到了7 4 5 ，占到了用户 首选搜索引擎市场的7 成以上。谷歌( g o o g l e ) 的首选市场份额是1 4 3 。【3 】 垂直搜索是近几年兴起的一种新的概念。垂直搜索是针对某一个行业的专 业搜索引擎，是搜索引擎的细分和延伸，是对网页库中的某类专门的信息进行 一次整合，定向分字段抽取出需要的数据进行处理后再以某种形式返回给用户。 垂直搜索引擎和普通的网页搜索引擎的最大区别是对网页信息进行了结构化信 息抽取，也就是将网页的非结构化数据抽取成特定的结构化信息数据，好比网 2 第1 章引言 页搜索是以网页为最小单位，基于视觉的网页块分析是以网页块为最小单位， 而垂直搜索是以结构化数据为最小单位。然后将这些数据存储到数据库，进行 进一步的加工处理，如：去重、分类等，最后分词、索引再以搜索的方式满足 用户的需求。整个过程中，数据由非结构化数据抽取成结构化数据，经过深度 加工处理后以非结构化的方式和结构化的方式返回给用户。垂直搜索引擎的应 用方向很多，比如企业库搜索、供求信息搜索引擎、购物搜索、房产搜索、人 才搜索、地图搜索、m p 3 搜索、图片搜索几乎各行各业各类信息都可以进一 步细化成各类的垂直搜索引擎。t r s 的企业搜索引擎和酷讯网等垂直搜索企业正 在崛起。 研究搜索引擎的发展历史我们可以知道，每次搜索引擎的突破性发展往往 是伴随这排序技术的发展而产生的。早期的全文检索技术成全了y a h o o ； p a g e r a n k 技术让g 0 0 酉e 迅速起飞赢得了搜索引擎市场上的第二桶金；超链接分 析技术和竞价排名让b a i d u 迅速占领国内市场。 1 3 课题研究的意义 随着数据的积累，网页的覆盖情况已经逐渐得到解决，搜索引擎的排序技 术逐渐成为人们研究的重点。排序技术对于一个搜索引擎来说，往往起着决定 性的作用。一个好的排序技术往往能够成就一个搜索引擎。但是，现在搜索引 擎采用的这些排序技术还都未能够真正解决网页的排序问题。问题主要出现在 以下两个方面： 1 搜索引擎不能够理解网页的内容，只能根据一定的表面特征( 词频等) 排序 2 搜索引擎所提供的排序千篇一律，不能根据不同用户进行调整 要解决上述两个问题，可以从以下几个方面着手： 1 建立语义网络，让搜索引擎能够真正的读懂网络上的信息 2 对用户提交的问题进行理解 3 提供个性化服务，根据不同的用户定制不同的服务 本文首先通过对大量标注问题集进行研究，利用有指导的机器学习的方法， 对用户提交的问题进行理解，即利用条件随机场模型对用户提交的关键字进行 角色标注，达到对用户问题的初步理解。然后，利用关键字标注的结果，调整 第1 章引言 关键字之间的权重比例，突出用户的中心词，达到优化排序结果的作用。最后， 通过对用户查询记录进行研究，隐式得获取用户兴趣，将用户兴趣分类应用到 搜索引擎的排序算法中去，针对不同的用户，调整网页权重，提供个性化的排 序结果。 1 4 论文结构 本文主要对搜索引擎的关键技术之一的排序算法进行了研究。在研究掌握 搜索引擎基本排序算法的基础上，对搜索引擎排序算法中的关键字之间的权重 分配和个性化方面提出了一些改进，并进行了一些试验。论文共分为六章： 第一章：引言部分对搜索引擎的发展历史进行了详细的介绍，引出课题研 究的意义。 第二章：排序算法简介部分分别对基于内容的排序算法、基于超链接分析 的排序算法和其他排序算法进行了详细的介绍，了解搜索引擎的基本排序算法。 第三章：相关技术准备部分对本文要用到的搜索引擎的排序流程、条件随 机场和l u c e n e 系统进行了详细的介绍为第四章和第五章做准备。 第四章：本章对整个系统的关键模块问句浅层语法分析模块和用户兴趣反 馈模块进行了详细的介绍。 第五章：我们在l u c e n e 的基础上，构建了一个优化的排序系统，并进行了相 应的实验。 第六章：最后，在仔细分析了系统的优缺点后，了解到系统中存在的优缺 点，在将来的工作中，将进一步完善系统。 4 第2 章搜索引擎排序算法简介 第2 章搜索引擎排序算法简介 2 1 基于内容的排序算法 2 1 1 词频加权 词频加权的方法有绝对词频加权、相对词频加权、反词频加权、基于词分 辨值加权等等。【4 】对于单一词搜索引擎，只用单纯地计算一个词在网页中的出现 频率就可给定权值；而对于具有进行逻辑组配功能的搜索引擎，则必须用其它 的加权方法。因为用组配的检索式检索时，检索结果跟检索式中的每个检索词 相关，而每个检索词在所有的网页中出现的总频率是不同的，如果按总权值来 排序，就会造成结果的不相关。这可以通过其它多种方法解决。例如，利用相 对词频加权原理，可以通过对大量网页的统计，把越是在所有网页中出现频率 高的词赋予一个较低的初始值；相对地，在所有网页中出现频率低的词，给一 个较高的权值。 2 1 2 词位置加权 通过对词在网页中不同位置和版式，给予不同的权值，从而根据权值来确 定所搜索的结果和搜索词的相关程度。【5 】词的位置包括：网页标题、网页描述 关键字、正文标题、正文内容、文本链接、a l t 标识等，版式包括：字体、字号、 有无加粗强调等。和传统文献一样，一般在较重要的位置如标题、正文的结尾 句等出现的词给较大的权值，例如要了解百度，在搜索“百度”时，有两个结 果，一个标题是百度介绍，另一篇文章的标题是( g o o g l e 介绍，但内容有个 别地方提到百度，显然第一个结果的相关性更大，“百度”这个词在第一个结果 中给予的权值应大一些。另外，字符较大、加粗强调的地方，一般也会给予较 大的权值。 2 1 3 词频和位置统计优缺点 第2 章搜索引擎排序算法简介 词频统计有易用，易实现的优点，其技术也发展得最成熟。至今仍是各搜 索引擎排序核心技术的基础，因为依靠单纯的链接分析，如果检索词和网页相 关度不高，就算网页的质量再高，再权威，相对用户来说也是没用的。词频统 计也有很多不足，它根本没有利用网络中网页有关的特性，可以说是前网络时 代的技术。然而，网络时代的主要文献是以网页的形式存在的，而几乎每个人 都可以随心所欲地在网上发表各种内容，词频相同的两个网页，质量相差可以 很远。为了能够排在某些检索结果的前几位，s e o ( s e a r c he n g i n eo p t i m i z i n g 针 对搜索引擎的优化人员) 绞尽脑汁，在其页面上堆砌关键词，例如，在网页中 加入和背景颜色一样的层，并加大量的关键词，这样，人来浏览网页时，完全 看不到，但搜索引擎在标引时，却能发现。对此，搜索引擎也研究出各种方法 来，发现和惩罚这种作弊的行为。【习 2 2 基于超链接分析的排序算法 2 2 1p a g e r a n k 算法 核心理论是一个网页的权威( p a g e r a i l l 【) 【6 1 值等于用户一开始随机访问所有 网页集合中的某一网页，以后再点击这个网页中的链接，不往回浏览以前的网 页时，用户点击某一链接的概率。p a g e r a n k 算法是链接分析的鼻祖，开创了一 个全新的搜索研究领域，其它的链接分析算法都或多或少包含t p a g e r a n k 算法 的一些思想，同时该算法本身也在不断地发展完善。 2 2 2 t s 算法 认为网页可分成两大类：权威网页和h u b 网页。【刀权威网页是指重要的网页， h u b 网页是指向权威网页链接集合的网页。h u b 本身可能不重要，但它指向重 要的网页。而好的h u b 网页指向许多好的权威网页，好的权威网页有许多好的 h u b 网页指向它，即权威网页和h u b 网页有互相加强的关系。 2 2 3s a l s a 算法 在上述两个算法的基础上，以色列学者r l e m p e l 和s m o r a n 于2 0 0 0 年在第 6 第2 章搜索引擎排序算法简介 9 届国际互联网大会上提出一个新的算法s a l s a 8 1 算法，其英文全称为 “s t o c h a s t i ca p p r o a c hf o rl i n ks t r u c t u r ea n a l y s i s ”。在保留p a g e r a n k 随机漫游和 h i t s 中h u b 值和权威值思想的同时，s a l s a 算法考虑了用户后退浏览网页的情 况，取消了h u b 值和权威值的互相加强关系。 2 2 4hiiit o p 算法 h i l l t o p 9 】同样是一项搜索引擎结果排序的专利，是g o o g l e 的一个工程师 b h a r a t 在2 0 0 1 年获得的专利。g o o g l e 的排序规则经常在变化，但变化最大的一次 也就是基于h i l l t o p 算法进行了优化。 h i l l t o p 算法的指导思想和p a g e r a n k 的是一致的，都是通过网页被链接的数 量和质量来确定搜索结果的排序权重。但h i l l t o p 认为只计算来自具有相同主题 的相关文档链接对于搜索者的价值会更大：即主题相关网页之间的链接对于权 重计算的贡献比主题不相关的链接价值要更高。如果网站是介绍“服装”的， 有l o 个链接都是从“服装 相关的网站链接过来，那这1 0 个链接比另外1 0 个从 “电器”相关网站链接过来的贡献要大。b h a r a t 称这种对主题有影响的文档为“专 家”文档，从这些专家文档页面到目标文档的链接决定了被链接网页“权重得 分 的主要部分。 与p a g e r a n k 结合h i l l t o p 算法确定网页与搜索关键词的匹配程度的基本排序 过程取代了过分依靠p a g e r a n k 的值去寻找那些权威页面的方法。这对于两个具 有同样主题而且p r 相近的网页排序过程中，h i l l t o p 算法就显得非常的重要了。 h i l l t o p h 时也避免了许多想通过增加许多无效链接来提高网页p a g e r a n k 值的作 弊方法。 2 3 其他算法 2 3 1 竞价排名 竞价排名是搜索引擎关键词广告的一种形式，按照付费最高者排名靠前的 原则，对购买了同一关键词的网站进行排名的一种方式。竞价排名也是搜索引 擎营销的方式之一，美国著名搜索引擎o v e r t u r e ( 2 0 0 3 年7 月被雅虎收购) 于2 0 0 0 7 第2 章搜索引擎排序算法简介 年开始首次采用，目前被多个著名搜索引擎采用。中文搜索引擎百度、一搜等 都采用了竞价排名的方式。竞价排名算不是真正意义上的排序方法，相反它可 以说是打破了排序的公平性，因此专家对这种排名方式的评价褒贬不一。但是， 通过商用实践可以发现，竞价排名也是一种非常成功的排序方式 2 4 算法优化 影响搜索引擎排序的因素有很多，经过对搜索引擎排序流程的仔细分析我 们就可以知道，对搜索引擎的排序优化可以从以下几个方面进行： 1 网页与关键字之间关联关系计算 2 关键字之间的关联关系计算 3 网页之间关联关系的计算 4 提高查询的广度 5 以上三方面关系之间，参数的调整。 2 4 1 网页与关键字之间的优化 一、锚文本( a n c h o r t e x t ) 例 锚文本名字听起来难以理解，实际上锚文本就是链接文本。例如，在个人 网站上把中央电视台( w w w c c t v c o m ) 作为新闻频道的链接，访问者通过点击 网站上的“新闻频道 就能进入h t t p ：w w w c c t v c o m 网站，那么“新闻频道 就 是中央电视台网站首页的锚文本。 锚文本可以作为锚文本所在的页面的内容的评估。正常来讲，页面中增加 的链接都会和页面本身的内容有一定的关系。服装的行业网站上会增加一些同 行网站的链接或者一些做服装的知名企业的链接；另一方面，锚文本能作为对 所指向页面的评估。锚文本能精确的描述所指向页面的内容，个人网站上增加 g o o g l e 的链接，锚文本为“搜索引擎”。这样通过锚文本本身就能知道，g o o g l e 是搜索引擎。 锚文本对搜索引擎起的作用还表现为可以收集一些搜索引擎不能索引的文 件。例如，网站上增加了一张张曼玉的照片，格式为j p g 文件，搜索引擎目前很 难索引( 一般只处理文本) 。若这张照片链接的锚文本为“张曼玉的照片”，那 8 第2 章搜索引擎排序算法简介 么搜索引擎就能识别这张图片是张曼玉的照片，以后访问者搜索“张曼玉”的时 候，这张图片就能被搜索到。 由此可见，在网页设计中选择合适的锚文本，会让所在网页和所指向网页 的重要程度有所提升。 二、页面版式p j 每个网页都有版式，包括标题、字体、标签等等。搜索引擎也会利用这些 版式来识别搜索词与页面内容的相关程度。以静态的h t m l 格式的网页为例，搜索 引擎通过网络蜘蛛把网页抓取下来后，需要提取里面的正文内容，过滤其他h t m l 代码。在提取内容的时候，搜索引擎就可以记录所有版式信息，包括：哪些词 是在标题中出现，哪些词是在正文中出现，哪些词的字体比其他的字体大，哪 些词是加粗过，哪些词是用k e y w o r d 标识过的等等。这样在搜索结果中就可以根 据这些信息来确定所搜索的结果和搜索词的相关程度。例如搜索“毛泽东一，假 如有两个结果，一篇文章标题是毛泽东的一生，另一篇文章的标题是江青 的一生但内容有提到毛泽东，这时搜索引擎会认为前者比较重要，因为“毛 泽东 在标题里出现了。 因此，合理的利用网页的页面版式，会提升网页在搜索结果页的排序位置。 三、词位置 武汉大学的杨广翔等在搜索引擎结果的重排序方法i io 】一文中，介绍了 如何根据关键字在文本中出现的位置信息来调整排序的方法。根据他们的研究 结果，多数相关度高的文档其关键词在文档中的分布往往是较为均匀的。而不 相关的文档即使词频较高，但关键词的分布并不均匀。因此，找到一个量来表 现词在文档中的分布情况，并用这个量帮助区分文档对关键词的相关程度，可 以迸一步改进排序结果。文章对具体的实现方法，计算公式进行了详细的描述。 2 4 2 关键字与关键字之间的关联关系优化 传统的关于计算文本相关度和网页和查询的相关性的计算都是采用匹配的 方式进行的，然而这只能是基于字面意义上的统计计算。这罩介绍的做法是采 9 第2 章搜索引擎排序算法简介 用关键词相关性扩展的做法从而得到更加精确的相关度计算。】 例子： 文章a ：谈论的是大学教育，最高频的关键词是：学生 3 】，学 - - j 2 ，大学【2 】 文章b ：谈论的是普通教育，最高频的关键词是：教育 5 】，教师 1 】，进修 1 】 口里是相对的权重，可以理解成t f * i d f 根据传统的相关性计算，我们会得到如下的结果： 文章a 与文章b 不相关 查询学生，学习，大学只能返回文章a ，不能返回文章b 查询教育，教师，进修只能返回文章b ，不能返回文章a 这个显然是有一定的问题的，问题的出现在于我们通常将字面的意思作为 分析的来源而且依靠和仅仅依靠这些字面的关键词作为文章相关性和查询相关 性判断的唯一要素。通过词扩展我们可以解决这个问题，举例说明： 当出现： - - ：t f ，i z l ，巧，x ，f ) + t & ( r ，x ，f ) ) 上 ( 3 2 ) 这里，( 巧- l 巧，x ，f ) 是关于整个观测序列和位置f 以及f l 标记的特征函数， ( ，x ，f ) 是关于位置f 的标记和观测序列的状态特征函数，这里参数乃和版是 特征权重，可从训练语料中估计得到。 当定义特征函数时，可以构造了观测序列的实数值特征d 五，j 集合来描述 训练数据的经验分布特征，这些特征与模型具有相同的分布。下面是一个例子： ，。，、f l 雅置i 的观测值是汉字“书” 以爿，j2 10 其他 ，q 口、 、 u u ， 每个特征函数表示一个实数值的观测特征d 【五，2 j ，如果当前状态( 状态函数) 或前一个状态和当前状态( 转移函数) 具有特定的值，则所有的特征函数都是实数 1 8 第3 章排序算法相关技术准备 值的。例如下面的转移函数。 杈蛳，精力孵动霎稚词4 ) 在后面的描述中，我们用式( 3 5 ) 来表示状态函数。 s , f f , ，x ，f ) = s t ( k - i ，巧，x ，f ) ( 3 5 ) 且 乃( 1 ，x ) = 乃( 巾，x ，n f ( 3 6 ) 式( 3 6 ) 中，特征函数乃( 小巧，x ，) 是一个状态特征函数& ( z ，x ，) 或者是一 个转移特征函数0 ( k - ，i ，x ，n 。因此对于一个给定观测序列 x = x l ，x 2 ，x i x 一，其对应的标记序列y = k ，k ，匕的概率为式( 3 7 ) 尸( y i x 卅= 去e x p ( 莩堋” ( 3 7 ) z ( x ) 是归一化因子( n o r m a l i z a t i o nf a c t o r ) 其形式如式( 3 8 ) z ( x ) = e x p ( t j f j ( y ，x ) ) 这样就可以表示出p ( y ix ) 了。 ( 3 8 ) 3 3 3 序列标记任务 现在我们用c r f 建立了p ( yx ) 的统计模型，求解序列标记任务就是求得y 。 满足p ( yx ) 最大，z ( x ) 与y 无关，所以y 为式( 3 9 ) 所示。 1 9 第3 章排序算法相关技术准备 y = a r g m a x p ( rix ) 2 a r g m 觚去e x p ( 莩乃w ) = a r g m a x e 旯j e j ( r ，x ) ( 3 9 ) 使用v i t e r b i 等动态优化方法，即可求出最优解】，。 3 3 4 条件随机场的参数估计 建立c r f 模型的主要任务就是从样本数据中估计得到特征权重力。c r f 参数 估计可以使用最大似然估计( m 戤i m u ml i k e l i h o o de s t i i i l a t i o i l m l e ) 和贝叶斯估计 ( b a y e se s t i m a t i o n ) 。下面主要介绍用最大似然估计估计c r f f f q 模型参数。 在训练集丁= ) 中，最大似然参数估计就是假设p ( y lx ，a ) 为旯的 函数，使p ( yx ，五) 的对数值最大的五为估计值，其似然值为式( 3 1 0 ) ，其最大 值为式( 3 11 ) 。 厶= l o g p ( y f x k , 五) 2 莩1 0 9 志懿p ( 莩乃( ) ) = ( 乃( y ，x ) - l o g ( z ( x ) ) ) r ， ( 3 1 0 ) 人= a r g m a x e l o g p ( y lx k , 五) t ( 3 1 1 ) 由于厶为凸函数，导数为零点为最值点。故对a 求导，则偏导数公式为式 ( 3 1 2 ) 。 瓦a - a = t ( y 孵x ) - - e p ( r l x , ) 啉x m ( 3 1 2 ) 可以简写为： 亟：0 ，一e ，：0 ( 3 1 3 ) 式( 3 1 3 ) 中，d 为- 在训练集r 中出现的频率，e j 2 e r e t , ( v l x ) e ( y ，x ) 】 第3 章排序算法相关技术准备 是乃在模型分布中的特征期望。岛如果直接计算需要很大的计算量，可以使用 动态规划的方法求解，如向前一向后( f o r w a r d r a c k w a r d ) 算法。 如果直接使用最大似然估计，可能会发生过度学 - j 问题，可以通过引入罚函 形2 ! 一 数的方法解决这一问题。例如使用惩罚项2 0 2 ，则原问题变为式( 3 1 4 ) 乃 三a - 厶一寺+ 脚 ( 3 1 4 ) 其导数变为式： 盟= 亟一生 弘仃2 ( 3 1 5 ) 于是五的参数估计问题可以用最优化方法解决。可以使用g i s ，i i s 等迭代方 法。 3 3 5 概率计算 对于一个链式结构的c r f ，可以为每个句子添加开始状态标记和结束状态标 记来标记序列，j o 和1 川分别表示开始标记和结束标记，给定一个观测序列x ， 标记序列y 的概率尸( y ix ，五) 可以使用矩阵进行有效的计算。 设甲是标记的字母表，y o 和y 。是来自这个字母表的标记，我们定义了n + 1 个矩阵的集合 m ，( x ) ii = l ，2 ，玎+ n ，这里每个m r ( x ) 都是一个i 甲甲l 的矩 阵，矩阵元素形式如式( 3 1 6 ) 。 m ，( 】，。lx ) = e x p ( y - 乃( 1 ，y 。，x ，f ) ) ， ( 3 1 6 ) 给定观测序列x ，没有归一化的标记序列y 的条件概率可以表示为甩+ 1 个矩 阵的元素的乘积，如式( 3 1 7 ) 。 p ( y 加高兀i = l m i ( m x ( 3 1 7 ) 2 1 第3 章排序算法相关技术准备 相似的，观察序列x 的归一化因子z ( x ) 可以通过使用c l o s e ds e m i r i n g s 方、法 a m ，( x ) 矩阵中计算得到，该代数结构是一个处理图中的路径问题的一般框架。 z ( x ) 的值由从开始位置到结束位置的m ，( x ) 矩阵的乘积给定。其形式如式 ( 3 1 8 ) z ( 耻 珥州删一耐 ( 3 1 8 ) 因此只要求出m ，( x ) 就可计算出z ( x ) 的值。 3 3 6 动态规划问题 在参数估计过程中，无论是使用迭代收敛还是基于梯度的方法，为计算出 极大似然的参数，对于训练数据中的每个观测序列x ，都必须有效地计算出每 个与c l u 模型分布相关的特征函数的期望e e m r ) 【( y ，x ) 】。 e p ( y i x ) 吲y , x k ) 】_ 志涉p ( 莩堋r 手咿锄( 3 1 9 ) 对式( 3 1 9 ) 直接计算的开销十分巨大，若标记序列x 有刀元素，则y 对应 元素为n l t 个，因此，通常使用类似h m m 中的向前一向后算法解决这个问题 3 6 】o 我们定义向前向后向量吒( x ) 和屈( x ) 为分别为式( 3 2 0 ) 和式( 3 2 1 ) 州叫，2 嚣犍“ 慨2 。， 邶旧2 器臻” 慨2 。， 其递归定义分别为式( 3 2 2 ) 和式( 3 2 3 ) 6 t i ( x ) 7 = 口( x ) r m f ( x ) ( 3 2 2 ) 屈( x ) = m i + i ( x ) 尼+ - ( x ) ( 3 2 3 ) 因此 似u w 砌= 喜莓堂盟半业地( 3 2 4 ) 并日 第3 章排序算法相关技术准备 z ( x ) = p o ( x ) = 口川( x ) ( 3 。2 5 ) 我们可以很快求出特征期望，从而能够使用机器学习的方法计算得到模型 睁征权值五。 ；4l u c e n e 及其排序系统 l u c r e 是a p a c h e 软件基金会j a k a r t a 项目组的一个子项目，是一个开放源代码 拘全文检索引擎工具包，即它不是一个完整的全文检索引擎，而是一个全文检 秦引擎的架构，提供了完整的查询引擎和索引引擎，部分文本分析引擎( 英文 与德文两种西方语言) 。l u c e n e 的目的是为软件开发人员提供一个简单易用的工 具包，以方便的在目标系统中实现全文检索的功能，或者是以此为基础建立起 完整的全文检索引擎。 l u c e n e 的原作者是d o u gc u t t i n g ，他是一位资深全文索引、检索专家，曾经 是v - t w i n 搜索引擎的主要开发者，后在e x c i t e 担任高级系统架构设计师，目前从 事于一些i n t e r n e t 底层架构的研究。早先发布在作者自己的 a t t p ：w w w 1 u c e n e c o m ，后来发布在s o u r c e f o r g e ，2 0 0 1 年年底成为a p a c h e 软件基 金会j a k a r t a 的一个子项目：h t t p ：j a k a r t a a p a c h e o r g l u e e n e 。 作为一个开放源代码项目，l u c e n e 从问世之后，引发了开放源代码社群的巨 大反响，程序员们不仅使用它构建具体的全文检索应用，而且将之集成到各种 系统软件中去，以及构建w e b 应用，甚至某些商业软件也采用t l u e e n e 作为其内 部全文检索子系统的核心。a p a c h e 软件基金会的网站使用了l u c e n e 作为全文检索 的引擎，i b m 的开源软件e c l i p s e 的2 1 版本中也采用了l u c e n e 作为帮助子系统的全 文索引引擎，相应的i b m 的商业软件w e bs p h e r e t 9 也采用了l u c e n e 。l u c e n e 以其 开放源代码的特性、优异的索引结构、良好的系统架构获得了越来越多的应用。 l u c e n e 作为一个全文检索引擎，其具有如下突出的优点： 1 索引文件格式独立于应用平台。l u c e n e 定义了一套以8 位字节为基础的 索引文件格式，使得兼容系统或者不同平台的应用能够共享建立的索引 文件。 2 在传统全文检索引擎的倒排索引的基础上，实现了分块索引，能够针对 新的文件建立小文件索引，提升索引速度。然后通过与原有索引的合并， 第3 章排序算法相关技术准备 达到优化的目的。 3 优秀的面向对象的系统架构，使得对于l u c e n e 扩展的学习难度降低，方 便扩充新功能。 4 设计了独立于语言和文件格式的文本分析接口，索引器通过接受t o k e n 流完成索引文件的创立，用户扩展新的语言和文件格式，只需要实现文 本分析的接口。 5 已经默认实现了一套强大的查询引擎，用户无需自己编写代码即使系统 可获得强大的查询能力，l u c e n e 的查询实现中默认实现了布尔操作、模 糊查询、分组查询等等。 l u c e n e 系统的排序是根据信息检索的向量空间模型来计算的。文档( d ) 和 查询条件( q ) 之间越接近，那么文档( d ) 的得分就越高。计算公式如下： s c o r e ( q ，d ) = c o o r d ( q ，d ) q u e r y n o r m ( q ) ( 矿( t i n d ) i d f ( t ) y f g e t b o o s t ( ti n t i n q t g e t b o o s t ( t f i e l d i nd ) 宰l e n g t h n o r m ( t f i e l d 伽d ) ) ( 3 2 6 ) 其中： 1 t f ( ti nd ) 表示的是查询条件中，每个( t ：t e r m ) 在本文档( d ) 中的出 现频率。查询关键词出现的频率越高，文档的得分就越高。这个部分的 默认计算公式( 3 2 7 ) 是： t f f ti nd ) 2f r e q u e n c y ( 3 2 7 ) 2 渺( f ) 表示的是反转文档频率( i n v e r s ed o c u m e n tf r e q u e n c y ) 这个函数 表示的是( t ：t e r m ) 在所有文档中一共在多少个文档中出现过。因为文 档出现的次数越少就越容易定位，所以文档数越少，得分就越高。这个 函数的默认计算公式( 3 2 8 ) 如下： i d f ( 归o g ( 竺d o c p 筹r e ) ( 3 2 8 ) + l ( 叉9 r 1 3 1 e n g t h n o r m ( t f i e l d i n d ) 这个函数并不影响排序的效果，主要用来调 节各个字段之i b j 的比重。例如，当一个词在一个长字段中出现和在一个 第3 章排序算法相关技术准备 短字段中出现时，在短字段中出现的时候比重应该更大一些。这个函数 的默认计算公式如下： l e n g t h n o r m ( t f i e l d i n d ) = 1 n u m t o k e n s ( 3 ：2 9 ) 4 c o o r d ( q ，d ) 这个函数表示的是在这个文档( d ) 中t e r r n ( t ) 出现的百分 比，也就是文档中出现的不同t e r m 数量和查询条件( q ) 中的不同t e r m ( t ) 的数量之比。所以，文档中出现的t e r m 种类越多，分值就高。 5 q u e r y n o r m ( q ) 这个函数是一个调节因子，不影响具体的排序情况。主要 是用来让排序结果在不同的查询条件( 或者不同的索引) 之间可以比较。 这个条件是在搜索的时候计算的。它的计算公式( 3 3 0 ) 如下： q u e r y n o r m ( q ) = q u e r y n o r m ( s u m o f f q u a r e d w e i g h t s ) 1 = 耳= s u m o f s q u a r e d w e 嘞t s “ ( 3 3 0 ) 6 t h es u m o f s q u a r e dw e i g h t s ( 查询条件的t 锄s ) 是由查询的权重对象计算 的。不同的查询方式，有不同的计算方法。例如：b o o l e a nq u e r y 的计算 公式( 3 3 1 ) 如下： s u m o j s q u a r e d w e i g h t s = q g e t b o o s t o 。z ( i d f ( f ) ，i c f g e t b o o s t o ) 2 第4 章排序算法关键模块分析 第4 章排序算法关键模块分析 4 1 问句浅层语法分析流程 本文对问句的语法分析主要是对问句中的谓词