您的位置: 首页 > 技术文档 > 网站建设 > 搜索引擎中的粒度问题
DNS优化的原理和方法 回到列表 优秀产品经理所需具备的7种能力
 搜索引擎中的粒度问题

作者:xinzhou 时间: 2011-12-02 文档类型:合作网站提供 来自:百度搜索引擎研发部

一.前言

传统的搜索引擎的定义,是指一种对于指定的查询(Query),能够返回与之相关的文档集合(Documents)的系统。而百度将这个定义更加丰富化,即搜索引擎能够帮助人们更方便的找到所求。这里的“所求”,比“文档”更加宽泛和丰富,比如一个关于天气的查询,直接返回一个天气预报的窗口,而非一篇关于天气的文档;再如一个关于小游戏的查询,直接返回这个小游戏的Flash页面而非简单的介绍性的文字。

百度对Query深刻的理解,源于自然语言处理技术在其中发挥的巨大作用。对搜索引擎而言,文本切分是最基础也是最重要的自然语言问题之一。今天,我们就来谈谈文本切分粒度与搜索引擎的关系。

本文后续章节组织如下:第二节介绍什么是文本的粒度,第三节讲述搜索引擎的基本原理与文本切分粒度的关系,第四节深入探讨粒度的属性与检索相关性计算,第五节小结。

二.文本粒度

什么是文本的粒度?我们用什么来衡量文本粒度?在回答这些问题前,让我们先看看以下几组词汇:

缠绵、崎岖、葡萄、乒乓

绿茶、篮球、红色、鼠标垫、起重机

打球、跳绳、炒菜、登山

笔记本电脑、高清机顶盒、IP电视

但是、然后、如果、非常

步步惊心、家的n次方、一个人的精彩

百度在线网络技术(北京)有限公司、清华大学

张学友、赵传、工藤新一、里奥内尔·安德雷斯·梅西

……

这几组词汇中,哪些的粒度大,哪些的粒度小?

不管在传统的语言学领域,还是在自然语言处理领域,都没有对粒度下一个清晰准确的定义。但是就搜索引擎而言,我们不妨这样定义:粒度是衡量文本所含信息量的大小。文本含信息量多,粒度就大,反之就小。有了这个原则,我们就很容易判断文本粒度大小了。像“缠绵”,“崎岖”,“葡萄”这些词,虽然有两个字组成,但是仅表达一个意思,这些词的粒度是小的。而“篮球”,“鼠标垫”等词,是由简单词合成的,虽然也只有一个意思,但还可以拆分,如“篮”和“球”,“鼠标”和 “垫”。这类词,粒度稍微大一些。而“笔记本电脑”,“高清机顶盒”这样的词,粒度就更大了。

专名是一类比较特殊的词,尽管所含字数很多,但其实只表达一个意思,如“步步惊心”,“家的n次方”这样的电影、电视剧的名称,粒度是很小的。机构名、人名等属于有内部结构的专名,比电影名的粒度稍大一些。

显然易见,我们在讨论文本粒度时,理想的方式是从语义角度出发,合理的分析和判断。然而以上我们仅对粒度做了定性的分析,为粒度找一个合适的度量单位和计算方法,是百度人一直追求的目标。

三.搜索引擎的基本原理与词汇切分关系

3.1 搜索引擎的基本原理

文本检索系统,是搜索引擎最简单的实现方式。通过返回包含关键字的页面,来满足用户的检索需求。形式化的表达就是给定一系列关键字集合K,要求返回所有包含关键字的文档D,对D中的任意一个文档d,包含K中的任意一个关键字k。

一般我们采用倒排索引的方式来实现这个系统。所谓倒排索引,就是对关键字建立索引,记录包含这个关键字的文档集合D。对于请求的关键字集合,找出所有关键字对应的索引,并对索引求交,最后返回同时存在于所有索引中的文档。

在百度,我们不仅允许用户输入关键字,也可以输入任何长度在一定范围内的文本。此时我们需要对文本做一定处理,切分成一系列关键字,从而能够从倒排索引中找出对应的文档。

那么为什么要对输入文本做切分,如果不切分会有什么问题?

我们可以想象一下,如果不对输入文本做切分,直接用输入文本去做匹配,会怎么样?首先,得到的结果会非常少,因为直接用全部文本匹配,就失去了灵活性,对结果限制的非常死,必须完全匹配才能满足要求;其次,系统性能会非常差,因为需要对所有长度的文本都建立索引,这是指数级的,在实际系统中根本不可能实现。再考虑一下另一个极端?我们对输入文本做单字切分,结果又是怎样?我们会得到大量无关的页面,不仅浪费系统性能,对相关性计算也造成了巨大的压力。

