1、Web搜索引擎的基本要求
 
搜索引擎是一个网络应用软件系统，如下图所示，对它有如下基本要求。 
 能够接受用户通过浏览器提交的查询词或者短语，记作q，例如“大数据”，“Spark”等等。 
 在一个可以接受的时间内返回一个和该用户查询匹配的网页信息列表，记作L。这个列表的每一条目至少包含三个元素（标题，网址链接，摘要）。 
 示意图： 
 
 
“可以接受的时间”，也就是响应时间，这个时间不能太长，通常也就在“秒”这个量级。这是衡量搜索引擎可用性的一个基本指标。 
 更进一步的，这样的响应时间要求不仅要能满足单个用户查询，而且要能在系统设计负载的情况下满足所有的用户。也就是说，系统应该在额定吞吐率的情况下保证秒级响应时间。
 
“匹配”，指的是网页中以某种形式包含有q的内容，最简单最常见的形式就是q在其中直接出现。（当然，如果一个搜索引擎就是以百分之百满足这种简单的包含关系为目标，即使实现了也并不意味着达到了最好的效果。）
 
“列表”，就是一种序列（rank）。大多数情况下，L特别长，例如上万条数目等。这不仅是由于Web上的信息量大，也由于搜索引擎的查询方式简单。简单，意味着抽象；抽象，意味着有更多的具体事物可能是它的体现。 
 有分析统计表明，用户平均察看返回结果不超过2页。 
 现代大规模高质量搜索引擎一般采用下图三段式的工作流程，即：网页搜集、预处理和查询服务：
 
 
 
2、网页搜集
 
大规模搜索引擎服务的基础应该是一批预先搜集好的网页，如何维护？
 
1）定期搜集，每次搜集替换上一次的内容，我们称之为“批量搜集”。由于每次都是重新来一次，对于大规模搜索引擎来说，每次搜集的时间通常会花几周。而由于这样做开销较大，通常两次搜集的间隔时间也不会很短。这样做的好处是系统实现比较简单，主要缺点是“时新性”（freshness）不高，还有重复搜集所带来的额外带宽的消耗。 
 
2）增量搜集，开始时搜集一批，往后只是： 
 （1）搜集新出现的网页 
 （2）搜集那些在上次搜集后有过改变的网页 
 （3）发现自从上次搜集后已经不再存在了的网页，并从库中删除。 
 这样的系统表现出来的信息时新性就会比较高，主要缺点是系统实现比较复杂；这种复杂还不仅在于搜集过程，而是还在于建索引的过程。 
 
 
搜集方式：
 
最常见的一种是所谓“爬取”：将Web上的网页集合看成是一个有向图，搜集过程从给定起始URL集合S开始，沿着网页中的链接，按照先深、先宽、或者某种别的策略遍历，不停的从S中移除URL，下载相应的网页，解析出网页中的超链接URL，看是否已经被访问过，将未访问过的那些URL加入集合S。整个过程可以形象地想象为一个蜘蛛（spider）在蜘蛛网（Web）上爬行（crawl）。一般真正的系统其实是多个“蜘蛛”同时在爬。 
 
另外一种可能的方式是在第一次全面网页搜集后，系统维护相应的URL集合S，往后的搜集直接基于这个集合。每搜到一个网页，如果它发生变化并含有新的URL，则将它们对应的网页也抓回来，并将这些新URL也放到集合S中；如果S中某个URL对应的网页不存在了，则将它从S中删除。这种方式也可以看成是一种极端的先宽搜索，即第一层是一个很大的集合，往下最多只延伸一层。 
 
还有一种方法是让网站拥有者主动向搜索引擎提交它们的网址，系统在一定时间内定向向那些网站派出“蜘蛛”程序，扫描该网站的所有网页并将有关信息存入数据库中。大型商业搜索引擎一般都提供这种功能。 
 
 
3、预处理
 
一个合适的数据结构是查询子系统工作的核心和关键。这里只是指出：现行最有效的数据结构是“倒排文件”（inverted file）；倒排文件是用文档中所含关键词作为索引，文档作为索引目标的一种结构。 
 下面讨论从网页集合形成这样的倒排文件过程中的几个主要问题，即我们所说的 “预处理”。主要包括四个方面，关键词的提取，“镜像网页”（网页的内容完全相同，未加任何修改）或“转载网页”（near-replicas，主题内容基本相同但可能有一些额外的编辑信息等，转载网页也称为“近似镜像网页”）的消除，链接分析和网页重要程度的计算。 
 
 
1、关键词的提取 
 
随便取一篇网页的源文件，我们可以看到其中的情况纷乱繁杂。除了我们从浏览器中能够正常看到的文字内容外，还有大量的HTML标记。根据天网统计，网页文档源文件的大小（字节量）通常大约是其中内容大小的4倍。另外，由于HTML文档产生来源的多样性，许多网页在内容上比较随意，不仅文字不讲究规范、完整，而且还可能包含许多和主要内容无关的信息。
 
于是，作为预处理阶段的一个基本任务，就是要提取出网页源文件的内容部分所含的关键词。
 
对于中文来说，就是要根据一个词典Σ，用一个所谓“切词软件”，从网页文字中切出Σ所含的词语来。之后，一篇网页主要就由一组词来近似代表了，p = {t1, t2, …, tn}。 
 一般来讲，我们可能得到很多词，同一个词可能在一篇网页中多次出现。从效果(effectiveness)和效率（efficiency）考虑，不应该让所有的词都出现在网页的表示中，要去掉诸如“的”，“在”等没有内容指示意义的词，称为“停用词”(stop word)。
 
 
