浅谈搜索引擎要涉及的一些知识要点

wz***

　　随着互联网的迅猛发展、WEB信息的增加，用户要在信息海洋里查找自己所需的信息，就象大海捞针一样，搜索引擎技术恰好解决了这一难题(它可以为用户提供信息检索服务)。搜索引擎是指互联网上专门提供检索服务的一类网站，这些站点的服务器通过网络搜索软件(例如网络搜索机器人)或网络登录等方式，将Intemet上大量网站的页面信息收集到本地，经过加工处理建立信息数据库和索引数据库，从而对用户提出的各种检索作出响应，提供用户所需的信息或相关指针。用户的检索途径主要包括自由词全文检索、关键词检索、分类检索及其他特殊信息的检索(如企业、人名、电话黄页等)。下面以网络搜索机器人为例来说明搜索引擎技术。

　　1.网络机器人技术

　　网络机器人(Robot)又被称作Spider、Worm或Random，核心目的是为获取Intemet上的信息。一般定义为“一个在网络上检索文件且自动跟踪该文件的超文本结构并循环检索被参照的所有文件的软件”。机器人利用主页中的超文本链接遍历WWW，通过U趾引用从一个HT2LIL文档爬行到另一个HTML文档。网上机器人收集到的信息可有多种用途，如建立索引、HIML文件合法性的验证、uRL链接点验证与确认、监控与获取更新信息、站点镜像等。机器人安在网上爬行，因此需要建立一个URL列表来记录访问的轨迹。它使用超文本，指向其他文档的URL是隐藏在文档中，需要从中分析提取URL，机器人一般都用于生成索引数据库。所有WWW的搜索程序都有如下的工作步骤：

　　(1)机器人从起始URL列表中取出URL并从网上读取其指向的内容。

　　(2)从每一个文档中提取某些信息(如关键字)并放入索引数据库中。

　　(3)从文档中提取指向其他文档的URL，并加入到URL列表中。

　　(4)重复上述3个步骤，直到再没有新的URL出现或超出了某些限制(时间或磁盘空间)。

　　(5)给索引数据库加上检索接口，向网上用户发布或提供给用户检索。

　　搜索算法一般有深度优先和广度优先两种基本的搜索策略。机器人以URL列表存取的方式决定搜索策略：先进先出，则形成广度优先搜索，当起始列表包含有大量的WWW服务器地址时，广度优先搜索将产生一个很好的初始结果，但很难深入到服务器中去;先进后出，则形成深度优先搜索，这样能产生较好的文档分布，更容易发现文档的结构，即找到最大数目的交叉引用。也可以采用遍历搜索的方法，就是直接将32位的IP地址变化，逐个搜索整个Intemet。

　　搜索引擎是一个技术含量很高的网络应用系统。它包括网络技术、数据库技术动标引技术、检索技术、自动分类技术，机器学习等人工智能技术。

　　2.索引技术

　　索引技术是搜索引擎的核心技术之一。搜索引擎要对所收集到的信息进行整理、分类、索引以产生索引库，而中文搜索引擎的核心是分词技术。分词技术是利用一定的规则和词库，切分出一个句子中的词，为自动索引做好准备。目前的索引多采用Non—clustered方法，该技术和语言文字的学问有很大的关系，具体有如下几点：

　　(1)存储语法库，和词汇库配合分出句子中的词汇;

　　(2)存储词汇库，要同时存储词汇的使用频率和常见搭配方式;

　　(3)词汇宽，应可划分为不同的专业库，以便于处理专业文献;

　　(4)对无法分词的句子，把每个字当作词来处理。

　　索引器生成从关键词到URL的关系索引表。索引表一般使用某种形式的倒排表(1nversionUst)，即由索引项查找相应的URL。索引表也要记录索引项在文档中出现的位置，以便检索器计算索引项之间的相邻关系或接近关系，并以特定的数据结构存储在硬盘上。

　　不同的搜索引擎系统可能采用不尽相同的标引方法。例如Webcrawler利用全文检索技术，对网页中每一个单词进行索引;Lycos只对页名、标题以及最重要的100个注释词等选择性词语进行索引;Infoseek则提供概念检索和词组检索，支持and、or、near、not等布尔运算。检索引擎的索引方法大致可分为自动索引、手工索引和用户登录三类。

　　3.检索器与结果处理技术

　　检索器的主要功能是根据用户输入的关键词在索引器形成的倒排表中进行检索，同时完成页面与检索之间的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。

