随着因特网的迅猛发展、WEB信息的增加，用户要在信息海洋里查找信息，就象大海捞针一样，搜索引擎技术恰好解决了这一难题（它可以为用户提供信息检索服务）。目前，搜索引擎技术正成为计算机工业界和学术界争相研究、开发的对象。 + _; ]0 W. b: `, N9 H) Y. `- V
搜索引擎（Search Engine）是随着WEB信息的迅速增加，从1995年开始逐渐发展起来的技术。据发表在《科学》杂志1999年7月的文章《WEB信息的可访问性》估计，全球目前的网页超过8亿，有效数据超过9T，并且仍以每4个月翻一番的速度增长。用户要在如此浩瀚的信息海洋里寻找信息，必然会“大海捞针”无功而返。
$ I7 k9 u$ T i4 H) i4 p0 Z 搜索引擎正是为了解决这个“迷航”问题而出现的技术。搜索引擎以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导航的目的。搜索引擎提供的导航服务已经成为互联网上非常重要的网络服务，搜索引擎站点也被美誉为“网络门户”。搜索引擎技术因而成为计算机工业界和学术界争相研究、开发的对象。本文旨在对搜索引擎的关键技术进行简单的介绍，以起到抛砖引玉的作用。
" f: U* y; ]7 R$ f8 Z4 l* T 一、分类
7 G% Z: q2 F/ y 按照信息搜集方法和服务提供方式的不同，搜索引擎系统可以分为三大类： 6 x2 Q4 k6 T6 h7 J1 P: O
1．目录式搜索引擎：以人工方式或半自动方式搜集信息，由编辑员查看信息之后，人工形成信息摘要，并将信息置于事先确定的分类框架中。信息大多面向网站，提供目录浏览服务和直接检索服务。该类搜索引擎因为加入了人的智能，所以信息准确、导航质量高，缺点是需要人工介入、维护量大、信息量少、信息更新不及时。这类搜索引擎的代表是：Yahoo、LookSmart、Open Directory、Go Guide等。
- u9 d) ~; |3 t' ^$ } 2．机器人搜索引擎：由一个称为蜘蛛（Spider）的机器人程序以某种策略自动地在互联网中搜集和发现信息，由索引器为搜集到的信息建立索引，由检索器根据用户的查询输入检索索引库，并将查询结果返回给用户。服务方式是面向网页的全文检索服务。该类搜索引擎的优点是信息量大、更新及时、毋需人工干预，缺点是返回信息过多，有很多无关信息，用户必须从结果中进行筛选。这类搜索引擎的代表是：AltaVista、Northern Light、Excite、Infoseek、Inktomi、FAST、Lycos、Google；国内代表为：“天网”、悠游、OpenFind等。
" K5 Z+ H/ n p$ v 3．元搜索引擎：这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处理后，作为自己的结果返回给用户。服务方式为面向网页的全文检索。7997单机游戏网这类搜索引擎的优点是返回结果的信息量更大、更全，缺点是不能够充分使用所使用搜索引擎的功能，用户需要做更多的筛选。这类搜索引擎的代表是WebCrawler、InfoMarket等。
5 p. F) J- {5 B& k) y 二、性能指标 ( G8 i/ _" T: e7 {
我们可以将WEB信息的搜索看作一个信息检索问题，即在由WEB网页组成的文档库中检索出与用户查询相关的文档。所以我们可以用衡量传统信息检索系统的性能参数-召回率（Recall）和精度（Pricision）衡量一个搜索引擎的性能。 ! U# D0 Q" y0 o# {' D
召回率是检索出的相关文档数和文档库中所有的相关文档数的比率，衡量的是检索系统（搜索引擎）的查全率；精度是检索出的相关文档数与检索出的文档总数的比率，衡量的是检索系统（搜索引擎）的查准率。对于一个检索系统来讲，召回率和精度不可能两全其美：召回率高时，精度低，精度高时，召回率低。所以常常用11种召回率下11种精度的平均值（即11点平均精度）来衡量一个检索系统的精度。对于搜索引擎系统来讲，因为没有一个搜索引擎系统能够搜集到所有的WEB网页，所以召回率很难计算。目前的搜索引擎系统都非常关心精度。
9 `6 P6 w/ ]6 X/ m7 K) x$ { 影响一个搜索引擎系统的性能有很多因素，最主要的是信息检索模型，包括文档和查询的表示方法、评价文档和用户查询相关性的匹配策略、查询结果的排序方法和用户进行相关度反馈的机制。
1 K9 Q, V6 `$ n/ {) T! a/ _ ~: S 三、主要技术 % n6 P6 _( e' N$ M6 |
一个搜索引擎由搜索器、索引器、检索器和用户接口等四个部分组成。 : R4 d7 m$ W" G* C" ^, t, q
1.搜索器 5 u# s: p& P$ O" b: o+ ]5 Y
搜索器的功能是在互联网中漫游，发现和搜集信息。它常常是一个计算机程序，日夜不停地运行。它要尽可能多、尽可能快地搜集各种类型的新信息，同时因为互联网上的信息更新很快，所以还要定期更新已经搜集过的旧信息，以避免死连接和无效连接。目前有两种搜集信息的策略： ( G* d1 e# a: a! s
● 从一个起始URL集合开始，顺着这些URL中的超链（Hyperlink），以宽度优先、深度优先或启发式方式循环地在互联网中发现信息。这些起始URL可以是任意的URL，但常常是一些非常流行、包含很多链接的站点（如Yahoo！）。 1 o$ |) O, n' V% M, _3 [& c
● 将Web空间按照域名、IP地址或国家域名划分，每个搜索器负责一个子空间的穷尽搜索。 3 j9 Q# c$ x8 E' C" c, R0 a
搜索器搜集的信息类型多种多样，包括HTML、XML、Newsgroup文章、FTP文件、字处理文档、多媒体信息。 ' A: K+ ]( _' T' v4 c
搜索器的实现常常用分布式、并行计算技术，以提高信息发现和更新的速度。商业搜索引擎的信息发现可以达到每天几百万网页。
8 E* B* O$ ]7 ?" C 2.索引器
2 w% j* t) K0 p+ S8 a& q0 t ` P 索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项，用于表示文档以及生成文档库的索引表。 $ m3 b; C" U/ ] B7 o+ f
索引项有客观索引项和内容索引项两种：客观项与文档的语意内容无关，如作者名、URL、更新时间、编码、长度、链接流行度（Link Popularity）等等；内容索引项是用来反映文档内容的，如关键词及其权重、短语、单字等等。内容索引项可以分为单索引项和多索引项（或称短语索引项）两种。单索引项对于英文来讲是英语单词，比较容易提取，因为单词之间有天然的分隔符（空格）；对于中文等连续书写的语言，必须进行词语的切分。 9 T+ ]) f5 m" r- Q; Z
在搜索引擎中，一般要给单索引项赋与一个权值，以表示该索引项对文档的区分度，同时用来计算查询结果的相关度。使用的方法一般有统计法、信息论法和概率法。短语索引项的提取方法有统计法、概率法和语言学法。 8 |8 l' v/ z# t
索引表一般使用某种形式的倒排表（Inversion List），即由索引项查找相应的文档。索引表也可能要记录索引项在文档中出现的位置，以便检索器计算索引项之间的相邻或接近关系（proximity）。
$ _$ f9 Z, H& H& ?4 {$ w+ c) E 索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实现即时索引（Instant Indexing），否则不能够跟上信息量急剧增加的速度。索引算法对索引器的性能（如大规模峰值查询时的响应速度）有很大的影响。一个搜索引擎的有效性在很大程度上取决于索引的质量。
* B' K$ h) W/ o. f6 M0 [+ ?0 V 3.检索器
8 c8 w" l9 t R1 I$ f! w: b; y 检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。http://www.7997.com
. |; v4 k$ e, q+ T- u) E6 v- N. M 检索器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合模型四种。
" O5 g4 L+ w4 f; G- d' ^: m. \0 @ 4.用户接口 ( Y+ _+ c% y" C' B3 W* a. b
用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。主要的目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、及时的信息。用户接口的设计和实现使用人机交互的理论和方法，以充分适应人类的思维习惯。 ' N Z) [+ \: H3 l( | V
用户输入接口可以分为简单接口和复杂接口两种。 & `4 N+ }$ }" ~2 R: a7 ?
简单接口只提供用户输入查询串的文本框；复杂接口可以让用户对查询进行限制，如逻辑运算（与、或、非； 、-）、相近关系（相邻、NEAR）、域名范围（如.edu、.com）、出现位置（如标题、内容）、信息时间、长度等等。目前一些公司和机构正在考虑制定查询选项的标准。
( c0 P* p/ h, a 四、未来动向
/ B$ D& t Q% T2 V s, x* M1 w: N 搜索引擎已成为一个新的研究、开发领域。因为它要用到信息检索、人工智能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理等多领域的理论和技术，所以具有综合性和挑战性。又由于搜索引擎有大量的用户，有很好的经济价值，所以引起了世界各国计算机科学界和信息产业界的高度关注，目前的研究、开发十分活跃，并出现了很多值得注意的动向。 & J( m+ {% p8 {
1.十分注意提高信息查询结果的精度，提高检索的有效性 8 R) M$ e% X8 Y7 p/ ]+ L3 o& W3 h3 y0 }" q
用户在搜索引擎上进行信息查询时，并不十分关注返回结果的多少，而是看结果是否和自己的需求吻合。对于一个查询，传统的搜索引擎动辄返回几十万、几百万篇文档，用户不得不在结果中筛选。解决查询结果过多的现象目前出现了几种方法：一是通过各种方法获得用户没有在查询语句中表达出来的真正用途，包括使用智能代理跟踪用户检索行为，分析用户模型；使用相关度反馈机制，使用户告诉搜索引擎哪些文档和自己的需求相关（及其相关的程度），哪些不相关，通过多次交互逐步求精。二是用正文分类（Text Categorization）技术将结果分类，使用可视化技术显示分类结构，用户可以只浏览自己感兴趣的类别。三是进行站点类聚或内容类聚，减少信息的总量。 1 G3 h5 P% b* d3 z& B
2.基于智能代理的信息过滤和个性化服务
9 Y/ c, f c5 Q3 P$ [. B0 } 信息智能代理是另外一种利用互联网信息的机制。它使用自动获得的领域模型（如Web知识、信息处理、与用户兴趣相关的信息资源、领域组织结构）、用户模型（如用户背景、兴趣、行为、风格）知识进行信息搜集、索引、过滤（包括兴趣过滤和不良信息过滤），并自动地将用户感兴趣的、对用户有用的信息提交给用户。智能代理具有不断学习、适应信息和用户兴趣动态变化的能力，从而提供个性化的服务。智能代理可以在用户端进行，也可以在服务器端运行。 ; E0 ]1 s. A0 c" b( ]
3.采用分布式体系结构提高系统规模和性能 ( t- m$ @: \1 R, ~* D6 a
搜索引擎的实现可以采用集中式体系结构和分布式体系结构，两种方法各有千秋。但当系统规模到达一定程度（如网页数达到亿级）时，必然要采用某种分布式方法，以提高系统性能。搜索引擎的各个组成部分，除了用户接口之外，都可以进行分布：搜索器可以在多台机器上相互合作、相互分工进行信息发现，以提高信息发现和更新速度；索引器可以将索引分布在不同的机器上，以减小索引对机器的要求；检索器可以在不同的机器上进行文档的并行检索，以提高检索的速度和性能。
' o4 c* |( f) }! C C 4.重视交叉语言检索的研究和开发
( |+ e5 ?9 W% p) r% S 交叉语言信息检索是指用户用母语提交查询，搜索引擎在多种语言的数据库中进行信息检索，返回能够回答用户问题的所有语言的文档。如果再加上机器翻译，返回结果可以用母语显示。该技术目前还处于初步研究阶段，主要的困难在于语言之间在表达方式和语义对应上的不确定性。但对于经济全球化、互联网跨越国界的今天，无疑具有很重要的意义。
; L) {- X! U1 P$ d 五、学术研究
! i0 y; r5 z6 t" g* P 目前搜索引擎领域的商业开发非常活跃，各大搜索引擎公司都在投巨资研制搜索引擎系统，同时也不断地涌现出新的具有鲜明特色的搜索引擎产品，搜索引擎已经成为信息领域的产业之一。在这种情况下，对搜索引擎技术相关领域的学术研究得到了大学和科研机构的重视。如Stanford大学在其数字图书馆项目中开发了Google搜索引擎，在Web信息的高效搜索、文档的相关度评价、大规模索引等方面作了深入的研究，取得了很好的成果。
1 B9 a' W& m6 @. @! t2 _: g NEC美国研究所的Steve Lawrence和C. Lee Giles 1998年和1999年连续两年在《自然》和《科学》杂志上撰文对搜索引擎技术的研究进行评述。著名的信息检索会议TREC也从1998年开始增加了Web Track课题，以考察Web文档与其它类型文档在检索性质上的不同之处，并将测试在大规模的Web库（如100G字节）上进行信息检索的算法性能。 - t( F7 S1 x: T+ J5 M- g9 @
由美国Infornotics公司主办的搜索引擎国际会议从1996年开始，每年举行一次，对搜索引擎技术进行总结、讨论和展望，参加者有著名的搜索引擎公司、大学和研究机构的学者，对搜索引擎技术起到了很好的推动作用。另外象IEEE主办的国际万维网会议、人机交互会议已有+ S/ y; I5 m+ E2 \
8 o' i: g ~' A7 i, D
|
