Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 搜索引擎技术概述　
发信站: 哈工大紫丁香 (2001年07月03日19:02:43 星期二), 站内信件

搜索引擎（Search Engine）是随着WEB信息的迅速增加，从1995年开始逐渐发展起来的
技术。据发表在《科学》杂志1999年7月的文章《WEB信息的可访问性》估计，全球目前
的网页超过8亿，有效数据超过9T，并且仍以每4个月翻一番的速度增长。用户要在如此
浩瀚的信息海洋里寻找信息，必然会“大海捞针”，无功而返。搜索引擎正是为了解决
这个“迷航”问题而出现的技术。它以一定的策略在因特网中搜集、发现信息，对信息
进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导航的作用。搜
索引擎提供的导航服务已经成为因特网上非常重要的网络服务，搜索引擎站点也被美誉
为“网络门户”。搜索引擎技术因而成为计算机工业界和学术界争相研究、开发的对象
。
一、 搜索引擎的分类
 按照信息搜集方法和服务提供方式的不同，搜索引擎系统可以分为三大类：
1． 目录式搜索引擎（Directory Search Engine）
以人工方式或半自动方式搜集信息，由编辑员查看信息之后，人工形成信息摘要，并将
信息置于事先确定的分类框架中。信息大多面向网站。提供目录浏览服务和直接检索服
务。该类搜索引擎因为加入了人的智能，所以信息准确、导航质量高，缺点是需要人工
介入（维护工作量大）、信息量少、信息更新不及时。
这类搜索引擎的代表是：Yahoo！、LookSmart、Ask Jeeves、Snap 、Open Directory。

2． 机器人搜索引擎（Crawler-Based Search Engine）
由一个称为蜘蛛（Spider）的机器人程序以某种策略自动地在Internet中搜集和发现信
息，由索引器为搜集到的信息建立索引，由检索器根据用户的查询输入检索索引库，并
将查询结果返回给用户。服务方式是面向网页的全文检索服务。该类搜索引擎的优点是
信息量大、更新及时、毋需人工干预，缺点是返回信息过多，有很多无关信息，用户必
须从结果中筛选。
这类搜索引擎的代表是：AltaVista、Northern Light、Excite、Infoseek、Inktomi、
FAST、Lycos、Google。
3． 元搜索引擎（Meta Search Engine）
这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，将返
回的结果进行重复排除、重新排序等处理后，作为自己的结果返回给用户。服务方式为
面向网页的全文检索。这类搜索引擎的优点是返回结果的信息量大，缺点是不能够充分
使用原搜索引擎的功能，用户需要做更多的筛选。
这类搜索引擎的代表是WebCrawler、InfoMarket。
目前，商业的搜索引擎站点正在结合各种搜索引擎的优点，在类型上有逐渐融合的趋势
。例如，Yahoo！在保持人工分类的同时，使用Inktomi的机器人搜索引擎，用户查询时
，如果选择“网站搜索”便搜索人工分类库，选择“网页搜索”便搜索机器人搜索引擎
的索引库。一些传统的机器人搜索引擎也增加了人工分类的内容，以提供高精度的导航
信息。另外搜索引擎站点有“门户化”的倾向，在提供搜索服务的同时，提供多样的网
络服务，如新闻、股票、天气预报、虚拟社区、游戏、电子商务等等，成为名符其实的
“网络门户”。
二、 搜索引擎的性能指标
我们可以将WEB信息的搜索看作一个信息检索问题，即在由WEB网页组成的文档集中检索
出与用户查询相关的文档。所以我们可以用衡量传统信息检索系统的性能参数---召回率
（Recall）和精度（Precision）---来衡量一个搜索引擎的性能。
召回率是检索出的相关文档数和文档集中所有的相关文档数的比率，衡量的是检索系统
（搜索引擎）的查全率；精度是检索出的相关文档数与检索出的文档总数的比率，衡量
的是检索系统（搜索引擎）的查准率。对于一个检索系统来讲，召回率和精度不可能两
全其美：召回率高时，精度低；精度高时，召回率低。所以常常用11种召回率下11种精
度的平均值（即11点平均精度）来衡量一个检索系统的精度。对于搜索引擎系统来讲，
因为对于一个查询总能返回很多信息，所以召回率一般不成问题；加之，没有一个搜索
引擎系统能够搜集到所有的WEB网页，召回率很难比较，所以衡量搜索引擎的性能时，召
回率很少使用。目前的搜索引擎系统都非常关心精度，即是否为用户提供了相关度很高
的、高质量的导航信息。
搜索引擎系统的其它衡量指标还有响应时间、支持峰值查询的能力、易用性、返回结果
的有效性（是否为死链、过时信息）等等。
影响一个搜索引擎系统的性能有很多因素，最主要的是信息搜集策略和检索模型，包括
索引库的更新频率和策略、文档和查询的表示方法、评价文档和用户查询相关性的匹配
策略、查询结果的排序方法和用户进行相关度反馈的机制。
三、 搜索引擎组成部分及其主要技术
一个搜索引擎由搜索器（Spider）、索引器（Indexer）、检索器（Searcher）和用户接
口（User Interface）等四个部分组成。
1、 搜索器
搜索器的功能是在Internet中漫游，发现和搜集信息。它常常是一个计算机程序，日夜
不停地运行。它要尽可能多、尽可能快地搜集各种类型的新信息，同时因为Internet上
的信息更新很快，所以还要定期更新已经搜集过的旧信息，以避免死连接和无效连接。
目前有两种搜集信息的策略：
 从一个起始URL集合开始，顺着这些URL中的超链（Hyperlink），以宽度优先