2、重复或转载网页的消除 
 
我们看到Web上的信息存在大量的重复现象。 
 例如，一条新闻总是会有十多个不同的URL也给出相同或者基本相似的内容。这种现象对于广大的网民来说是有正面意义的，因为有了更多的信息访问机会。但对于搜索引擎来说，则主要是负面的；它不仅在搜集网页时要消耗机器时间和网络带宽资源，而且如果在查询结果中出现，无意义地消耗了计算机显示屏资源，也会引来用户的抱怨，“这么多重复的，给我一个就够了”。
 
因此，消除内容重复或主题内容重复的网页是预处理阶段的一个重要任务。 
 
 
3、链接分析 
 前面提到，大量的HTML标记既给网页的预处理造成了一些麻烦，也带来了一些新的机遇。
 
HTML文档中所含的指向其他文档的链接信息是人们近几年来特别关注的对象，认为它们不仅给出了网页之间的关系，而且还对判断网页的内容有很重要的作用。 
 
 
4、 网页重要程度的计算 
 搜索引擎返回给用户的，是一个和用户查询相关的结果列表。列表中条目的顺序是很重要的一个问题。
 
如何讲一篇网页比另外一篇网页重要？
 
人们参照科技文献重要性的评估方式，核心想法就是“被引用多的就是重要的”。“引用”这个概念恰好可以通过HTML超链在网页之间体现得非常好。 
 除此以外，人们还注意到网页和文献的不同特点，即一些网页主要是大量对外的链接，其本身基本没有一个明确的主题内容，而另外有些网页则被大量的其他网页链接。从某种意义上讲，这形成了一种对偶的关系，这种关系使得人们可以在网页上建立另外一种重要性指标。这些指标有的可以在预处理阶段计算，有的则要在查询阶段计算，但都是作为在查询服务阶段最终形成结果排序的部分参数。 
 
 
4、查询服务
 
从一个原始网页集合S开始，预处理过程得到的是对S的一个子集的元素的某种内部表示，这种表示构成了查询服务的直接基础。
 
对每个元素来说，这种表示至少包含如下几个方面： 
 
 原始网页文档 
  URL和标题 
  编号 
  所含的重要关键词的集合（以及它们在文档中出现的位置信息） 
  其他一些指标（例如重要程度，分类代码等） 
 
而系统关键词总体的集合和文档的编号一起构成了一个倒排文件结构，使得一旦得到一个关键词输入，系统能迅速给出相关文档编号的集合输出。 
 然而，用户通过搜索引擎看到的不是一个“集合”，而是一个“列表”。
 
如何从集合生成一个列表，是服务子系统的主要工作。
 
对服务子系统的要求和其工作原理，主要有三个方面： 
 
1、查询方式和匹配
 
查询方式指的是系统允许用户提交查询的形式。考虑到各种用户的不同背景和不同的信息需求，不可能有一种普适的方式。一般认为，对于普通网络用户来说，最自然的方式就是“要什么就输入什么”。
 
用一个词或者短语来直接表达信息需求，希望网页中含有该词或者该短语中的词，依然是主流的搜索引擎查询模式。 
 这不仅是因为它的确代表了大多数的情况，还因为它比较容易实现。这样，一般来讲，系统面对的是查询短语。就英文来说，它是一个词的序列；就中文来说，它是包含若干个词的一段文字。 
 一般地，我们用q0表示用户提交的原始查询，例如，q0 =“网络与分布式系统实验室”。它首先需要被“切词”（segment）或称“分词”，即把它分成一个词的序列。如上例，某分词算法将其分为“网络 与 分布式 系统 实验室”。然后需要删除那些没有查询意义或者几乎在每篇文档中都会出现的词（例如“的”），在本例中即为“与”。最后形成一个用于参加匹配的查询词表，q = {t1, t2, …, tm}，在本例中生成的词表就是q = {网络，分布式，系统，实验室}。
 
倒排文件就是用词来作为索引的一个数据结构，显然，上例q中的词必须是包含在倒排文件词表中才有意义。有了这样的q，它的每一个元素都对应倒排文件中的一个倒排表（文档编号的集合），记作L(ti)，它们的交集即为对应查询的结果文档集合，从而实现了查询和文档的匹配。
 
上述过程的基本假设是一般情况：用户是希望网页包含所输入查询文字的。 
 
 
2、 结果排序 
 用户查询的这个集合的元素需要以一定的形式通过计算机显示屏呈现给用户。就目前的技术情况看，列表是最常见的形式。
 
给定一个查询结果集合，R={r1, r2, …, rn}，所谓列表，就是按照某种评价方式，确定出R中元素的一个顺序，让这些元素以这种顺序呈现出来。笼统地讲，ri和q的相关性（relevance）是形成这种顺序的基本因素。
 
为了形成一个合适的顺序，在搜索引擎出现的早期人们采用了传统信息检索领域很成熟的基于词汇出现频度的方法。大致上讲就是一篇文档中包含的查询（q）中的那些词越多，则该文档就应该排在越前面；再精细一些的考虑则是若一个词在越多的文档中有出现，则该词用于区分文档相关性的作用就越小。这样一种思路不仅有一定直觉上的道理，而且在倒排文件数据结构上很容易实现。因为，当我们通过前述关键词的提取过程，形成一篇文档的关键词集合，p = {t1, t2, …, tn}的时候，很容易同时得到每一个ti在该文档中出现的次数，即词频，而倒排文件中每个倒排表的长度则对应着一个词所涉及的文档的篇数，即文档频率。 
 然而，由于网页编写的自发性、随意性较强，仅仅针对词的出现来决定文档的顺序，在Web上做信息检索表现出明显的缺点，需要有其他技术的补充。
 
