基于Web的FTP搜索引擎系统的设计与实现.doc

1、海量的基于Web的FTP搜索引擎系统的设计与实现摘要在因特网上对众多FTP站点进行快速的文件条目查找，是网络信息搜索的重要组成部分。本文以“天网”FTP搜索引擎为例，介绍了千万级基于WEB的强大的FTP搜索引擎的设计与实现，并重点分析了系统所采用的关键技术和方法。关键词 FTP, 搜索引擎，WWWl AbstractFTP Search Engine is a powerful tool to search useful files for users from various resourceful FTP sites. In this paper, mainly described are

2、 the design and implementation of our FTP search engine, as well as the key technologies and methods we adopt.l Keyword FTP, Search Engine, World Wide Web目 录一、 引言.4二、 搜索引擎的历史与发展4a) 搜索引擎的起源4b) 真正意义的搜索引擎.4 c) Ftp的搜索引擎.5I、基于文本的ftp搜索引擎：Archie。.5II、基于Web的Ftp搜索引擎。5三、 天网ftp搜索引擎的现状.5a) 天网Ftp搜索产生的起源与发展历史。.5b

3、) 天网ftp搜索引擎的现状6i. 提供的功能61. 文件类型的分类.62. 时间过滤63. 大小过滤64. 精确匹配65. 站点限制66. 结果中查询功能.67. 支持常用的*，?，与，并 操作.78. 多语言版本79. 快捷方式系统.7ii. 数据量.71. 站点数量在3000以上72.文件条目1300万左右73. 快捷方式约一千条.7iii. 访问量.71. 日页面下载量在3万左右.72. 日访问人数在1.5万以上8四、 海量ftp搜索引擎的系统结构设计.9a) 系统的结构设计：四大模块和五个数据库9b) 数据库功能和结构说明10i. 文件类型库.10ii. 站点列表库11iii. 素材

4、数据库11iv. 索引数据库12v. 快捷方式数据库13c) 搜集建库模块.14i. 搜集建库过程说明.14ii. 站点获得策略14iii. 并发搜集策略15iv. 分布搜集策略15v. 多次尝试和断点续搜.15vi. 线性的建库过程.15vii. 数据库的切换16d) 搜索服务模块.16i. 搜索服务过程说明16ii. 服务接口说明17iii. 匹配算法.17iv. Cache策略18v. 强大的过滤功能的实现.181. 文件类别过滤182. 文件大小过滤183. 文件最后修改时间过滤.184. 站点过滤185. 精确匹配18vi. 对“与”、“并”、*、？操作以及结果中再搜索的支持19e)

5、 WWW搜索界面.20i. CGI参数说明20ii. 智能的换页机制20iii. 使用结果页面模板.21iv. 多语言版本的支持.21v. 漂亮、实用的结果输出页面.22vi. 为支持分布搜索的改进.221. 使用多服务器的可能性和必要性.222. 分布搜索的实现.223. 对分布搜索的加速.23f) 支持多媒体文件的特别处理技术23i. 多媒体文件条目的文件名特殊性以及查询特殊性23ii. 一种比较有效的处理技术.23iii. 在建库模块的改动.23iv. 在CGI模块的改动24g) 快捷方式系统24i. 使用快捷方式的原因.24ii. 快捷方式系统的关系图.24iii. 文件分类类别层次的

6、显示.25iv. 快捷方式条目的显示.25v. 注册新的软件26vi. 过滤用户注册的快捷方式26vii. 管理快捷方式系统.26五、 天网ftp搜索与国内国际Ftp搜索引擎的比较.26a) 国内国际ftp搜索引擎系统按原型分类说明：.26b) 功能比较：27c) 数据量比较：28d) 速度比较：28六、 天网Ftp搜索引擎未来的发展.28七、 结束语.29一、 引言今天搜索引擎的核心是网络导航服务，搜索引擎是一个网络门户，他们提供新闻，在线图书馆，词典，以及其它网络资源，他们提供了不仅仅是网站搜索的服务，他们的涉及面越来越广，也越来越有用。比如，Yahoo!注重的是网站分类归总服务，而如Al