所以,我们需要对文本做一个合适的切分。

3.2 用户满意度与粒度关系

无论是建立倒排索引、还是处理输入文本,我们都需要对文本做切分,切出合适的关键字出来。为了能够使用户对查询结果满意,搜索引擎需要什么样的粒度?让我们先看一下下面几个例子:

1. Q:“北京地图” P1:“北京市地图” P2:“北京城市地图”

2. Q:“闹太套是神马意思”, P:”A:神呐,我骑不了这烈马。B:闹太套!”

3. Q:“兽兽门” P:“兽兽艳照门”

4. Q1:“工业园” Q2:“园区” P:“工业园区”

5. Q:“ip电视” P1:“ip电视的历史” P2:“电视销售…您的IP是xxx”

注:Q表示query,P表示页面中包含Q的内容

Case1,要求query能找到P1和P2这样的结果,就必须对P1和P2都切出“北京”这个词来。Case2,必须把”神马”切为一个词,否则会召回P这样不相关的结果。Case3,不能把Q中的“兽兽门“切为一个词,而需要切除“兽兽”,否则就召不回”兽兽艳照门”这个结果。Case4中,对“工业园区”这样的页面,必须同时切出“工业园”和“园区”这两个重叠的词汇,才能保证Q1 和Q2都能召回。Case5与Case2类似,如果把ip和电视分开切分,将召回P2这样不相关的结果。

以上几个case,基本上概括了搜索引擎对切分粒度的要求,我们可以从两方面来描述:1)影响召回 2)影响相关性

以上从用户满意度的角度,讨论了搜索引擎与粒度的关系,当然,这是最基本的要求,在第四节我们还会对文本的粒度问题做更深入的分析。

3.3 搜索系统性能与粒度的关系

显而易见,粒度越小,召回就越多,建立倒排索引时,索引的长度就越长;粒度的层次越多,索引的数量就越多。一个多,一个长,就对搜索系统的性能构成了极大的考验。

一般而言,大型搜索引擎的索引都采用分布式系统。不同文本的索引,被某种hash算法 “分配”到了某台机器。理论上讲,索引的数量的增长,只会造成所需机器的增长,而对整体系统性能的消耗影响比较小。所以一般搜索引擎会从性价比的角度来考虑索引数量与机器数量的折衷,也就是召回与硬件投入的折衷。粒度分析对于折衷的性价比也有一定的贡献,在粒度层次里,当粒度逐渐变小的过程中,我们并不一定对所有小粒度词都建索引,而是选择“更有可能召回相关结果”的小粒度词。词汇的什么性质决定了“更有可能召回相关结果”?我们同样会在第四节讨论。

四.深入分析粒度的性质

在第三节中我们反复提到:一般情况下,粒度越大,相关性越好,召回越差;粒度越小,相关性越差,召回越好。在搜索引擎中,如果做到折衷呢?基本的原则是,在系统性能可接受的前提下,尽量多召回有效结果,计算相关性时,将最相关的排在前面。

我们如何做到将合理减小粒度,增加有效召回,又如何做到将最好的排在最前呢?这里涉及到两个问题:紧密度与重要性。

既然粒度是衡量文本所含信息量的大小,那么紧密度就是描述文本所含信息紧密程度的量。再说的通俗一些,紧密度就是信息被人们表达和接受的稳定程度。稳定有两种解释,第一,稳定是相对于临时而言的。一般来说,如果信息是因为某些因素临时组合在一起,那就是不稳定的,即不紧密。比如许多动宾结构的短语(“过马路”,“踢足球”),定中结构的短语(“红苹果”,“豪华轿车”)。第二,稳定是相对于顺序不固定而言的。如果同样一个信息,内部的子信息顺序可以互换,那么这个词汇就不稳定,即不紧密。比如一些大粒度的词汇“鼠标护腕垫”、“护腕鼠标垫”。

由此可见,我们根据词汇的紧密程度,可以将结果中表述与查询表述的一致程度联系起来,作为计算相关性的一个因素。同样,我们也可以将紧密度作为减小粒度的依据之一,词汇越不紧密,我们就有理由将其拆分为更小的粒度。