这方面最重要的成果就是PageRank。通过在预处理阶段为每篇网页形成一个独立于查询词（也就和网页内容无关）的重要性指标，将它和查询过程中形成的相关性指标结合形成一个最终的排序，是目前搜索引擎给出查询结果排序的主要方法。 
 
 
3、 文档摘要 
 搜索引擎给出的结果是一个有序的条目列表，每一个条目有三个基本的元素：标题，网址和摘要。
 
其中的摘要需要从网页正文中生成。 
 但相关的技术用到网络搜索引擎来有两个基本困难。一是网页的写作通常不规范，文字比较随意，因此从语言理解的角度难以做好；二是复杂的语言理解算法耗时太多，不适应搜索引擎要高效处理海量网页信息的需求。
 
根据查询词在文档中的位置，提取出周围的文字来，在显示时将查询词标亮。这是目前大多数搜索引擎采用的方式。为了保证查询的效率，需要在预处理阶段分词的时候记住每个关键词在文档中出现的位置。 
 
 
5、体系结构
 
上述工作原理的基础上，作为一个网络应用软件，我们可以勾画出搜索引擎的体系结构： 
 
 
上图中“控制器”的作用： 
 网页的搜集，如果是为了向大规模搜索引擎稳定地提供网页数据，通常需要每天搜集上百万网页，而且是持续进行，情况则要复杂许多，核心是要综合解决效率、质量和“礼貌”的问题。这就是“控制器”的作用。 
 
所谓效率，在这里就是如何利用尽量少的资源（计算机设备、网络带宽、时间）来完成预定的网页搜集量。 
 所谓质量问题，指的是在有限的时间，搜集有限的网页，希望它们尽量是比较“重要”的网页，或者说不要漏掉那些很重要的网页。 
 礼貌，即是说搜索引擎需要和网站“和睦相处”，不要频繁抓取过多，会被认为是黑客攻击。
 
 
知识来源：搜索引擎教材 李晓明等著

摘要

 

       随着网络与通信技术的迅速发展，web信息爆炸性的增长，已经成为一个巨大的海量信息空间。如何快速、准确、方便的从如此庞大的信息库中获取自己需要的信息，是互联网用户面临的一个重要问题。Web搜索引擎能为用户提供一种查找所需资源的服务，已经成为互联网上仅次于电子邮件的第二大服务。本文首先介绍了搜索引擎的原理和实现技术。然后讨论了搜索引擎技术发展最新前沿技术。最后，结合笔者在这方面的研究，给出了搜索引擎近期的发展方向。
关键词
Web，搜索引擎，网络技术
一.  导论
随着网络技术的应用与发展，互连网已经成为信息的重要来源地。到1999年底，已经至少有1，600万台主机接入互连网，互联网上网页总数已达到10多亿页，并且以每月近千万的数目递增[1]。搜索引擎以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导航的目的[2]，互联网用户使用网络获取信息过程中，搜索引擎也成为必不可少的工具。调查表明，当前的所有互连网应用中，网络信息搜索是仅次于电子邮件的第二大应用，而这些搜索绝大多数是专门的，高度复杂的搜索引擎实现的。
按照信息搜集方法和服务提供方式的不同，搜索引擎系统可以分为三大类：目录式搜索引擎，以人工方式或半自动方式搜集信息，由编辑员查看信息之后，人工形成信息摘要，并将信息置于事先确定的分类框架中，由于web信息的海量性和人工处理能力、经济代价的限制，这类搜索引擎信息的即时性和全面性难以保证它的优秀代表是Yahoo[3]等；机器人搜索引擎，由一个称为蜘蛛（Spider）的机器人程序以某种策略自动地在互联网中搜集和发现信息，由索引器为搜集到的信息建立索引，由检索器根据用户的查询输入检索索引库，并将查询结果返回给用户，这类搜索引擎实现较为复杂，但能很好的实现信息的全面获取和即时更新，它的优秀代表是google[4]等,后文如非特别说明，都指这类搜索引擎；元搜索引擎，这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处理后，作为自己的结果返回给用户，这类搜索引擎兼集多个搜索引擎的信息，并且加入新的排序和信息过滤，可以很好的提高用户满意度，它的优秀代表是vivisino[5]等。
本文组织如下：第二部分介绍了web搜索引擎的原理和实现技术；第三部分介绍了web搜索引擎的最新发展动态和前沿技术；第四部分给出了基本展望。最后给出了结论。
二.  web搜索引擎的原理、实现和评价指标
web搜索引擎的原理通常为：首先是用蜘蛛（Spider）进行全网搜索，自动抓取网页；然后将抓取的网页进行索引，同时也会记录与检索有关的属性，中文搜索引擎中还需要首先对中文进行分词；最后，接受用户查询请求，检索索引文件并按照各种参数进行复杂的计算，产生结果并返回给用户。
基于上面的原理，下面将简要介绍Web搜索引擎实现。
1.         利用网络蜘蛛获取网络资源。
这是一种半自动化的资源（由于此时尚未对资源进行分析和理解，不能成为信息而仅是资源）获取方式。所谓半自动化，是指搜索器需要人工指定起始网络资源url（Uniform Resource Locator），然后获取该url所指向的网络资源，并分析该资源所指向的其他资源并获取。其基本流程图如下：