、深度优先或启发式方式循环地在Internet中发现信息。这些起始URL可以是任意的URL
，但常常是一些非常流行、包含很多链接的站点（如Yahoo！）。
 将Web空间按照域名、IP地址或国家域名划分，每个搜索器负责搜集一个子空
间的信息。
搜索器搜集的信息类型多种多样，包括HTML文本、XML文本、正文文本、Newsgroup文章
、FTP文件、字处理文档（如Word、Postscript、PDF）、多媒体信息（如地图、图形、
图象、声音）等。
搜索器的实现常常用分布处理和并行计算技术，以提高信息发现和更新的速度。商业搜
索引擎的信息发现速度可以达到每天几百万网页。
2、 索引器
索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项，用于表示文档以及生成
文档集的索引表。
索引项（term）有客观索引项（Objective Terms）和内容索引项（Content Terms）两
种：客观项与文档的语意内容无关，如作者名、URL、更新时间、编码、长度、链接流行
度（Link Popularity）等等；内容索引项是用来反映文档内容的，如关键词及其权重、
短语、单字等等。内容索引项可以分为单索引项和多索引项（或称短语索引项）两种。
单索引项对于英文来讲是英语单词，比较容易提取，因为单词之间有天然的分隔符（空
格）；对于中文等连续书写的语言，必须进行词语的切分。
在搜索引擎中，一般要给单索引项赋与一个权值，以表示该索引项的重要程度及对文档
的区分度，同时用来计算查询结果的相关度。使用的方法一般有统计法、信息论法和概
率法。短语索引项的提取方法有统计法、概率法和语言学法。
索引表一般使用某种形式的倒排表（Inversion List），即由索引项定位相应的文档。
索引表也可能要记录索引项在文档中出现的位置，以便检索器计算索引项之间的相邻或
接近关系（proximity）。
索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实现即时索
引（Instant Indexing），否则不能够跟上信息量急剧增加的速度。索引算法对索引器
的性能（如大规模峰值查询时的响应速度）有很大的影响。一个搜索引擎的有效性在很
大程度上取决于索引的质量。
3、 检索器
检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与查询的相关度评
价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。
检索器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合模型四种。
 集合理论模型
   集合理论模型又分为布尔模型（Boolean Model）和模糊集合（Fuzzy-set Model）模