　　通过搜索引擎获得的检索结果往往成百上千，为了得到有用的信息，常用的方法是按网页的重要性或相关性给网页评级，进行相关性排序。这里的相关度是指搜索关键字在文档中出现的额度。当额度越高时，则认为该文档的相关程度越高。能见度也是常用的衡量标准之一。一个网页的能见度是指该网页入口超级链接的数目。能见度方法是基于这样的观点：一个网页被其他网页引用得越多，则该网页就越有价值。特别地，一个网页被越重要的网页所引用，则该网页的重要程度也就越高。结果处理技术可归纳为：

　　(1)按频次排定次序通常，如果一个页面包含了越多的关键词，其搜索目标的相关性应该越好，这是非常合平常理的解决方案。

　　(2)按页面被访问度排序在这种方法中，搜索引擎会记录它所搜索到的页面被访问的频率。人们访问较多的页面通常应该包含比较多的信息，或者有其他吸引入的长处。这种解决方案适合一般的搜索用户，而因为大部分的搜索引擎都不是专业性用户，所以这种方案也比较适合一般搜索引擎使用。

　　(3)二次检索进一步净化(比flne)结果，按照一定的条件对搜索结果进行优化，可以再选择类别、相关词进行二次搜索等。

　　由于目前的搜索引擎还不具备智能，除非知道要查找的文档的标题，否则排列第一的结果未必是“最好”的结果。所以有些文档尽管相关程度高，但并不一定是用户最需要的文档。

　　搜索引擎技术的行业应用：

　　搜索引擎的行业应用一般指类似于千瓦通信提供的多种搜索引擎行业与产品应用模式，大体上分为如下几种形式：

　　1、政府机关行业应用

　　n实时跟踪、采集与业务工作相关的信息来源。

　　n全面满足内部工作人员对互联网信息的全局观测需求。

　　n及时解决政务外网、政务内网的信息源问题，实现动态发布。

　　n快速解决政府主网站对各地级子网站的信息获取需求。

　　n全面整合信息，实现政府内部跨地区、跨部门的信息资源共享与有效沟通。

　　n节约信息采集的人力、物力、时间，提高办公效率。

　　2、企业行业应用

　　n实时准确地监控、追踪竞争对手动态，是企业获取竞争情报的利器。

　　n及时获取竞争对手的公开信息以便研究同行业的发展与市场需求。

　　n为企业决策部门和管理层提供便捷、多途径的企业战略决策工具。

　　n大幅度地提高企业获取、利用情报的效率，节省情报信息收集、存储、挖掘的相关费用，是提高企业核心竞争力的关键。

　　n提高企业整体分析研究能力、市场快速反应能力，建立起以知识管理为核心的竞争情报数据仓库，是提高企业核心竞争力的神经中枢。

　　3、新闻媒体行业应用

　　n快速准确地自动跟踪、采集数千家网络媒体信息，扩大新闻线索，提高采集速度。

　　n支持每天对数万条新闻进行有效抓取。监控范围的深度、广度可以自行设定。

　　n支持对所需内容智能提取、审核。

　　n实现互联网信息内容采集、浏览、编辑、管理、发布的一体化。

　　4、行业网站应用

　　n实时跟踪、采集与网站相关的信息来源。n及时跟踪行业的信息来源网站，自动，快速更新网站信息。动态更新信息。

　　n实现互联网信息内容采集、浏览、编辑、管理、发布的一体化。

　　n针对商务网站提出商务管理模式，大大提高行业网站的商务应用需求。

　　n针对资讯网站分类目录生成，提出用户生成网站分类结构。并可以实时增加与更新分类结构。不受级数限制。从而大大利高行业的应用性。

　　n提供搜索引擎SEO优化专业服务，快速提高行业网站的推广。

　　n提供与CCDC呼叫搜索引擎的广告合作。建立行业网站联盟，提高行业网站知名度。

　　5)网络信息监察与监控

　　n网络舆情系统。如“千瓦通信-网络舆情雷达监测系统”

　　n网站信息与内容监察与监控系统，如“千瓦通信-网站信息与内容监测与监察系统(站内神探)”

　　随着因特网的迅猛发展、WEB信息的增加，用户要在信息海洋里查找信息，就象大海捞 针一样，搜索引擎技术恰好解决了这一难题(它可以为用户提供信息检索服务)。目前， 搜索引擎技术正成为计算机工业界和学术界争相研究、开发的对象。