图1,基本搜索器流程图
网络蜘蛛访问资源的过程，是对互联网上信息遍历的过程。在实际的蜘蛛程序中，为了保证信息收集的全面性，及时性，还有多个蜘蛛程序的分工和合作问题，往往有复杂的控制机制。如google的在利用蜘蛛程序获取网络资源时，是由一个认为管理程序负责任务的分配和结果的处理，多个分布式的蜘蛛程序从管理程序活动任务，然后将获取的资源作为结果返回，并从新获得任务[6]。
2.         利用索引器从搜索器获取的资源中抽取信息，并建立利于检索的索引表：
当用网络蜘蛛获取资源后后，需要对这些进行加工过滤，去掉网控制代码及无用信息，提取出有用的信息，并把信息用一定的模型表示，使查询结果更为准确。其中信息的表示模型一般有布尔模型，向量模型，概率模型和神经网络模型等[7]。Web上的信息一般表现为网页，对每个网页，须生成一个摘要，此摘要将显示在查询结果的页面中，告诉查询用户各网页的内容概要。模型化的信息将存放在临时数据库中，由于web数据的数据量极为庞大，为了提高检索效率，须按照一定规则建立索引。不同搜索引擎在建立索引时会考虑不同的选项，如是否建立全文索引，是否过滤无用词汇，是否使用meta信息等。索引的建立包括：分析过程，处理文档中可能的错误；文档索引，完成分析的文档被编码进存储桶，有些搜索引擎还会使用并行索引；排序，将存储桶按照一定的规则排序，生产全文存储桶。最终形成的索引一般按照倒排文件的格式存放。
3.         检索及用户交互：
前面两部分属于搜索引擎的后台支持。本部分在前面信息索引库的基础上，接受用户查询请求，并到索引库检索相关内容，返回给用户。这部分的主要内容包括：用户查询（query）理解，即最大可能贴近的理解用户通过查询串想要表达的查询目的，并将用户查询转换化为后台检索使用的信息模型；根据用户查询的检索模型，在索引库中检索出结果集；结果排序：通过特定的排序算法，对检索结果集进行排序。现在用的的排序因素一般有查询相关度，google发明的pagerank计术，baidu的竞价技术等。由于web数据的海量性和用户初始查询的模糊性，检索结果集一般很大，而用户一边不会有足够的耐性逐个查看所有的结果，所以怎样设计结果集的排序算法，把用户感兴趣的结果排在前面就十分重要。
搜索引擎的评价指标有响应时间、查全率、查准率和用户满意度等。其中响应时间是从用户提交查询请求到搜索引擎给出查询结果的时间间隔，响应时间必须在用户可以接受的范围之内。查全率是指查询结果集信息的完备性。查准率是指查询结果集中符合用户要求的数目与结果总数之比。用户满意度是一个难以量化的概念，除了搜索引擎本身的服务质量外，它还和用户群体，网络环境有关系。在搜索引擎可以控制的范围内，其核心是搜索结果的排序，即前文提到的如何把最合适的结果排到前面。
三.  web搜索引擎的最新动态
当前，搜索引擎技术已经趋于成数，用户满意度也保持在一个可以接受的水平。在信息搜集技术，索引建立技术，检索技术和结果集排序技术方面，最近几年，除了google创造性的提出pagerank技术，并把他用于结果排序外，基本没有什么突破性的进展。而搜索引擎的研究与信息集成逐渐融合，在这方面的研究主要集中在两个方面：查询扩展（query expansion）和结果集的动态分类。
1．  查询扩展：
由于用户使用搜索引擎查找信息时，往往不能用搜索引擎提供的标准准确的表述想要查找的东西，从而在基于用户查询请求到索引库检索前，需要进行查询扩展（query expansion）。查询扩展包括两个步骤：用新的关键词扩展初始查询串；对扩展后查询串里的关键词从新进行权重分配。查询扩展的方法分为三类：基于用户注册兴趣的方式；基于用户对结果集操作反馈信息的方式[7]；基于搜索结果文档集全局信息的方式[8]。这些方法分别通过不同的途径扩展用户初始查询，以期提高查询结果的用户贴近度。用户兴趣注册的方式最准确和易于实现，但用户须先注册，而用户是否认可和信任这种方式还未知；用户反馈信息挖掘的方式中，用户不需任何额外的操作，但搜索引擎的工作量会更大，挖掘的准确度也难以控制，而挖掘本身也涉及用户隐私许可问题；基于搜索结果文档集全局信息的方式中，目前已经有很好的实现，但由于不是针对特定的用户进行，而搜索引擎最需要的是实现个性化的搜索，所以对搜索结果的用户贴近度没有直接的帮助。
2．  搜身结果的动态分类：
由于结果集通常十分庞大，因而如何组织结果集展现形式，方便用户快速的找到需要的信息就成为一个十分关键的问题。虽然通过改进页面排序算法，可以尽量使“重要”的页面出现在返回结果的前面，但由于用户职业，兴趣，年龄等各方面的差异，很难让所有的用户都接受服务商给出的重要性顺序。另外，统计显示，用户一般不会在结果集中向后翻超过五页。所以将查询结果以一定的类别层次组织，让用户能方便的选择查看类别，可以很好的缩小结果集，从而使用户能更快的查找信息。
目前这方面研究的主要要内容包括，怎样确定类别层次？怎样确定文章所属的类别？现有的解决方式大致可以分为两种：(a)根据经验或一定的计算模型，事先确定出静态的类别层次，让后通过网页内容的语义分析确定其所属类别。它面临的主要问题是：由于互连网用户地域，职业，宗教的，教育程度的不可预知性，很难确定出让所有用户的接受的分类层次体系；由于类别层次是静态的，所以对文章的归类可避免会出现限制，使某些网页没有合适的类别可放；另外，目前基于自然语言理解的语义分析技术准确度不高，系统消耗过大，由于网页数量的海量性质，所以每个网页都需要很高的处理消耗是不能接受的。(b)对查询结果集进行动态(on-the-fly)聚类，即在检索结果集和结果集展现之间增加一步，先对结果集安一定的相似度计算算法进行动态聚类，然后将结果集安聚类的结果进行组织，用户可以选择动态生产的聚类类别以缩小结果集，从而快速的找到需要的信息。这种方式简便灵活，且易于实现。但动态生成的类别不能很好的构成体系，层次关系更是难以体现，所以怎样设计聚类算法，直接关系聚类结果的好坏。
四.  web搜索引擎的发展趋势浅谈
以当前信息技术发展的速度，任何人要预测技术的发展趋势，都只会贻笑大方。具体到web搜索引擎技术，笔者只能根据当前的研究成果和研究方向，就近期的可能发展，给出个人的见解。
当前搜索引擎服务提高的挑战主要来之两方面，一个是用户初始查询请求描述的不准却性，用户往往难以清楚的表达其信息需求。所以，当前以及今后一段时间内，对如何根据用户模糊的查询请求，较为准确、全面的理解用户的实际信息需求的研究，将是搜索引擎技术研究的一个重要方面。目前这方面的研究主要集中于查询结果文档的信息挖掘，这方面的努力已经取得很多的成果。另一方面，挖掘用户的个性化信息，将是一个能产生突破性成果的方法：根据用户的背景信息，如知识水平，专业方向，职业和兴趣等，将极大的促进用户初始查询理解的准确性和全面性。另外，对用户网络使用的日志分析，也能提供准确的用户网络行为，从而为用户信息需求分析提供重要依据。综上所述，对个性化搜索引擎的实现的研究，将成为近段时间研究的重点和突破点。
搜索引擎服务质量提高的另一个挑战是，查询结果集过于庞大，用户往往不会看到位于结果集后部的信息。这方面目前已经基本确定的解决方案是，根据分类体系组织结果集，通过类别选择缩小结果范围。它的实现难点是分类体系的确定和最终页面归属类别的确定。目前的研究，主要是基于搜索引擎提供方对搜集到的信息的理解，限于当前自然语言理解准确度较低，开销较大，这方面的研究难以有更大的突破。而另外的选择是，让信息发布者自己提供信息的类别，用统一的规范描述信息的类别信息和语义信息。搜索引擎只需获取这些信息即可，无疑，这种方式得出的类别和语义信息都是最准确得。例如，当前一般网站都建有导航栏，网站内容安导航栏所指得类别层次组织，从而可以把导航信息作为类别层次，各导航项只想得最终页面归属于该类别下。笔者目前研究的重点就是如何提取网站栏目信息，如何把网站按栏目划分范围，从而把栏目和范围对应，把该范围内的所有内容规类到对应栏目项所指的类别。将来，如果能让所有信息发布者规范的描述类别和语义信息，这方面的研究必将发上飞跃。
从上面的论述，不难看出，今后一段时间，搜索引擎技术的研究将主要集中在如何提供个性化服务[9]，如何提供基于信息发布者提供的信息类别及语义理解两方面。
五.  结论
本文介绍了web搜索引擎的原理和实现技术，讨论当前web搜索引擎研究的最新动态，并论述了近期web搜索引擎发展的方向。
参考文献：
[1]   《world wide web search technoligies》Shi Nansi，Idea Group Publish
[2]   《搜索引擎技术及趋势》李晓明，刘建国。2003.6
[3]  http://www.yahoo.com。
[4]   http://www.google.com。
[5]   http://www.vivisino.com。
[6] 《搜索引擎与信息获取技术》p107。徐宝文，张卫风；清华大学出版社。
[6]   http://www.searchenginewatch.com。
[7]   Conceptual retrieval based on feature clustering of documents。Youjin Chang，Ikkyu Cho。
[8]   Modern information retrieval, p117。Addison Wesley。1999
[9]   Microsoft Unveils its New Search Engine -At Last, Chris Sherman，2004.11

 摘要