型两种。
   布尔模型用一组索引项表示文档，每个索引项可看作一个布尔变量，如果该索引项在
文档中出现，则取值为真。索引项没有权值。查询表示为由逻辑运算符（与、或、非）
连接起来的布尔表达式。检索状态值（Retrieval Status Value，RSV）用来度量文档和
查询的相似度。如果查询表达式的值为真，则RSV值为1，否则为0。所有RSV为1的文档与
查询相关。这种模型实现简单（算法简单、对存储文档表示要求不高），但是检索性能
较差。因为所有检索出的文档有相同的RSV，所以无法对输出结果进行排序，用户相关度
反馈也很难实现。
   模糊集合模型使用了模糊集合理论。模糊集合理论与传统集合理论的不同之处在于，
它允许集合的部分成员关系。模糊集合模型重新定义了逻辑运算以包含集合部分成员关
系，用户查询的处理方法和布尔模型类似。但实验证明，该模型和布尔模型有同样的缺
点。
 代数模型
   代数模型又称为向量空间模型（Vector Space Model）。它将文档表示为由n个经过
归一化处理的索引词构成的n维空间中的向量，该向量第k维的值（第k个分量）表示第k
个索引项在文档中的权值。用户查询也同样表示为一个n维向量。文档和查询的RSV是这
两个向量的标量乘积（Scalar Product），RSV越大，文档和查询的相关度便越大。该模
型可以很容易地进行输出结果的排序，用户相关性反馈机制也很容易实现。其主要缺点
是，用户查询时输入的索引项（关键词）较少，查询向量的很多分量为0，很难准确地计
算RSV；它假设向量空间的每一维都是正交的（Orthogonal），没有考虑索引项之间的相
关关系。
 概率模型
   概率模型考虑了索引项之间的相关关系，并定义了查询词权值等主要参数以及查询和
文档间相似度的形式。概率模型中有两个主要参数：一篇文档与查询的相关概率Pr（re
l）和无关概率Pr（nonrel）。它们是用索引项的概率权值和文档中实际出现的索引项计
算得到的。另外，使用两个损失参数a1，a2分别表示在无关文档中检出和在相关文档中
漏检的损失。概率模型因为同时考虑了文档集中相关和不相关部分对索引项权值的影响
，所以能较好地表示检索过程。
 混合模型
   混合模型又称为扩展的布尔模型（Extended Boolean Model）。该模型与向量空间模
型一样，将文档表示为n维空间中的向量，不同的是它用两个向量之间一般化（general
ized）的标量乘积衡量文档和查询的相似度。随着一般化参数的变化，该模型可以变为
向量空间模型、模糊集合模型和布尔模型。
   上述一些模型都是信息检索系统常用的信息检索模型，经过多年的研究、开发已基本