　　搜索引擎(Search Engine)是随着WEB信息的迅速增加，从1995年开始逐渐发展起来的技术。据发表在《科学》杂志1999年7月的文章《WEB信息的可访问性》估计，全球目的网页超过8亿，有效数据超过9T，并且仍以每4个月翻一番的速度增长。用户要在如此浩 瀚的信息海洋里寻找信息，必然会"大海捞针"无功而返。搜索引擎正是为了解决这个"迷航"问题而出现的技术。搜索引擎以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导航的目的。搜索引擎提供的导航服务已经成为互联网上非常重要的网络服务，搜索引擎站点也被美誉为"网络门户"。搜索引擎技术因而成为计算机工业界和学术界争相研究、开发的对象。本文旨在对搜索 引擎的关键技术进行简单的介绍，以起到抛砖引玉的作用。

　　分 类

　　按照信息搜集方法和服务提供方式的不同，搜索引擎系统可以分为三大类：

　　1.目录式搜索引擎：以人工方式或半自动方式搜集信息，由编辑员查看信息之后，人 工形成信息摘要，并将信息置于事先确定的分类框架中。信息大多面向网站，提供目录浏 览服务和直接检索服务。该类搜索引擎因为加入了人的智能，所以信息准确、导航质量高 ，缺点是需要人工介入、维护量大、信息量少、信息更新不及时。这类搜索引擎的代表是 ：Yahoo、LookSmart、Open Directory、Go Guide等。

　　2.机器人搜索引擎：由一个称为蜘蛛(Spider)的机器人程序以某种策略自动地在互联网中搜集和发现信息，由索引器为搜集到的信息建立索引，由检索器根据用户的查询输入检索索引库，并将查询结果返回给用户。服务方式是面向网页的全文检索服务。该类搜索引擎的优点是信息量大、更新及时、毋需人工干预，缺点是返回信息过多，有很多无关信息，用户必须从结果中进行筛选。这类搜索引擎的代表是：AltaVista、Northern Light、Excite、Infoseek、Inktomi、FAST、Lycos、Google;国内代表为："天网"、悠游、OpenFind等。

　　3.元搜索引擎：这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处理后，作为自己的结果返回给用 户。服务方式为面向网页的全文检索。这类搜索引擎的优点是返回结果的信息量更大、更 全，缺点是不能够充分使用所使用搜索引擎的功能，用户需要做更多的筛选。这类搜索引 擎的代表是WebCrawler、InfoMarket等。

　　性 能 指 标

　　我们可以将WEB信息的搜索看作一个信息检索问题，即在由WEB网页组成的文档库中检索 出与用户查询相关的文档。所以我们可以用衡量传统信息检索系统的性能参数-召回率(R ecall)和精度(Pricision)衡量一个搜索引擎的性能。

　　召回率是检索出的相关文档数和文档库中所有的相关文档数的比率，衡量的是检索系 统(搜索引擎)的查全率;精度是检索出的相关文档数与检索出的文档总数的比率，衡量 的是检索系统(搜索引擎)的查准率。对于一个检索系统来讲，召回率和精度不可能两全 其美：召回率高时，精度低，精度高时，召回率低。所以常常用11种召回率下11种精度的 平均值(即11点平均精度)来衡量一个检索系统的精度。对于搜索引擎系统来讲，因为没 有一个搜索引擎系统能够搜集到所有的WEB网页，所以召回率很难计算。目前的搜索引擎系 统都非常关心精度。

　　影响一个搜索引擎系统的性能有很多因素，最主要的是信息检索模型，包括文档和查询 的表示方法、评价文档和用户查询相关性的匹配策略、查询结果的排序方法和用户进行相 关度反馈的机制。

　　主 要 技 术

　　一个搜索引擎由搜索器、索引器、检索器和用户接口等四个部分组成。

　　1.搜索器

　　搜索器的功能是在互联网中漫游，发现和搜集信息。它常常是一个计算机程序，日夜 不停地运行。它要尽可能多、尽可能快地搜集各种类型的新信息，同时因为互联网上的信 息更新很快，所以还要定期更新已经搜集过的旧信息，以避免死连接和无效连接。目前有 两种搜集信息的策略：

　　● 从一个起始URL集合开始，顺着这些URL中的超链(Hyperlink)，以宽度优先、深 度优先或启发式方式循环地在互联网中发现信息。这些起始URL可以是任意的URL，但常常 是一些非常流行、包含很多链接的站点(如Yahoo!)。

　　● 将Web空间按照域名、IP地址或国家域名划分，每个搜索器负责一个子空间的穷尽 搜索。搜索器搜集的信息类型多种多样，包括HTML、XML、Newsgroup文章、FTP文件、 字处理文档、多媒体信息。搜索器的实现常常用分布式、并行计算技术，以提高信息 发现和更新的速度。商业搜索引擎的信息发现可以达到每天几百万网页。