随着网络与通信技术的迅速发展，web信息爆炸性的增长，已经成为一个巨大的海量信息空间。如何快速、准确、方便的从如此庞大的信息库中获取自己需要的信息，是互联网用户面临的一个重要问题。Web搜索引擎能为用户提供一种查找所需资源的服务，已经成为互联网上仅次于电子邮件的第二大服务。本文首先介绍了搜索引擎的原理和实现技术。然后讨论了搜索引擎技术发展最新前沿技术。最后，结合笔者在这方面的研究，给出了搜索引擎近期的发展方向。
关键词
Web，搜索引擎，网络技术
一.  导论
随着网络技术的应用与发展，互连网已经成为信息的重要来源地。到1999年底，已经至少有1，600万台主机接入互连网，互联网上网页总数已达到10多亿页，并且以每月近千万的数目递增[1]。搜索引擎以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导航的目的[2]，互联网用户使用网络获取信息过程中，搜索引擎也成为必不可少的工具。调查表明，当前的所有互连网应用中，网络信息搜索是仅次于电子邮件的第二大应用，而这些搜索绝大多数是专门的，高度复杂的搜索引擎实现的。
按照信息搜集方法和服务提供方式的不同，搜索引擎系统可以分为三大类：目录式搜索引擎，以人工方式或半自动方式搜集信息，由编辑员查看信息之后，人工形成信息摘要，并将信息置于事先确定的分类框架中，由于web信息的海量性和人工处理能力、经济代价的限制，这类搜索引擎信息的即时性和全面性难以保证它的优秀代表是Yahoo[3]等；机器人搜索引擎，由一个称为蜘蛛（Spider）的机器人程序以某种策略自动地在互联网中搜集和发现信息，由索引器为搜集到的信息建立索引，由检索器根据用户的查询输入检索索引库，并将查询结果返回给用户，这类搜索引擎实现较为复杂，但能很好的实现信息的全面获取和即时更新，它的优秀代表是google[4]等,后文如非特别说明，都指这类搜索引擎；元搜索引擎，这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处理后，作为自己的结果返回给用户，这类搜索引擎兼集多个搜索引擎的信息，并且加入新的排序和信息过滤，可以很好的提高用户满意度，它的优秀代表是vivisino[5]等。
本文组织如下：第二部分介绍了web搜索引擎的原理和实现技术；第三部分介绍了web搜索引擎的最新发展动态和前沿技术；第四部分给出了基本展望。最后给出了结论。
二.  web搜索引擎的原理、实现和评价指标
web搜索引擎的原理通常为：首先是用蜘蛛（Spider）进行全网搜索，自动抓取网页；然后将抓取的网页进行索引，同时也会记录与检索有关的属性，中文搜索引擎中还需要首先对中文进行分词；最后，接受用户查询请求，检索索引文件并按照各种参数进行复杂的计算，产生结果并返回给用户。
基于上面的原理，下面将简要介绍Web搜索引擎实现。
1.         利用网络蜘蛛获取网络资源。
这是一种半自动化的资源（由于此时尚未对资源进行分析和理解，不能成为信息而仅是资源）获取方式。所谓半自动化，是指搜索器需要人工指定起始网络资源url（Uniform Resource Locator），然后获取该url所指向的网络资源，并分析该资源所指向的其他资源并获取。其基本流程图如下：