成熟，搜索引擎索引器可以选择使用。
4、 用户接口
用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。主要的目
的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、及时的信息。
用户接口的设计和实现使用人机交互（Computer Human Interaction）的理论和方法，
要充分适应人类的思维习惯。
用户输入接口可以分为简单接口和复杂接口两种。简单接口面向普通非专业的查询用户
，一般只提供内容浏览和简单的输入框；复杂接口面向专业的查询用户，可以让用户指
定查询条件和查询限制，如逻辑运算（与、或、非；+、-）、相近关系（相邻、NEAR）
、域名范围（如.edu、.com）、出现位置（如标题、内容）、信息时间、长度等等。目
前一些公司和机构正在考虑制定查询选项的表示标准。
四、 搜索引擎技术未来的几个发展动向
搜索引擎已成为一个新的研究、开发领域。因为它要用到信息检索、人工智能、计算机
网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理等多领域的理论和
技术，所以具有综合性和挑战性。又由于搜索引擎有大量的用户，能为用户提供信息检
索服务，有很好的经济价值，所以引起了世界各国计算机科学界和信息产业界的高度关
注，目前的研究、开发十分活跃，并出现了很多值得注意的动向。
1、 十分注意提高信息查询结果的精度，提高检索的有效性。
用户在搜索引擎上进行信息查询时，并不十分关注返回结果的多少，而是看结果是否和
自己的需求吻合。对于一个查询，传统的搜索引擎动辄返回几十万、几百万篇文档，用
户不得不在结果中筛选。解决查询结果过多的现象目前出现了几种方法：一是通过各种
方法获得用户没有在查询语句中表达出来的真正用途，包括使用智能代理跟踪用户检索
行为，分析用户模型；使用相关度反馈机制，使用户告诉搜索引擎哪些文档和自己的需
求相关（及其相关的程度），哪些不相关，通过多次交互逐步求精。二是用正文分类（
Text Categorization）技术将结果分类，使用可视化技术显示分类结构，用户可以只浏
览自己感兴趣的类别。三是进行站点类聚或内容类聚，减少信息的总量。
2、 基于智能代理的信息过滤和个性化服务
信息智能代理是另外一种利用Internet信息的机制。它使用自动获得的领域模型（如We
b知识、信息处理、与用户兴趣相关的信息资源、领域组织结构）、用户模型（如用户背
景、兴趣、行为、风格）知识进行信息搜集、索引、过滤（包括兴趣过滤和不良信息过
滤），并自动地将用户感兴趣的、对用户有用的信息提交给用户。智能代理具有不断学
习、适应信息和用户兴趣动态变化的能力，从而能够提供用户化服务（Customization）
和个性化服务（Personalization）。智能代理可以在用户端运行，也可以在服务器端运
行。
3、 采用分布式体系结构提高系统规模和性能
搜索引擎的实现可以采用集中式体系结构和分布式体系结构，两种方法各有千秋。但当
系统规模达到一定程度（如网页数达到亿级）时，必然要采用某种分布式方法，以提高
系统性能。搜索引擎的各个组成部分，除了用户接口之外，都可以进行分布：搜索器可
以在多台机器上相互合作、相互分工进行信息发现，以提高信息发现和更新速度；索引
器可以将索引分布在不同的机器上，以减小索引对机器的要求；检索器可以在不同的机
器上进行文档的并行检索，以提高检索的速度和性能。
4、 重视交叉语言检索的研究和开发
交叉语言信息检索是指用户用母语（如汉语）提交查询，搜索引擎在多种语言（如英语
、法语、德语、日语）的数据库中进行信息检索，返回能够回答用户问题的所有语言的
文档。如果再加上机器翻译，返回结果可以用母语显示。该技术目前还处于初步研究阶
段，主要的困难在于语言之间在表达方式和语义对应上的不确定性（如依赖于上下文、
一字多义）。但对于经济全球化、Internet跨越国界的今天，无疑具有很重要的意义。

5、 注意搜索引擎技术和其它信息技术的相互借鉴
前文已经指出，搜索引擎是一个综合性很强的领域，必然要使用信息技术其它领域的理
论和技术。搜索引擎面对的是因特网上时刻处于动态变化的海量信息，在计算机的发展
史上，我们从来没有处理过如此大规模的数据，原有的理论和技术必须进行相应的改造
才能加以有效的利用，才能解决好搜索引擎面对的问题。另一方面，搜索引擎使用的技
术也可以被其它领域的应用所使用。例如搜索引擎是基于检索技术的应用，它的用户模
型和非基于检索技术的应用（Non-search-technology-based Applications）的用户模
型有很大的不同。但它们会面对很多共同的问题。例如非基于检索技术的应用都要提供
某种形式的过滤服务，如信息选径（Routing）、分类（Categorization）、类聚（Clu
stering）、抽取（Extraction）、文摘（Abstraction）、事件检测（Event Detectio
n）等等，而这种服务在搜索引擎系统中也要提供，这两种系统所用技术的相互借鉴将有
助于更好地解决各自领域的问题。
6、 重视学术研究
   目前搜索引擎领域的商业开发非常活跃，各大搜索引擎公司都在投巨资研制搜索引擎