7、ta Vista，Excite等则注重提供庞大的搜索数据库。根据中国互联网络信息中心(CNNIC)有关中国Internet发展状况统计报告，搜索引擎是除电子邮件以外网民使用最多的服务。面对浩如烟海的网络信息资源，网络搜索与导航已成为网络用户必不可少的工具。与相对众多的WWW搜索引擎相比，功能强大的FTP搜索引擎并不常见，由此限制了人们对具有大量信息与资源的FTP站点的访问。实现一个高速、海量、功能强大而又基于WEB的FTP搜索引擎将为网络用户提供极大方便。为此，北京大学计算机系网络与分布式系统领域最新开发出了“天网”FTP搜索引擎，并已作为“天网”中、英文搜索引擎1, 2的一个子系统在网上提供

8、服务, 获得了广大用户的一致好评。本文将从“天网”FTP搜索引擎的系统结构与算法出发阐述一种千万级FTP搜索引擎的设计与实现的方案。二、 搜索引擎的历史与发展a) 搜索引擎的起源1991年，XWAIS版本提供了一个有着友好界面的信息搜索系统，但这个系统要求很特殊的文件格式。而在同一年还出现了另外一个信息搜索系统，这是我们所称之为的GOPHER。Gopher 是一种按菜单形式组织的分布式文档查询系统 , 最初在 Minnesota大学发展起来(1991年), 开始用于校园网, 后来推广到Internet. Gopher为用户查询信息提供一个多级的菜单界面, 只需按照菜单指示的路径就能获取你想要的

9、信息, 使用非常方便. Gopher由 Gopher客户(Gopher Client)程序和Gopher服务器(Gopher Server)程序两部分组成. 在Internet上建立了数以千计的运行Gopher服务器程序的 Gopher 服务器. 它们是一些能为用户提供信息查询服务的计算机系统. 到1995年初的统计, 约有 6, 000主机安装了Gopher Server, 遍及全世界 100多个国家. 绝大多数 Gopher 服务器都是向 所有Internet用户开放的. Gopher系统的主要信息形式是正文文件. 信息文件可能驻留在不同的计算机上, 通过目录结构把它们链接在一起. 一个

10、Gopher 服务器的所有信息文件组成一棵信息树. 由于这种链接是透明的, 用户查询时可以在信息树之间自由穿越, 不必考虑信息的物理位置. Gopher 客户程序是用户端的信息浏览程序, 用于同Gopher Server进行对话. 用户查询时, 通过Client对Server发出查询请求; Server接收这种请求并把查询结果送回Client. 任何一台能够通过某种方式与Internet连接的计算机, 都可以通过一定方法成为 Gopher client .b) 真正意义的搜索引擎最早的真正意义上的搜索引擎是Lycos，创建于1994年的春天，当时Michael Mauldin将John Lea

11、vitt的spider程序接入到其索引程序中。Yahoo!也是在当年成立的。而NCSA Mosaic出现在1993年，Netscape出现在1994年。搜索引擎起源于传统的信息全文检索理论，即计算机程序通过扫描每一篇文章中的每一个词，建立以词为单位的倒排文件，检索程序根据检索词在每一篇文章中出现的频率和每一个检索词在一篇文章中出现的概率，对包含这些检索词的文章进行排序，最后输出排序的结果。搜索引擎除了全文检索系统之外，还要有“蜘蛛”(SPIDER)系统，即能够从互联网上自动收集网页的数据搜集系统。蜘蛛将搜集所得的网页内容交给索引和检索系统处理，就形成了我们常见互联网搜索引擎系统。c) Ftp的

12、搜索引擎I、基于文本的ftp搜索引擎：Archie。Archie能在只知道文件名的前提下，为用户找到这个文件所在的FTP服务器的地址。Archie实际上是一个大型的数据库，再加上与这个大型数据库相关联的一套检索方法。该数据库中包括大量可通过FTP下载的文件资源的有关信息，包括这些资源的文件名、文件长度、存放该文件的计算机名及目录名等。 使用Archie服务器有三条途径，常用到的是：通过远程登录到Archie主机，用Archie作为登录名。一旦登录成功，一个Archie程序将自动执行，这时一次输入一条命令，告诉Archie想查寻的内容，Archie将检索自己的数据库并显示检索的结果。如果用户对自