图1,基本搜索器流程图
网络蜘蛛访问资源的过程，是对互联网上信息遍历的过程。在实际的蜘蛛程序中，为了保证信息收集的全面性，及时性，还有多个蜘蛛程序的分工和合作问题，往往有复杂的控制机制。如google的在利用蜘蛛程序获取网络资源时，是由一个认为管理程序负责任务的分配和结果的处理，多个分布式的蜘蛛程序从管理程序活动任务，然后将获取的资源作为结果返回，并从新获得任务[6]。
2.         利用索引器从搜索器获取的资源中抽取信息，并建立利于检索的索引表：
当用网络蜘蛛获取资源后后，需要对这些进行加工过滤，去掉网控制代码及无用信息，提取出有用的信息，并把信息用一定的模型表示，使查询结果更为准确。其中信息的表示模型一般有布尔模型，向量模型，概率模型和神经网络模型等[7]。Web上的信息一般表现为网页，对每个网页，须生成一个摘要，此摘要将显示在查询结果的页面中，告诉查询用户各网页的内容概要。模型化的信息将存放在临时数据库中，由于web数据的数据量极为庞大，为了提高检索效率，须按照一定规则建立索引。不同搜索引擎在建立索引时会考虑不同的选项，如是否建立全文索引，是否过滤无用词汇，是否使用meta信息等。索引的建立包括：分析过程，处理文档中可能的错误；文档索引，完成分析的文档被编码进存储桶，有些搜索引擎还会使用并行索引；排序，将存储桶按照一定的规则排序，生产全文存储桶。最终形成的索引一般按照倒排文件的格式存放。
3.         检索及用户交互：
前面两部分属于搜索引擎的后台支持。本部分在前面信息索引库的基础上，接受用户查询请求，并到索引库检索相关内容，返回给用户。这部分的主要内容包括：用户查询（query）理解，即最大可能贴近的理解用户通过查询串想要表达的查询目的，并将用户查询转换化为后台检索使用的信息模型；根据用户查询的检索模型，在索引库中检索出结果集；结果排序：通过特定的排序算法，对检索结果集进行排序。现在用的的排序因素一般有查询相关度，google发明的pagerank计术，baidu的竞价技术等。由于web数据的海量性和用户初始查询的模糊性，检索结果集一般很大，而用户一边不会有足够的耐性逐个查看所有的结果，所以怎样设计结果集的排序算法，把用户感兴趣的结果排在前面就十分重要。
搜索引擎的评价指标有响应时间、查全率、查准率和用户满意度等。其中响应时间是从用户提交查询请求到搜索引擎给出查询结果的时间间隔，响应时间必须在用户可以接受的范围之内。查全率是指查询结果集信息的完备性。查准率是指查询结果集中符合用户要求的数目与结果总数之比。用户满意度是一个难以量化的概念，除了搜索引擎本身的服务质量外，它还和用户群体，网络环境有关系。在搜索引擎可以控制的范围内，其核心是搜索结果的排序，即前文提到的如何把最合适的结果排到前面。
三.  web搜索引擎的最新动态
当前，搜索引擎技术已经趋于成数，用户满意度也保持在一个可以接受的水平。在信息搜集技术，索引建立技术，检索技术和结果集排序技术方面，最近几年，除了google创造性的提出pagerank技术，并把他用于结果排序外，基本没有什么突破性的进展。而搜索引擎的研究与信息集成逐渐融合，在这方面的研究主要集中在两个方面：查询扩展（query expansion）和结果集的动态分类。
1．  查询扩展：
由于用户使用搜索引擎查找信息时，往往不能用搜索引擎提供的标准准确的表述想要查找的东西，从而在基于用户查询请求到索引库检索前，需要进行查询扩展（query expansion）。查询扩展包括两个步骤：用新的关键词扩展初始查询串；对扩展后查询串里的关键词从新进行权重分配。查询扩展的方法分为三类：基于用户注册兴趣的方式；基于用户对结果集操作反馈信息的方式[7]；基于搜索结果文档集全局信息的方式[8]。这些方法分别通过不同的途径扩展用户初始查询，以期提高查询结果的用户贴近度。用户兴趣注册的方式最准确和易于实现，但用户须先注册，而用户是否认可和信任这种方式还未知；用户反馈信息挖掘的方式中，用户不需任何额外的操作，但搜索引擎的工作量会更大，挖掘的准确度也难以控制，而挖掘本身也涉及用户隐私许可问题；基于搜索结果文档集全局信息的方式中，目前已经有很好的实现，但由于不是针对特定的用户进行，而搜索引擎最需要的是实现个性化的搜索，所以对搜索结果的用户贴近度没有直接的帮助。
2．  搜身结果的动态分类：
由于结果集通常十分庞大，因而如何组织结果集展现形式，方便用户快速的找到需要的信息就成为一个十分关键的问题。虽然通过改进页面排序算法，可以尽量使“重要”的页面出现在返回结果的前面，但由于用户职业，兴趣，年龄等各方面的差异，很难让所有的用户都接受服务商给出的重要性顺序。另外，统计显示，用户一般不会在结果集中向后翻超过五页。所以将查询结果以一定的类别层次组织，让用户能方便的选择查看类别，可以很好的缩小结果集，从而使用户能更快的查找信息。
目前这方面研究的主要要内容包括，怎样确定类别层次？怎样确定文章所属的类别？现有的解决方式大致可以分为两种：(a)根据经验或一定的计算模型，事先确定出静态的类别层次，让后通过网页内容的语义分析确定其所属类别。它面临的主要问题是：由于互连网用户地域，职业，宗教的，教育程度的不可预知性，很难确定出让所有用户的接受的分类层次体系；由于类别层次是静态的，所以对文章的归类可避免会出现限制，使某些网页没有合适的类别可放；另外，目前基于自然语言理解的语义分析技术准确度不高，系统消耗过大，由于网页数量的海量性质，所以每个网页都需要很高的处理消耗是不能接受的。(b)对查询结果集进行动态(on-the-fly)聚类，即在检索结果集和结果集展现之间增加一步，先对结果集安一定的相似度计算算法进行动态聚类，然后将结果集安聚类的结果进行组织，用户可以选择动态生产的聚类类别以缩小结果集，从而快速的找到需要的信息。这种方式简便灵活，且易于实现。但动态生成的类别不能很好的构成体系，层次关系更是难以体现，所以怎样设计聚类算法，直接关系聚类结果的好坏。
四.  web搜索引擎的发展趋势浅谈
以当前信息技术发展的速度，任何人要预测技术的发展趋势，都只会贻笑大方。具体到web搜索引擎技术，笔者只能根据当前的研究成果和研究方向，就近期的可能发展，给出个人的见解。
当前搜索引擎服务提高的挑战主要来之两方面，一个是用户初始查询请求描述的不准却性，用户往往难以清楚的表达其信息需求。所以，当前以及今后一段时间内，对如何根据用户模糊的查询请求，较为准确、全面的理解用户的实际信息需求的研究，将是搜索引擎技术研究的一个重要方面。目前这方面的研究主要集中于查询结果文档的信息挖掘，这方面的努力已经取得很多的成果。另一方面，挖掘用户的个性化信息，将是一个能产生突破性成果的方法：根据用户的背景信息，如知识水平，专业方向，职业和兴趣等，将极大的促进用户初始查询理解的准确性和全面性。另外，对用户网络使用的日志分析，也能提供准确的用户网络行为，从而为用户信息需求分析提供重要依据。综上所述，对个性化搜索引擎的实现的研究，将成为近段时间研究的重点和突破点。
搜索引擎服务质量提高的另一个挑战是，查询结果集过于庞大，用户往往不会看到位于结果集后部的信息。这方面目前已经基本确定的解决方案是，根据分类体系组织结果集，通过类别选择缩小结果范围。它的实现难点是分类体系的确定和最终页面归属类别的确定。目前的研究，主要是基于搜索引擎提供方对搜集到的信息的理解，限于当前自然语言理解准确度较低，开销较大，这方面的研究难以有更大的突破。而另外的选择是，让信息发布者自己提供信息的类别，用统一的规范描述信息的类别信息和语义信息。搜索引擎只需获取这些信息即可，无疑，这种方式得出的类别和语义信息都是最准确得。例如，当前一般网站都建有导航栏，网站内容安导航栏所指得类别层次组织，从而可以把导航信息作为类别层次，各导航项只想得最终页面归属于该类别下。笔者目前研究的重点就是如何提取网站栏目信息，如何把网站按栏目划分范围，从而把栏目和范围对应，把该范围内的所有内容规类到对应栏目项所指的类别。将来，如果能让所有信息发布者规范的描述类别和语义信息，这方面的研究必将发上飞跃。
从上面的论述，不难看出，今后一段时间，搜索引擎技术的研究将主要集中在如何提供个性化服务[9]，如何提供基于信息发布者提供的信息类别及语义理解两方面。
五.  结论
本文介绍了web搜索引擎的原理和实现技术，讨论当前web搜索引擎研究的最新动态，并论述了近期web搜索引擎发展的方向。
参考文献：
[1]   《world wide web search technoligies》Shi Nansi，Idea Group Publish
[2]   《搜索引擎技术及趋势》李晓明，刘建国。2003.6
[3]  http://www.yahoo.com。
[4]   http://www.google.com。
[5]   http://www.vivisino.com。
[6] 《搜索引擎与信息获取技术》p107。徐宝文，张卫风；清华大学出版社。
[6]   http://www.searchenginewatch.com。
[7]   Conceptual retrieval based on feature clustering of documents。Youjin Chang，Ikkyu Cho。
[8]   Modern information retrieval, p117。Addison Wesley。1999
[9]   Microsoft Unveils its New Search Engine -At Last, Chris Sherman，2004.11