系统，同时也不断地涌现出新的具有鲜明特色的搜索引擎产品，搜索引擎已经成为信息
领域的产业之一。在这种情况下，对搜索引擎技术相关领域的学术研究得到了大学和科
研机构的重视。如Stanford大学在其数字图书馆项目中开发了Google搜索引擎，在Web信
息的高效搜索、文档的相关度评价、大规模索引等方面作了深入的研究，取得了很好的
成果。NEC美国研究所的Steve Lawrence和C. Lee Giles 1998年和1999年连续两年在《
自然》（Nature）和《科学》（Science）杂志上撰文对搜索引擎技术的研究进行评述。
 IBM Almaden研究中心研制了Clever系统，对网页链接结构在对内容相关度的评价、网
页的分类、有共同兴趣团体的发现等方面的作用进行了研究，取得了值得重视的成果。
由美国国家标准和技术研究院（NIST）、信息访问和用户界面公司（IAUI）、信息技术
实验室（ITL）的自然语言处理和信息检索部（NLPIR）和国防部高级研究计划署（DARP
A）信息技术处共同主办的正文检索会议（TREC）也将从第8届（1999年11月）开始增加
Web Track竞赛项目，以考察Web文档与其它类型文档在性质上的不同之处，并将测试在
大规模的Web文档集上进行信息检索的算法性能。由英国Infonortics公司主办的搜索引
擎国际会议从1996年开始，每年举行一次，对搜索引擎技术进行总结、讨论和展望，参
加者有著名的搜索引擎公司、大学和研究机构的学者，对搜索引擎技术起到了很好的推
动作用。另外像IEEE主办的国际万维网会议（International World Wide Web Confere
nce）、ACM主办的人机交互会议（Computer Human Interaction，CHI）等重要学术会议
已有越来越多关于搜索引擎技术研究的文章发表。
国内先后有北京大学、清华大学、国家智能研究中心等高校和研究单位对搜索引擎技术
开展研究，并开发出了几个较好的系统。如由北京大学计算机系网络研究室开发的“天
网”中英文搜索引擎（http：//pccms.pku.edu.cn:8000/gbindex.htm）,在系统规模及
系统性能方面达到了国外中型搜索引擎系统的技术水平，为国内用户提供了很好的Inte
rnet搜索服务，受到了用户的好评。但是总体来讲，我们在对大规模、高性能搜索引擎
系统的研究和开发方面投入不够，产业界对自主开发搜索引擎技术重视不够，这些在一
定程度上影响了我们在搜索引擎领域的纵深研究。可喜的是，在最近的国家高技术计划
（863）306主题中，设立了搜索引擎方面的研究内容，对搜索引擎关键技术研究和实用
系统开发进行支持，此举必将促进我国对搜索引擎技术的研究和开发，尽快赶上和超过
国际先进水平。
（本文联系人：刘建国 lguo@csnetlib.pku.edu.cn）
主要参考文献：
1． Steve Lawrence, C. Lee Giles, Accessibility of Information on the Web, N
ature, Vol 400, 8 Jul 1999
2． Steve Lawrence, C. Lee Giles, Searching the World Wide Web, Science 280,
  98-100(1998)
3． Venkat N. Gudivada, Vijay V. Raghavan, William I. Grosky, Rajesh Kasanag
ottu, Information Retrieval on the World Wide Web, Internet Computing, Septe
mber-Octobor 1997
4． Susan Feldman, Search Engines: The 1999 Conference, Information Today, V
olume 16, Number 6, June 1999
5． http://searchenginewatch.com/
1． 周利民，刘建国，陈葆珏，“天网：一个中英文环球网搜索引擎“，第8卷（增刊）
，《软件学报》，1998

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]