13、己想要的东西并不太清楚，Archie还提供“whatis”服务项目，该服务提供成千上万个程序、数据文件和文档的简短说明。 II、基于Web的Ftp搜索引擎。WWW的出现改变了Archie在文件搜索方面的统治地位，在美观、方便的WWW页面上搜索ftp文件成为用户的一大需求。在功能上，基于Web的ftp搜索引擎实现的功能与Archie基本一样，都是对用户提交的查询匹配串找到可以下载的ftp站点链接。但基于Web的ftp搜索引擎也有很多特色的功能，比如天网ftp搜索引擎的文件分类功能等等。基于Web的ftp搜索引擎也采用了很多WWW搜索引擎的策略，比如使用Spider自动收集数据，采用倒排索引，智能

14、换页链接技术以及大型ftp搜索引擎必须采用的分布收集和服务技术。目前国内国际ftp搜索引擎已有不少，但在系统底层上有区别的只有几种，其中较为有名的有北京大学天网搜索引擎的ftp子系统，华南木棉的ftp搜索系统，号称全球最大的ftp搜索引擎的，以及使用的的fastftpsearch，小型网站常使用的NOSEY PARKER系统以及其他一些搜索引擎。三、 天网ftp搜索引擎的现状a) 天网Ftp搜索产生的起源与发展历史。在天网1.0系统里，有一个简单的ftp搜索引擎，它只扫描几个教育网的ftp站点，算法上基本由unix命令组成，只能提供简单的字符匹配功能，而且界面很简单。由于用户对ftp搜索的需求

15、增加，我们在1999年秋开始了ftp搜索引擎的项目，并于2000年春交付了一个可以服务的百万级ftp搜索引擎，它搜索了30多个站点，提供150万的文件条目检索。根据用户反馈和用户查询行为的分析，经过不断改进，在2000年秋ftp搜索引擎和天网的www搜索引擎同时升级并更换主页界面，提供了更为人性化的查询界面和结果界面，系统也更为稳定健壮。2000年冬，天网ftp搜索引擎开始进行从百万级到千万级的改变。直到2001年春，一个搜索了国内3000多个ftp站点，提供1300万文件条目索引，并有分类快捷方式系统的全新的天网ftp搜索引擎提供服务了。b) 天网ftp搜索引擎的现状i. 提供的功能天网Ft

16、p搜索引擎与其它ftp搜索引擎相比，最大的特点就在于它的功能强大。尤其其中的文件类型过滤和快捷方式系统是所有ftp搜索引擎中独有的。目前天网ftp所提供的各种功能包括：1. 文件类型的分类目前文件类型分类分成图象、声音、视频、压缩、文档、程序、源代码、目录等。文件分类的标准是按文件的扩展名。由于天网Ftp搜索引擎有特有的文件分类功能，使得我们在搜索时精确度更高，比如要查电影“垂直极限”，只需输入名字“垂直极限”，选择“视频”类型，则各种文件类型的“垂直极限”的下载都找出来了。如果没有类型过滤，则如果用户输入过于简单的话，可能查出的结果未必都是电影，如果用户输入包括了扩展名的话，则查询结果显然又

17、少了很多，而且非计算机专业用户往往并不知道某个文件类的扩展名有些什么。另外，在搜索的结果页面里，天网ftp搜索引擎使用了生动的图标区分各个类型的文件，使得文件所属类型一目了然。文件分类已经成为了天网搜索引擎最强大又最有特色的功能。2. 时间过滤可以精确到年月日的文件最后修改时间过滤。这个功能在寻找特定时间的文件时很有用。3. 大小过滤这个功能与文件类型过滤功能的集合，可以帮助寻找特定类型的文件。比如同为“.dat”文件，有的是电影格式，有的是普通的数据文件。但一般而言，大于40M的“.dat”文件应该是电影。当我们加上这个限制的时候，也就可以找到扩展名为“.dat”的电影了。4. 精确匹配精确