作者Blog：http://blog.csdn.net/hwalk/ 

简谈搜索引擎工作流程 
 


　
　互联网是一个宝库，搜索引擎是打开宝库的一把钥匙。然而，绝大多数网民在搜索引擎的相关知识及使用技巧上能力不足。国外的一次调查结果显示，约有71%的人对搜索的结果感到不同程度的失望。作为互联网的第二大服务，这种状况应该改变。 互联网的迅速发展，导致了网上信息的爆炸性增长。全球目前的网页超过20亿，每天新增加730万网页。要在如此浩瀚的信息海洋里寻找信息，就像“大海捞针”一样困难。搜索引擎正是为了解决这个“迷航”问题而出现的技术。 搜索引擎的工作包括如下三个过程：







1.在互联中发现、搜集网页信息；

2.对信息进行提取和组织建立索引库；

3.再由检索器根据用户输入的查询关字，在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并将查询结果返回给用户。







发现、搜集网页信息

需要有高性能的“网络蜘蛛”程序(Spider)去自动地在互联网中搜索信息。一个典型的网络蜘蛛工作的方式，是查看一个页面，并从中找到相关信息, 然后它再从该页面的所有链接中出发，继续寻找相关的信息，以此类推，直至穷尽。网络蜘蛛要求能够快速、全面。网络蜘蛛为实现其快速地浏览整个互联网，通常在技术上采用抢先式多线程技术实现在网上聚集信息。通过抢先式多线程的使用，你能索引一个基于URL链接的Web页面，启动一个新的线程跟随每个新的URL链接，索引一个新的URL起点。当然在服务器上所开的线程也不能无限膨胀，需要在服务器的正常运转和快速收集网页之间找一个平衡点。在算法上各个搜索引擎技术公司可能不尽相同，但目的都是快速浏览Web页和后续过程相配合。目前国内的搜索引擎技术公司中，比如百度公司的网络蜘蛛采用了可定制、高扩展性的调度算法使得搜索器能在极短的时间内收集到最大数量的互联网信息，并把所 获得的信息保存下来以备建立索引库和用户检索。