短语的重要性,其实是短语子成分的重要性,有很多定义。其中一种被普遍接受的定义为其占短语完整含义的比例。一般情况下,偏正结构短语中,“正”的部分比较重要,比如“绿茶”中的“茶”,但也有例外,如“珊瑚虫”中的“珊瑚”。而主谓、动宾短语一般来说,都比较重要,如“打球”,“你说”。所以,短语的子成分重要性,不能仅靠语法来识别,而应综合各种因素来确定。

假设有了词汇的子成分重要性,那么就可以帮助判断将词汇粒度变小后的语义损失风险程度(注意,这里使用了“语义损失”,而不是“转义”,想一想为什么)。这也就回答了第四节末尾的问题:语义损失越小,越有可能召回相关结果。

五.结束语

本文介绍了搜索引擎中的粒度问题,重点讨论了搜索引擎与短语切分粒度的关系,并进一步探讨了短语的两个重要性质——紧密度和重要性。通过本文,读者应该能够大致明白搜索引擎中关于粒度的种种。当然,本文只是对搜索引擎的粒度问题开了一个头,怎么合理的处理好粒度、在不同场合使用何种粒度,都是需要我们继续深入研究的。

本文链接:http://www.blueidea.com/tech/site/2011/8691.asp 

出处:百度搜索引擎研发部
责任编辑:bluehearts

◎进入论坛网站综合网页制作版块参加讨论

相关文章 更多相关链接
jQuery+Bing API实现简易搜索引擎
电子商务搜索引擎的细节设计
基于Sphinx+MySQL全文检索架构设计
搜索引擎优化基础知识PPT
利用日志维护TAG
热门搜索:CSS Fireworks 设计比赛 网页制作 web标准 用户体验 UE photoshop Dreamweaver Studio8 Flash 手绘 CG
站点最新 站点最新列表
周大福“敬•自然”设计大赛开启
国际体验设计大会7月将在京举行
中国国防科技信息中心标志征集
云计算如何让安全问题可控
云计算是多数企业唯一拥抱互联网的机会
阿里行云
云手机年终巨献,送礼标配299起
阿里巴巴CTO王坚的"云和互联网观"
1499元买真八核 云OS双蛋大促
首届COCO桌面手机主题设计大赛
栏目最新 栏目最新列表
浅谈JavaScript编程语言的编码规范
如何在illustrator中绘制台历
Ps简单绘制一个可爱的铅笔图标
数据同步算法研究
用ps作简单的作品展示页面
CSS定位机制之一:普通流
25个最佳最闪亮的Eclipse开发项目
Illustrator中制作针线缝制文字效果
Photoshop制作印刷凹凸字体
VS2010中创建自定义SQL Rule
分享按钮

蓝色理想版权申明:除部分特别声明不要转载,或者授权我站独家播发的文章外,大家可以自由转载我站点的原创文章,但原作者和来自我站的链接必须保留(非我站原创的,按照原来自一节,自行链接)。文章版权归我站和作者共有。

转载要求:转载之图片、文件,链接请不要盗链到本站,且不准打上各自站点的水印,亦不能抹去我站点水印。

特别注意:本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有,文章若有侵犯作者版权,请与我们联系,我们将立即删除修改。

您的评论
用户名:  口令:
说明:输入正确的用户名和密码才能参与评论。如果您不是本站会员,你可以注册 为本站会员。
注意:文章中的链接、内容等需要修改的错误,请用报告错误,以利文档及时修改。
不评分 1 2 3 4 5
注意:请不要在评论中含与内容无关的广告链接,违者封ID
请您注意:
·不良评论请用报告管理员,以利管理员及时删除。
·尊重网上道德,遵守中华人民共和国的各项有关法律法规
·承担一切因您的行为而直接或间接导致的民事或刑事法律责任
·本站评论管理人员有权保留或删除其管辖评论中的任意内容
·您在本站发表的作品,本站有权在网站内转载或引用
·参与本评论即表明您已经阅读并接受上述条款
推荐文档 | 打印文档 | 评论文档 | 报告错误  
专业书推荐 更多内容
网站可用性测试及优化指南
《写给大家看的色彩书1》
《跟我去香港》
众妙之门—网站UI 设计之道
《Flex 4.0 RIA开发宝典》
《赢在设计》
犀利开发—jQuery内核详解与实践
作品集 更多内容

杂⑦杂⑧ Gold NORMANA V2