18、匹配对于查找短文件名的文件比较方便,系统缺省使用是子串匹配，因为子串匹配更符合普通人的思维。5. 站点限制在天网搜索的3000多个站点里，用户可以选择其中的某个站点，仅仅对其中的文件进行查找。这个功能使得用户可以只搜对他（她）而言比较快的FTP站点，或他（她）比较喜欢的站点。6. 结果中查询功能很多WWW搜索引擎支持结果中查询的功能，但大部分Ftp搜索引擎并不支持结果中查询。天网Ftp搜索引擎采用巧妙的算法实现了结果中查询的功能，使用户可以逐步缩小搜索范围，最终得到想要的结果。7. 支持常用的*，?，与，并 操作由于大部分用户的查询都不是十分精确的，*，?，与，并 这四个操作就显得十分重要。与

19、的操作符是空格，并的操作符是逗号。这些操作的结合可以产生令人惊奇的结果，比如要查羽泉的最美，输入“羽泉 最美”，则用“羽泉”的查询结果和“最美”的查询结果作“与”操作，得到了用户想要的结果。8. 多语言版本天网Ftp搜索引擎在结果输出时采用模板技术，使得提供多语言、多界面的搜索结果页面成为可能。目前天网Ftp搜索引擎支持简体中文和英文，并保留支持其它语言和其它模板的接口。9. 快捷方式系统快捷方式系统是天网Ftp搜索引擎独有的功能。目前其它的Ftp搜索引擎仅仅提供了复杂的表单供用户提交查询，却没有考虑到广大搜索引擎用户大部分是普通网民而非计算机专业人士，使用上的简单化和傻瓜化是软件发展的必然。

20、因而天网Ftp搜索引擎建立了快捷方式系统，用户可以不输入任何字串，用鼠标就可以找到无数电影、音乐、程序、图片等等软件。而且快捷方式系统包含了注册功能，用户可以注册自己关心的软件，以便其它用户可以很方便的得到搜索结果。同时，我们对每个快捷方式的点击计数，在显示每一类快捷方式的时候排序，这样对于用户的非特定查询十分方便ii. 数据量1. 站点数量在3000以上站点列表来源于手工获得和机器扫描，由于扫描了国内大部分网段，因为可以说天网ftp搜索引擎可以查到几乎国内所有的ftp站点。2.文件条目1300万左右据国外的统计，全球ftp站点文件数目约一亿两千万，也就是说天网ftp搜索引擎已经搜集到全球十分

21、之一强的ftp网站。对比已知的若干Ftp搜索引擎，我们可以说天网Ftp搜索引擎已经是国内最大的Ftp搜索引擎。4. 快捷方式约一千条这个数目将随着用户注册的增加而增加。目前已经有528条电影快捷方式，295条音乐快捷方式，375条程序下载，59条开发资源快捷方式。iii. 访问量1. 日页面下载量在3万左右从2001年5月5日开始，我们记录了页面下载的总数，并定期计算每日页面下载量，下表(图1)为我们记录的页面下载日志统计： 时间 页面下载总数 平均每日下载量= = =2000.05.05 305 3052000.05.06 1011 7962000.05.10 10625 24032000.

22、05.11 16225 56002000.05.13 23494 36342000.05.15 30147 33262000.05.17 37883 38682000.05.19 41797 19572000.05.20 46757 4960 2000.05.22 53410 33262000.07.21 138562 14192000.07.22 142548 39862000.08.16 202286 23892000.08.26 227974 25682000.09.04 263068 38992000.09.05 271261 81932000.09.07 277893 3316200

23、0.09.24 377003 58302000.09.29 410703 67402000.10.17 511067 55752000.11.02 660012 93092000.11.06 702001 104972000.11.20 851550 106822000.11.23 880054 95012000.11.24 893388 133342000.11.27 925253 106212000.12.11 1131402 147242000.12.16 1213852 164902000.12.18 1252818 194832001.01.05 1502691 14698 2001

24、.02.14 1800674 74492001.03.06 2108148 153732001.03.09 2177719 231902001.03.12 2265346 292092001.05.13 3679936 292092001.05.19 3855190 29209图【1】 天网ftp搜索引擎用户访问日志从上表可以看出，天网ftp搜索引擎从最初的每日访问量只有几百，上升到现在的每日3万，经历了约一年的时间。在这一年里，天网ftp的用户随着天网的不断改进不断增加。而且，其中访问量下降的阶段都是学校的暑假和寒假，由此得出访问天网Ftp搜索引擎的大部分用户是教育网用户。2. 日访问人数在