索引库的建立

关系到用户能否最迅速地找到最准确、最广泛的信息，同时索引库的建立也必须迅速，对网络蜘蛛抓来的网页信息极快地建立索引，保证信息的及时性。对网页采用基于网页内容分析和基于超链分析相结合的方法进行相关度评价，能够客观地对网页进行排序，从而极大限度地保证搜索出的结果与用户的查询串相一致。新浪搜索引擎对网站数据建立索引的过程中采取了按照关键词在网站标题、网站描述、网站URL等不同位置的出现或网站的质量等级等建立索引库，从而保证搜索出的结果与用户的查询串相一致。新浪搜索引擎在索引库建立的过程中，对所有数据采用多进程并行的方式，对新的信息采取增量式的方法建立索引库，从而保证能够迅速建立索引，使数据能够得到及时的更新。新浪搜索引擎在建立索引库的过程中还对用户搜索的查询串进行跟踪，并对查询频率高的查询串建立Cache页。







用户检索的过程

这是对前两个过程的检验，检验该搜索引擎能否给出最准确、最广泛的信息，检验该搜索引擎能否迅速地给出用户最想得到的信息。对于网站数据的检索，新浪搜索引擎采用Client/Server结构、多进程的方式在索引库中检索，大大减少了用户的等待时间，并且在用户查询高峰时服务器的负担不会过高（平均的检索时间在0.3秒左右）。对于网页信息的检索，作为国内众多门户网站的网页检索技术提供商的百度公司其搜索引擎运用了先进的多线程技术，采用高效的搜索算法和稳定的UNIX平台，因此可大大缩短对用户搜索请求的响应时间。作为慧聪I系列应用软件产品之一的I-Search2000采用的超大规模动态缓存技术，使一级响应的覆盖率达到75%以上，独有的自学习能力可自动将二级响应的覆盖率扩充到20%以上。