搜索常识

搜索引擎研究新技术

搜索引擎作为网络信息搜寻的工具，它以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务。
早期的搜索引擎将互联网中的资源服务器做为搜索的目标，并将收集的数据按概念进行分类，用户从分类引导中索取所需的信息资源。随着网络资源成几何量级增 长，这种方式很快就被淘汰。1994年，Spider程序被应用到索引程序中，Yahoo 、Google等相继出现，搜索引擎技术在应用和性能方面得到长足进步。但至今，功能再强大的搜索引擎都仍然存在信息丢失、招回率不高、精确率不高等问 题。用户需要更快、更准、更方便、更有效的查询服务成为搜索引擎技术发展研究追求的目标。
2003年3月“全国首届搜索引擎和网上信息挖掘学术研讨会”在北京大学举行，该会收录论文30篇，基本反映了当前国内研究状况及进展，本文将其中最具代 表性的Igloo1.2版网络搜索引擎和天网FTP搜索引擎关键技术的研究状况做一介绍。 1　爬虫系统性能优化技术研究
上海交通大学叶允明等的国家自然科学基金重大国际合作研究项目“Igloo分布式爬虫系统的性能优化”研究介绍了一个大型的分布式爬虫系统Igloo1.2版所采用的性能优化的措施。
1.1 高速通信与优雅爬行的折中
问题提出：
1）Web资源的海量性，用15天爬行全部网页的30％（约10亿个网页）对“网络爬虫(Crawler)”是巨大的挑战，如何在一个有效的时间内完成一次爬行互联网的任务？
2）Web服务器同时有许多TCP链接或在很短时间内下载大量的数据给服务器造成很大的负担，服务器将拒绝Crawler访问，如何不影响Web服务器和网络正常运行？
3）分布式Crawler中有大量的线程并行爬行，要同时访问DNS服务器以对URL进行域名解释，会给DNS服务器造成很大的负载并可能导致它无法响应。
解决方案：
1）Igloo分布式爬虫系统采用多机并行工作，它由多个爬虫组成，每个爬虫分布在不同的计算机上各自承担一部分网页的爬行任务，协同完成工作；系统采用多线程机制，让每个爬虫启动多线程并发的网页爬行，提高爬行速度。
2）系统内设置一台主机担任任务协调器，协调器采用哈希分配算法为每个爬虫分配爬行的URL范围，确保每个爬虫根据分配策略均衡快速爬行。
3）系统通过DNS缓存机制来解决：DNS解析器在解析URL时，首先在本地的DNS缓存中查找，如果找不到才转发给DNS服务器，否则直接将缓存中的DNS解析项返回。系统同时设计一个具有超时控制的DNS解析器，保证DNS解析的高效性。
1.2　URL数据库快速存取
问题提出：
系统瓶颈的另一个因素是URL数据库的存取操作，它关系到用户检索的响应速度。URL数据库是以Trie数据结构实现的，Trie是一种快速索引的数据结构，而检索速度与URL长度有关。但URL数据结构无法全部存储在内存之中。
解决方案：
URL 数据库存取算法采用基于“滞后合并策略”，即URL存取操作在内存中完成，使URL存取客户不会因为磁盘I/O而阻塞，当该数据结构占用的内存空间超过一 定的大小或每隔一定的周期，才启动一个线程将该内存驻留的Trie与磁盘文件中存储的Trie数据结构进行合并，在合并时进行URL的检索比较和插入。系 统采用磁盘和内存交换的方式存取大数据结构的策略，保证Crawler搜索到的百万级以上的数量级的URL存取的高性能，URL的内存命中率将近 100％，同时也避免了DNS服务器负载过重。
Web Crawler是搜索引擎和Web信息检索系统的基础，也是Web挖掘中的模式抽取、链接分析等研究的必要前提。Crawler系统Igloo1.2版采 用分布式的系统结构，设计二级哈希映射算法对URL进行高效分配；采用有效的性能优化方法保证爬行的同时不影响Web服务器和网络的正常运行，目前 Igloo系统作为Luka搜索引擎的信息收集代理已正常运行了近两年，系统进一步完善研究仍在进行中。 2　高级文件搜索引擎核心技术研究
文件搜索引擎作为专业网络资源门户的搜索工具越来越受重视，其技术发展也日新月异，北京大学计算机科学系陈华等研究的国家985项目，介绍“天网文件搜索引擎”从简单的FTP搜索引擎发展成具有强大功能的高级文件搜索引擎的技术和方法。
早期的FTP搜索引擎功能项比较简单，仅支持一些简单的操作，查询结果一般以换页方式显示。目前搜索引擎基本上可以实现指定站点的站内文件结果排序，以及在排序分类目录中二次查询。“天网文件搜索引擎”提供更加强大的搜索功能，介绍如下： 2.1　字符串匹配的扩展
问题提出：
早期搜索引擎可以实现字符串匹配功能，但对于大数据量请求，仍然影响搜索速度。
解决方案：
字符串匹配扩展可以增加搜索速度。以用户的查询串作为标签，把匹配结果建索引表，同时将索引表有时间限制地保存在文件Cache中。再次查询时，可以先直 接在Cache中查看是否命中。该方案使再查询变得十分简便。以此逻辑，还可以将“子查询字符串＋父查询字符串”作为标签进行保存。 2.2　属性过滤的扩展
问题提出：
文件属性和路径信息是一种非结构化数据，不能与时间等结构化的数据混在一起保存。
解决方案：
属性过滤的扩展可以实现文件分类与站内查询。
1）将文件格式按文件扩展名进行分类，如图像（jpg、gif、bmp...）、声音（mp3、wav、cda...）、视频、压缩、文档、程序、源代 码、目录、其他等，将其归属的所有扩展名统统集合在对应属性之下，建立文件类型库，以此解决非结构数据的文件类别过滤问题。只要文件属性中的站点IP与用 户要求的IP相同，则属性过滤通过。
2）建立两种搜索模式：简单搜索模式：属性过滤仅对文件类型和站点IP；复杂搜索模式：属性过滤还包括文件大小、文件最后修改时间、精确匹配等较少用的操 作。该方案区分不同请求的用户而建立的对应搜索模式，无疑加快了搜索速度，缩短显示结果的时间。 2.3　查询结果优化排序
解决方案：
1）在现成的查询结果排序算法如快速排序、堆排序中加一个参数，解决同一个算法的各个不同属性间的排序，实现查询结果灵活、多种的优化排序。
2）排序工作必须放在属性过滤之前，其服务器流程是：获得用户查询参数－用户查询串与文件名字符串匹配（包括Cache命中检测）－结果排序－属性过滤－结果输出。 2.4　输出结果的优化选择
解决方案：
1）智能式换页方案：将输出结果当前的起始显示项号对应的链接放在系统链接表中，以最大显示项数为间距生成有限个向前和向后的链接，实现用户保持鼠标不动 情况下以相同间距的翻页。智能式换页中的CGI程序向服务器提供起始显示结果号和每页的最大显示项数，然后经过服务器过滤，将可显示的结果信息返回给 CGI，这样大大的减少网络流量，降低运算代价。
2）使用模板技术：新的模板技术将算法与界面分离，该方法使得搜索结果界面更为灵活，已实现提供中文简体、繁体，英文3个版本。 2.5　支持分布搜集和分布搜索
问题提出：
处理大用户量请求和搜集范围的扩大。
解决方案：
1） 将收集数据和查询服务分离，不影响用户的查询结果界面。
2） 均衡多个查询服务器的查询负载。 2.6　外挂在线分析系统
问题提出：
FTP站点的不稳定性，如何让用户在查询时既不影响查询速度，又能了解站点链接情况？
解决方案：
1）应用外挂的在线分析系统。系统每5分钟扫描所有站点，记录站点链接情况，对不在线的站点列表索引；查询服务器每10分钟链接到外挂的已经按IP顺序排列的系统中获得列表并输出站点是否链接的结果。
2）将输出的结果按IP属性存放在Cache中，以便减少判断IP是否在线工作的时间。 2.7　外挂分类目录列表
问题提出：
一方面，搜索引擎如果只提供一个输入框和一大堆复杂的表单对于普通用户会不知所措；另一方面，用户搜索的关键词十分有限，搜索请求经常无法返回。
解决方案：
1）搜索引擎建立文件分类目录。分类目录可以较准确地对应查询结果，系统在每个分类目录中，保存常用的快捷方式，用户应用查询快捷方式获取查询结果。
2）系统提供自动的快捷方式与文件分类相结合功能。当快捷方式增多时，系统自动进行两级分类，第一级分类与文件格式分类类似，如电影、音乐、程序等；第二 级分类将上述类别再次按内容分类，如电影之下又分：动作片、言情片、侦探片等。上述方法既提高用户查询的精确度，又确保查询速度。
近年来的研究使 FTP使用功能越来越方便，查全率和查准率大大提高，从专业化的工具变成大众化的网络文件资源的搜索入口。“天网文件搜索引擎”作为国内比较知名的FTP 搜索引擎已能胜任千万级文件的搜索任务，日访问人数已超过40万人次，成为国内最大的，也是最主要的查找文件资源门户网站。
我们期待着性能更加优化的、人性化的搜索引擎引导用户信息获取和利用。

参考文献
1　李晓明，李星.搜索引擎与Web挖掘进展.北京：高等教育出版社，2003