25、1.5万以上由每个用户平均查询一到两次算，估计天网Ftp搜索引擎现在每日的访问人数已经达到1.5万以上。而天网搜索引擎总的每日访问人数在4到5万之间，也就是说天网Ftp搜索引擎已经成为天网搜索引擎系统十分重要、不可缺少的部分，也是天网搜索引擎越来越受用户欢迎的一个因素。四、 海量ftp搜索引擎的系统结构设计a) 系统的结构设计：四大模块和五个数据库参考WWW搜索引擎的一般系统结构，我们设计了如下的四个模块：搜集建库模块、搜索服务模块、CGI和WWW页面模块以及快捷方式系统。其中使用了五个数据库包括：站点列表数据库、文件类型数据库、素材库、索引库、快捷方式数据库。系统程序和数据的物理位置分配主要

26、分七个部分：1） respath：源数据目录。 包括搜集建库的程序FtpCollect，站点列表库，文件类型库和素材库。同时也存放搜集程序的日志。2） basepath：主目录。 包括搜索服务器FtpServer，索引库。其中索引库由三个子库组成，它们是：用于显示的Display库、用户过滤的Content库和用户匹配字串的Index库。同时也存放建库程序的日志，搜索服务器的日志，页面下载的日志。3） manage：管理程序目录。 包括快捷方式管理系统，站点列表获得程序FtpGetSite，IP站点列表和域名站点列表合并程序CheckSite、搜索服务器状态监控程序ServerKeeper等等

27、。其中快捷方式系统包括用户注册项过滤器ItemFilter和快捷方式条目管理ItemManage。4） scripts：CGI目录。 包括提供服务用的CGI和快捷方式系统中的注册CGI Submit.exe、条目显示CGI TxtSearch.exe，条目点击计数CGI FtpCount.exe等等。5） wwwpath：WWW页面目录。包括主页面（中英文），搜索结果页面模板（中英文），复杂搜索页面模板（中英文），文件分类标志图片等等。6） cachepath：搜索结果存放的缓冲目录。7） SQL数据库系统。 目前使用的是MS SQL Server 7.0系统。用于存放快捷方式系统里的数据。系

28、统结构关系如图2：快捷方式管理系统FTP站点列表获得程序FTP文件条目搜集程序站点列表数据库快捷方式数据库快捷方式登记文件类型数据库 传送请求搜索服务器素材数据库 FTP文件条目建库程序 发送请求索引数据库 回送结果发送请求 回送结果 用户接口 客户方 服务方快捷方式系统图【2】 海量ftp搜索引擎系统结构设计图b) 数据库功能和结构说明i. 文件类型库为了进行文件按扩展名分类，建立了文件类型数据库。它对每类文件给于一个编号以及属于该类型的所有扩展名。目前各分类的扩展名包括：1)图象：jpg, gif, bmp, jpeg, pcx, tif, tiff, wmf, psd, tga, pic

29、, png, pcd, dib, rle, iff, lbm, ilbm, jpe, jif, dcx, ico2)声音：mp3, wav, cda, mid, au, mp1, m3u, mjf, as, voc, xm, s3m, stm, mod, dsm, far, ult, mtm, mp2, mpa, mpga, 669, aac, mp4, vqf, pls, xpl, lrc, rmi, midi, snd, aif, aifc, wma, wax, aiff, rms3)视频：mpeg, mpg, avi, rm, swf, ram, rmm, ra, rmj, vob, a

30、sf, asx, wvx, wmv, wm, m1v, wmp, ivf, smi, mpv2, mp2v, smil, rp, mpv, ssm, rv, mpe, rf, rt4)压缩：zip, arj, gz, tar, tgz, cab, z, arc, b64, bhx, hqx, lzh, mim, taz, tz, uu, uue, xxe5)文档：txt, doc, htm, html, ppt, exl, mdb, asp, asa, php, js, rtf, wri6)程序：exe, com, bat, dll, class, out, ocx7)源代码：cpp, c,

