搜索引擎及其性能改进方法的建设效果
0 引言
随着WWW的迅速发展，网上的信息也飞速膨胀。用户的主要问题不是信息不够，而是信息过剩（Information overload）。如何帮助人们有效利用WWW的海量信息资源成为当务之急，其首要任务便是发现信息——人们迫切需要有效的WWW导航工具，以协助用户找到所需信息。搜索引擎是一种信息检索工具，衡量其查询质量有两个重要标准：“查全率”和“查准率”<sup>[1]</sup>。查全率在信息检索领域的定义是：系统在进行某一检索时，检出的相关文献量与系统文献库中相关文献总量的比率，它反映该系统文献库中实有的相关文献量在多大程度上被检索出来。查准率是指在返回结果中相关页面占返回结果页面总量的比率。其中查全率主要通过分布抓取、抓取动态网页来改进。对于查准率，由于判断网页是否相关是用户的主观感受，因而改进查准率并没有普适的方法。用户访问搜索引擎的基本操作包括：提交查询、浏览结果页面和在结果页面中点击相关网页。用户的查询意图以及对结果的满意程度都体现在这些行为中，而这些行为都记录在搜索引擎的用户日志中。分析用户日志可以得到用户使用搜索引擎的基本特征，以这些基本特征为依据改进搜索引擎，可以提高搜索引擎的服务质量。
1 搜索引擎分类
尽管目前存在数量众多的搜索引擎，但根据它们所基
于的技术原理，可以将它们分成三大主要类型：基于机器
人（Robot）的搜索引擎、目录式（Directory或Catalog）搜索引擎和元（Meta）搜索引擎。
这三类搜索引擎中，元搜索引擎是基于第一类和第二类搜索引擎。第一类搜索引擎（基于Robot的搜索引擎）与第二类搜索引擎（目录式搜索引擎）各有如下特点：
（1）基于Robot的搜索引擎自动收集、分析和处理网页，因而它索引的网页数多、信息量大，并且能够定期重新收集网页，更新索引库的内容，向用户提供最新的Web网页信息。一般要定期访问大多数以前搜集的网页来刷新索引，以反映出网页的更新情况，同时还要去除一些死链接和镜像网页。网页部分内容的变化情况将反映到用户查询的结果中，这是基于Robot的搜索引擎的一个重要特征。但它只提供基于关键词的检索，用户只有确切地知道自己感兴趣的网页含有哪些关键词时，查询效果才比较理想。否则，返回的结果很可能和用户的实际需求“风马牛不相及”。这类搜索引擎的代表，国外有Google 、AltaVista、Northern Light、Excite、Infoseek、Inktomi、FAST、Lycos等，国内有天网、百度、悠游等。
（2）目录式搜索引擎支持基于分类目录的查询。目录式搜索引擎对收集的网页采用人工分类，这种人工方式对网页内容的理解比较准确。目录式搜索引擎的数据库依靠专职编辑或志愿人员建立起来。这些编辑人员在访问某个Web站点后撰写一段对该站点的描述，并根据站点的内容和性质将其归为一个预先分好的类别，把站点的URL和描述放在该类别中。信息大多面向网站，提供目录浏览服务和直接检索服务。很多目录也接受用户提交的网站和描述，当目录的编辑人员认可该网站及描述后，就会将之添加到合适的类别中。目录的用户界面基本上都是分级结构，首页提供了最基本的几个大类的入口，用户可以按照目录结构层层向下访问，直至找到自己感兴趣的类别。另外，用户也可以利用目录提供的搜索功能直接查找一个关键词，该类搜索引擎因为加入了人的智能，因此用户从目录搜索得到的结果往往比从基于Robot的搜索引擎得到的结果更具参考价值。缺点是需要人工介入、维护量大、信息量少、信息更新不及时。当用户对某个领域感兴趣但并不熟悉该领域的关键词时，这种查询方式能为用户提供更好的服务。由于人工分类效率低，网页更新困难，目录式搜索引擎在索引网页的规模上受到了很大限制。这类搜索引擎的代表有Yahoo、AOL等。
由于目录式搜索引擎完全采用人工进行网页的搜集和分类，其网页规模和更新速度与Internet的网页总量和网页更新速度相差太远，其涵盖的范围无法满足用户的需要，已经逐渐被基于Robot的搜索引擎所代替。同时，基于Robot的搜索引擎在用户的抱怨声中不断成长，不断改进检索质量，目前已经成为 Web用户发现网上信息必不可少的工具。
2 目前搜索引擎存在的不足
目前正处于第3代搜索引擎的研发阶段，这代搜索引擎没有某个单一的目标。它需要跟上WWW的发展速度，为用户提供更快、更准确的查询结果。智能化、个性化、专业化成为其追求的目标。同第一代搜索引擎技术相比，第二代搜索引擎在各方面都得到了很大提高，但是现有的搜索引擎技术仍然不能满足用户的需求。之前在Roper Starch的调查中指出，36%的互联网用户一个星期花了超过2个小时在网上搜索;71%的用户在使用搜索引擎时遇到过麻烦;平均搜索12分钟后发现搜索受挫，搜索受挫中46%都是因为链接错误;86%的互联网用户感到应当出现更有效、更准确的信息搜索技术。另一项由Keen所做的调查显示，人们平均每天有4个问题需要从外界获取答案;其中31%的人使用搜索引擎寻找答案;平均每周花费8.75个小时找寻答案;网上查找答案的，半数以上都不成功。
从这些调查数据中不难看出，目前的搜索引擎仍然存在不少局限。造成上述信息检索困难的实质原因在于，传统的搜索引擎对要检索的信息仅仅采用机械的关键词匹配来实现，缺乏知识处理能力和理解能力，也即搜索引擎无法处理在用户看来是非常普通的常识性知识，更不能处理随用户不同而变化的个性化知识等。而搜索引擎从根本上说是为用户提供服务，就需要研究用户行为，从中获取用户使用搜索引擎的一般性规律，这就等于学到一些用户认同的“普遍常识”，并用这些规律来对搜索引擎进行有针对性的改进。对于某些用户（譬如经常访问搜速引擎的用户），可以考察其特性，为其提供“量身订做”的服务。搜索引擎的用户日志中记录了用户访问搜索引擎的大量数据，对其进行分析可以得到用户访问搜索引擎的一般性规律和某些用户的特性。
3 性能改进及测试
3.1 日志分析
Google是搜索引擎的典型代表<sup>[2]</sup>，它提供对30亿文档（其中包括2 073 418 204 张网页）的访问，利用高效的算法和庞大的机器资源，向用户提供高质量的检索服务。国内搜索引擎中，具代表性
的是北京大学网络与分布式实验室研究开发的“天网”（Tianwang）搜索引擎。自1997年10月正式在CERNET上提供查询服务以来，受到学术界和用户的广泛好评。本研究对“天网”系统一个月的日志进行实验性分析，统计用户访问“天网”系统的查询、翻页、点击行为，希望从中找到用户查询行为的一些规律。并且，针对搜索引擎的cache设计了一系列实验，验证其可行性，并且测试了几种替换算法，得到如下结论：
（1）在使用“天网”的用户中，有一些是属于长期的固定用户，他们经常使用天网，大约占“天网”用户的20%，他们的查询占到了80%。而有30%以上的用户只是偶尔使用一下“天网”，他们在一个月的时间内只使用了一次“天网”。
（2）对“天网”用户的翻页点击行为进行分析发现，80%以上的查询用户只浏览了第一页内容，这说明第一页内容对于搜索引擎的形象至关重要。60%以上的查询用户没有在结果中点击页面，这表示用户对于“天网”搜索引擎的返回结果满意度不高。
（3）用户的查询一般都不长，4个汉字以下（8 byte）的查询词占到60%以上，而用户的查询词一般都被切成2～4个单词，99%以上的查询词都不在词典中出现。
（4）用户的查询词、用户点击url、用户查询词切词得到的单词序列，全部具有很强的集中性、一定的短期相关性和长期稳定性，可以考虑在查询端对查询词和索引端对单词进行cache，以提高响应速度，并对未在查询cache中命中的查询进行切词得到的单词序列进行分析，考察索引cache的可行性。分析发现，该单词序列的集中性非常强烈，不到10%的单词占到了80%以上。由此可知，索引端的cache也是非常可行和必要的。
（5）对FIFO、LRU、LFU 3种cache替换策略进行模拟实验，考察这3种替换算法的命中率。结果表明，LRU和LFU不分高下，FIFO略低于二者，而时间性能方面，FIFO和LRU要远好于LFU。因此，从时间效率和命中率两个角度考虑，LRU是最适合的替换算法。对于LRU，其命中率随cache容量的增加而提高，当cache容量超过5 000后，其增长趋于缓和。由此可知，根据目前情况，“天网”搜索引擎的查询cache大小在5 000比较合适。
3.2 位置相关性分析
在分析用户查询行为时，发现这样两个规律：
（1）用户的查询词一般都很短，2～4个汉字的查询词居多，8个字节长度以下的查询词占到总查询词的61.2%。
（2）用户的查询词往往都不是一个单词，只有不到1%的查询词是字典里的单词，其它绝大部分查询词都被切分成多个单词。
一般而言，如果用户输入的查询词是2～4个汉字，他们应该是把该输入作为一个整体提交给搜索引擎，比如用户提交频率很高的“大鸿米店”，用户希望返回的结果页面一定是包含“大鸿米店”的页面，但是经过切词，大鸿米店被切成了四个字“大+鸿+米+店”，索引子系统会提取“大”、“鸿”、“米”、“店”4个字出现的文档，进行合并后排序。这样返回的结果只是包含了这4个字，并不一定全部是用户想要的文档;而且，如果其排序只是考虑各个词出现的多少，这样排在前面的更不一定是用户所需要的。因此在处理用户查询时，必须考虑用户输入查询词中单词之间的位置关系，为此，设计并实现了位置相关性模块。
如果在处理查询时考虑查询词中单词之间的关系，就必须在索引数据库中记录单词的位置，这样才能在处理时进行匹配。因此，位置相关性模块涉及“天网”系统的两个部分：
（1） 搜集子系统。在网页抓取程序抓取网页进行切词的同时记录每篇文档中每个单词的位置信息。
（2）索引子系统。在建立索引数据库时，将单词位置关系也保存到索引数据库中。同时，在处理查询时，返回的结果要将单词位置关系和用户输入的查询词中单词位置关系进行匹配，有相同位置相邻关系的文档应该排在前面。位置相关性模块的系统结构如图1所示。
图1 位置相关性模块结构
3.3 测试结论
根据日志分析结果，可以对“天网”进行3方面的改造：
（1）增加位置相关性模块提高查询质量。传统的搜索引擎在定序时只考虑单词的出现次数而不考虑单词的位置关系，位置相关性模块突破了这种定序方式。它优先考虑用户查询中的单词位置关系，将与用户查询的单词位置关系一致的文档排在前面，借此来提高查询质量。
（2）改造cache模块提高响应速度。新的cache系统为二级cache结构，分为查询cache和索引cache两个部分。查询cache属于查询子系统，容量5 000，采用LRU替换算法，索引cache属于索引子系统，容量500，采用静态cache。
（3）增加自动目录导航服务提高用户满意程度。自动目录导航服务为用户提供类别内浏览和类别内查询两个功能，用户可以沿着预先设定好的类别层层前进，到达感兴趣的类别进行浏览和查询。
4 结语
本文对用户日志进行研究，以探寻用户访问的一般性规律，并根据研究结论对搜索引擎进行改造。研究中尚有许多问题有待完善，比如可以建造一个日志实时分析平台，在平台上添加各种分析功能，从而方便而快捷地得到各种分析结果，还可以对分析结果进行可视化，使结果更加直观等。同时，可以从多个方面对搜索引擎进行改造，增加一些小而实用的功能，比如近期热点查询、帮助用户了解时事，也可提供相关查询服务，以及个性化服务等。随着网络和多媒体技术的发展，音频、视频、图像将取代文本成为互联网上的主要信息，开发基于内容检索的多媒体搜索、个性化搜索、智能化搜索引擎是一个新的发展方向。