　　2.索引器

　　索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项，用于表示文档以及生 成文档库的索引表。

　　索引项有客观索引项和内容索引项两种：客观项与文档的语意内容无关，如作者名、 URL、更新时间、编码、长度、链接流行度(Link Popularity)等等;内容索引项是用来 反映文档内容的，如关键词及其权重、短语、单字等等。内容索引项可以分为单索引项和 多索引项(或称短语索引项)两种。单索引项对于英文来讲是英语单词，比较容易提取， 因为单词之间有天然的分隔符(空格);对于中文等连续书写的语言，必须进行词语的切 分。

　　在搜索引擎中，一般要给单索引项赋与一个权值，以表示该索引项对文档的区分 度，同时用来计算查询结果的相关度。使用的方法一般有统计法、信息论法和概率法。短 语索引项的提取方法有统计法、概率法和语言学法。

　　索引表一般使用某种形式的倒排表(Inversion List)，即由索引项查找相应的文档 。索引表也可能要记录索引项在文档中出现的位置，以便检索器计算索引项之间的相邻或 接近关系(proximity)。

　　索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实现即时 索引(Instant Indexing)，否则不能够跟上信息量急剧增加的速度。索引算法对索引器 的性能(如大规模峰值查询时的响应速度)有很大的影响。一个搜索引擎的有效性在很大 程度上取决于索引的质量。

　　3.检索器检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与 查询的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。

　　检索器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合模型四种。

　　4.用户接口

　　用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。主要的 目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、及时的信息。 用户接口的设计和实现使用人机交互的理论和方法，以充分适应人类的思维习惯。

　　用户输入接口可以分为简单接口和复杂接口两种。

　　简单接口只提供用户输入查询串的文本框;复杂接口可以让用户对查询进行限制，如 逻辑运算(与、或、非;+、-)、相近关系(相邻、NEAR)、域名范围(如.edu、.com) 、出现位置(如标题、内容)、信息时间、长度等等。目前一些公司和机构正在考虑制定 查询选项的标准。

　　未 来 动 向

　　搜索引擎已成为一个新的研究、开发领域。因为它要用到信息检索、人工智能、计算 机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理等多领域的理论和 技术，所以具有综合性和挑战性。又由于搜索引擎有大量的用户，有很好的经济价值，所 以引起了世界各国计算机科学界和信息产业界的高度关注，目前的研究、开发十分活跃， 并出现了很多值得注意的动向。

　　1.十分注意提高信息查询结果的精度，提高检索的有效性用户在搜索引擎上进行 信息查询时，并不十分关注返回结果的多少，而是看结果是否和自己的需求吻合。对于一 个查询，传统的搜索引擎动辄返回几十万、几百万篇文档，用户不得不在结果中筛选。解 决查询结果过多的现象目前出现了几种方法：一是通过各种方法获得用户没有在查询语句 中表达出来的真正用途，包括使用智能代理跟踪用户检索行为，分析用户模型;使用相关 度反馈机制，使用户告诉搜索引擎哪些文档和自己的需求相关(及其相关的程度)，哪些 不相关，通过多次交互逐步求精。二是用正文分类(Text Categorization)技术将结果分 类，使用可视化技术显示分类结构，用户可以只浏览自己感兴趣的类别。三是进行站点类 聚或内容类聚，减少信息的总量。

　　2.基于智能代理的信息过滤和个性化服务

　　信息智能代理是另外一种利用互联网信息的机制。它使用自动获得的领域模型(如We b知识、信息处理、与用户兴趣相关的信息资源、领域组织结构)、用户模型(如用户背景 、兴趣、行为、风格)知识进行信息搜集、索引、过滤(包括兴趣过滤和不良信息过滤) ，并自动地将用户感兴趣的、对用户有用的信息提交给用户。智能代理具有不断学习、适 应信息和用户兴趣动态变化的能力，从而提供个性化的服务。智能代理可以在用户端进行 ，也可以在服务器端运行。

　　3.采用分布式体系结构提高系统规模和性能

　　搜索引擎的实现可以采用集中式体系结构和分布式体系结构，两种方法各有千秋。但 当系统规模到达一定程度(如网页数达到亿级)时，必然要采用某种分布式方法，以提高 系统性能。搜索引擎的各个组成部分，除了用户接口之外，都可以进行分布：搜索器可以 在多台机器上相互合作、相互分工进行信息发现，以提高信息发现和更新速度;索引器可 以将索引分布在不同的机器上，以减小索引对机器的要求;检索器可以在不同的机器上。