31、h, hpp, pas, bas, java, asm, perl, inc, cxx, tli, tlh, hxx, inl, def, odl, idl 100)目录。目录类型由文件条目属性决定。0)其它。所有不在上述范围内的文件归类到其它中。文件类型库保存在FileType.txt。格式上采用文本格式，例如：0 图象 photos jpg, gif, bmp, jpeg1 声音 auidos mp3, wav, cda, mid这个库只在数据搜集程序中用到。ii. 站点列表库站点列表库保存在下的sites.txt里，每一行作为一个站点地址以文本格式保存。站点列表来源于站点获得程序扫描得到

32、的IP地址列表ipsites.txt和手工产生的有域名的地址列表namesites.txt经过CheckSite.exe程序合成产生。站点列表库用于确定搜集程序搜集范围和建库程序的建库范围。目前站点列表库大约有三千多个站点地址。iii. 素材数据库素材数据库是由搜集程序产生的简单搜集结果。搜集程序启动多个线程同时访问多个ftp站点，并行的将各个站点得到的文件条目经过简单的加工用存放在各个站点对应的素材库里。比如站点的文件条目信息保存在resource文件内。每个文件条目按文件名、最后修改时间、文件大小、站内路径、文件类型以一行行字符串的形式保存在对应的素材库里。例如：halfsize.jpg

33、文件名19700101 最后修改时间13421 文件大小(byte)/incoming/tools/htmledit/ 站内路径1 文件类型(图象)由此可见，素材库是一个非结构化的数据库，这种结构能够适应长文件名情况，而在空间利用上也相对比较充分。而如果采用固定大小的结构化数据库，则文件名和路径的长度就不得不作限制，最终导致不能正确访问下载地址或者可能浪费大量的存储空间。iv. 索引数据库索引数据库是直接用于搜索的数据库，它关系到搜索服务的速度与效率。它由用于显示的Display库、用于过滤的Content库和用于匹配字串的Index库组成。我们采用双字母倒排表的方式组织索引表。Index数据

34、库中包含256*256个双字母索引文件，每两个字母对应一个索引。其中Content库和Index库常驻内存，Display库只在输出结果时才被打开读取。对每一个FTP站点的文件条目，将其文件信息如创建时间，大小，文件类型等非字符串定长数据以及一个指向显示文件中对应的文件名和路径字串起始位置的偏移指针（DisplayOffset）记录在Content库里，由数据在Content库的位置获得该文件的唯一编号（ID）。同时在文件名的每两个连续字母对应的双字母索引里生成以ID为高24位，该双字母组在文件名内的偏移为低8位的32位索引项。Content 库是结构化的库，保存在content.dat里，它

35、的条目结构为typedef struct char filetype; /文件类型 long filesize; /文件大小long4 site; /所在站点编号long createdtime; /创建时间,如1999年2月为: 199902unsigned char filenamelen; /文件名长度long displayoffset; /对应的字串表示在DISPLAY库里的偏移FileContent;/Index 库包含256*256个双字母倒排表，保存在文件index.dat里，它的结构为_int32 indexoffset256*256+1; /每个双字母表在库里的偏移和库结尾

36、的偏移_int32 index0_0.; /0号字母和0号字母组成的索引表_int32 index0_1.; /0号字母和1号字母组成的索引表_int32 index0_2.; /0号字母和2号字母组成的索引表._int32 index255_255.; /255号字母和255号字母组成的索引表每个双字母倒排表的长度可以由indexoffset的相邻两项计算得到。倒排表由一系列32位结构组成，这个32位结构为typedef struct _int32 ID:24; /ID由该文件条目在Content库的编号决定_int32 OffsetInFileName:8; /双字母在文件名里的偏移 IndexItemStruct;Display库为非结构化库，以适应无限长度文件名和路径名情况。Display库保存在display.dat里，它的每个条目的结构定义为halfsize.jpg 文件名19700101 最后修改时间13421 文件大小(byte)/ Ftp路径1 文件类型(图象)v. 快捷方式数据库快捷方式数据库由三个子库组成，用户注册查询项的临时库：TmpFileItem，快捷方式分类层次库：TypeL