Web搜索引擎设计和实现分析

Web搜索引擎设计和实现分析----随着Internet的飞速发展，人们越来越依靠网络来查找他们所需要的信息，但是，由于网上的信息源多不胜数，也就是我们经常所说的"RichData,PoorInformation"。所以如何有效的去发现我们所需要的信息，就成了一个很关键的问题。为了解决这个问题，搜索引擎就随之诞生。----现在在网上的搜索引擎也已经有很多，比较著名的有AltaVista,Yahoo,InfoSeek,Metacrawler,SavvySearch等等。国内也建立了很多的搜索引擎，比如：搜狐、新浪、北极星等等,当然由于它们建立的时间不长，在信息搜索的取全率和取准率上都有待于改进和提高。----AltaVista是一个速度很快的搜索引擎，由于它强大的硬件配置，使它能够做及其复杂的查询。它主要是基于关键字进行查询，它漫游的领域有Web和Usenet。支持布尔查询的"AND"，"OR"和"NOT"，同时还加上最相近定位"NEAR"，允许通配符和"向后"搜索（比如：你可以查找链接到某一页的所有Web站点）。你可以决定是否对搜索的短语加上权值，在文档的什么部位去查找它们。能够进行短语查询而不是简单的单词查询的优点是很明显的，比如，我们想要查找一个短语"tobeornottobe"，如果只是把它们分解成单词的话，这些单词都是属于StopWord，这样这个查询就不会有任何结果，但是把它当作一个整体来查询，就很容易返回一些结果，比如关于哈姆雷特或者是莎士比亚等等的信息。系统对查询结果所得到的网页的打分是根据在网页中所包含的你的搜索短语的多少，它们在文档的什么位置以及搜索短语在文档内部之间的距离来决定的。同时可以把得到的搜索结果翻译成其他的语言。----Exite是称为具有"智能"的搜索引擎，因为它建立了一个基于概念的索引。当然它所谓的"智能"是基于对概率统计的灵活应用。它能够同时进行基于概念和关键字的索引。它能够索引Web,Usenet和分类的广告。支持"AND"，"OR"，"NOT"等布尔操作，同时也可以使用符号"+"和"-"。缺点是在返回的查询结果中没有指定网页的尺寸和格式。----InfoSeek是一个简单但是功能强大的索引，它的一个优点是有一个面向主题搜索的可扩展的分类。你可以把你的搜索短语和相似的分类目录的主题短语相互参照，而那些主题短语会自动加到你的查询中去。使你的搜索有更好的主题相关性。同时它也支持对图象的查询。它能够漫游Web,Usenet,UsenetFAQs等等。不支持布尔操作，但是可以使用符号"+"和"-"（相当于"AND"和"NOT"）----Yahoo实际上不能称为是一个搜索引擎站点，但是它提供了一个分层的主题索引，使你能够从一个通常的主题进入到一个特定的主题，Yahoo对Web进行了有效的组织和分类。比如你想要建立一个网页，但是你不知道如何操作，为了在Yahoo上找到关于建立网页的信息，你可以先在Yahoo上选择一个主题：计算机和Internet，然后在这个主题下，你可以发现一些子主题，比如：Web网页制作，CGI编程，JAVA，HTML，网页设计等，选择一个和你要找的相关的子主题，最终你就可以得到和该子主题相关的所有的网页的链接。也就是说，如果你对要查找的内容属于哪个主题十分清楚的话，通过目录查询的方法要比一般的使用搜索引擎有更好的准确率。你可以搜索Yahoo的索引，但是事实上，你并没有在搜索整个Web。但是Yahoo提供了选项使你可以同时搜索其他的搜索引擎，比如：AltaVista。但是要注意的是Yahoo实际上只是对Web的一小部分进行了分类和组织，而且它的实效性也不是很好。----搜索引擎的基本原理是通过网络机器人定期在web网页上爬行，然后发现新的网页，把它们取回来放到本地的数据库中，用户的查询请求可以通过查询本地的数据库来得到。如yahoo每天会找到大约500万个新的网页。----搜索引擎的实现机制一般有两种，一种是通过手工方式对网页进行索引，比如yahoo的网页是通过手工分类的方式实现的，它的缺点是Web的覆盖率比较低，同时不能保证最新的信息。查询匹配是通过用户写入的关键字和网页的描述和标题来进行匹配，而不是通过全文的匹配进行的。第二种是对网页进行自动的索引，象AltaVista则是完全通过自动索引实现的。这种能实现自动的文档分类，实际上采用了信息提取的技术。但是在分类准确性上可能不如手工分类。----搜索引擎一般都有一个Robot定期的访问一些站点，来检查这些站点的变化，同时查找新的站点。一般站点有一个robot.txt文件用来说明服务器不希望Robot访问的区域，Robot都必须遵守这个规定。如果是自动索引的话，Robot在得到页面以后，需要对该页面根据其内容进行索引，根据它的关键字的情况把它归到某一类中。页面的信息是通过元数据的形式保存的，典型的元数据包括标题、IP地址、一个该页面的简要的介绍，关键字或者是索引短语、文件的大小和最后的更新的日期。尽管元数据有一定的标准，但是很多站点都采用自己的模板。文档提取机制和索引策略对Web搜索引擎的有效性有很大的关系。高级的搜索选项一般包括：布尔方法或者是短语匹配和自然语言处理。一个查询所产生的结果按照提取机制被分成不同的等级提交给用户。最相关的放在最前面。每一个提取出来的文档的元数据被显示给用户。同时包括该文档所在的URL地址。----另外有一些关于某一个主题的专门的引擎，它们只对某一个主题的内容进行搜索和处理，这样信息的取全率和精度相对就比较高。----同时，有一类搜索引擎，它本身不用Robot去定期的采集网页。象SavvySearch和MetaCrawler是通过向多个搜索引擎同时发出询问并对结果进行综合返回给用户实现搜索功能。当然实际上象SavvySearch能够对各个搜索引擎的功能进行分析和比较，根据不同的用户查询提交给不同的搜索引擎进行处理，当然用户自己也可以指定利用哪一个搜索引擎。----一个优秀的搜索引擎必须处理以下几个问题：1网页的分类2自然语言的处理3搜索策略的调度和协作4面向特定用户的搜索。所以很多搜索引擎不同程度的使用了一些人工智能的技术来解决这些方面的问题。----二、网络Spider的实现描述----现在有很多文章对Web引擎做了大量的介绍和分析，但是很少有对它们的实现做一个详细的描述，这里我们主要来介绍一个具有基本功能的Web引擎的实现。本文，我们以类C++语言的形式来描述Web引擎如何采集网页并存放到数据库中的过程。同时描述了如何根据用户输入的关键字查询数据库并得到相关网页的过程。----2.1数据库结构----首先，我们要建立一个数据库表用来存放我们得到的网页。这里一般需要建立如下的表：----1.字典表的建立，事实上这里是用文档中有意义的单词和它们的出现频率来代表一个文档。----该表（WordDictionaryTbl）主要要包括三个字段，主要是用来存放和一个网页相关的单词的情况url_id对每一个URL的唯一的ID号word该URL中的经过stem的单词intag该单词在该网页中的出现的次数----2.存储每一个URL信息的表----该表(URLTbl)中主要的关键字段有：rec_id每一条记录的唯一的ID号status得到该URL内容的状态，比如HTTP_STATUS_TIMEOUT表示下载网页的最大允许超时urlURL的字符串名称content_type内容的类型last_modified最新的更改时间title该URL的标题docsize该URL的文件的尺寸last_index_time最近一次索引的时间next_index_time下一次索引的时间tag对于网页，用来表示它的类型，比如：是text，或者是html，或者是图片等等hops得到文件时候的曾经失败的次数keywords对于网页，和该网页相关的关键字description对于网页，指网页的内容的描述lang文档所使用的语言----3.因为网页中有很多单词是一些介词和语气助词或者是非常常用的常用词，它们本身没有多少意义。比如：英语中的about,in,at,we,this等等。中文中的如"和"，"一起"，"关于"等等。我们统一的把它们称为停止词（stopword）。所以我们要建立一个表，来包括所有这些停止词。该表(StopWordTbl)主要有两个字段。wordchar(32)表示那些停止词langchar(2)表示所使用的语言----4.我们要建立一个关于robot的表，我们在前面说过，所有的网站一般都有一个robot.txt文件用来表示网络上的robot可以访问的权限。该表(RobotTbl)主要有以下字段。hostinfoWeb站点主机的信息path不允许robot访问的目录----5.建立我们需要屏蔽的那些网页(比如一些内容不健康的或者没有必要去搜索的站点)的一张表(ForbiddenWWWTbl)，主要的字段就是网页的URL。----6.另外我们需要建立一个我们所要得到的文件类型的表(FileTypeTbl)，比如，对于一个简单的Web搜索引擎，我们可能只需要得到后缀为.html，htm，.shtml和txt的类型文件。其他的我们只是简单的忽略它们。主要的字段就是文件的类型和说明。----其中关于停止词的表的内容是我们要实现要根据各种语言的统计结果，把那些意义不大的单词放进去。关于文档单词、URL和Robot的表的内容都是在获取Web网页的时候动态增加记录的。----2.2具体网页获取算法描述----具体的网页的获取步骤是这样的：----我们可以设定我们的搜索程序最大可以开的线程的数目，然后这些线程可以同时在网上进行搜索，它们根据数据库中已有的关于网页的信息，找出那些需要更新的网页（如何判断哪些网页需要更新是一个值得研究的过程，现在有很多启发式和智能的算法，基本上是基于统计规律进行建模。最简单的当然是设定一个时间范围，在某个时间范围以前的网页被重新去搜索一遍），然后判断那些网页是否在屏蔽表中，如果是的话，就从关于URL的表中删除该条记录。否则，我们就到相应的WWW站点去得到URL指定的文件(这里需要注意的是根据不同的URL的特点，需要使用不同的协议，比如对于FTP站点要采用FTP协议，对于HTTP站点要采用HTTP协议，新闻站点要采用NNTP协议等等)事实上，我们先得到关于该网页的头信息，如果该网页的最新修改时间和我们最近提取的时间是一样的话，表示该网页内容没有任何更新，则我们就不必去得到它的内容，只需要修改最近一次更新它的时间为当前的时间就可以了。如果该网页最近做了修改，我们就要得到该网页，并对它的内容进行分析，主要要包括和它相关的链接，把它们加到相应的数据库中，同时判断网页所包含的各种其他的文件，如文本文件、图形文件、声音文件和其他多媒体文件是否是我们所需要的文件，如果是的话，就把它加到我们响应的数据库中。同时要根据网页的内容提取所有的有意义的单词和它们的出现的次数，放到相应的数据库中。为了更好的描述这个过程，我们来看跟这个过程相关的主要的几个对象和数据结构。对象主要是针对三个层次来讲的。第一层是针对WWW服务器，第二层是针对每一个页面，第三层是针对每一个页面的全文的索引。----2.3和实现相关的主要类对象和功能描述下面的结构是针对一个站点来说的。ClassCServer{主要的属性有：char*url;//WWW站点的URL名称char*proxy;//使用的代理的名称char*basic_auth;//进行基本的HTTP认证intproxy_port;//代理的端口号intperiod;//再次索引的周期intnet_errors;//网络连接不通的次数intmax_net_errors;//可以允许的最大的网络错误intread_timeout;//下载文件允许的最大的延迟intmaxhops;//表示URL可以最大跳转的深度intuserobots;//是否遵守robot.txt中的约定intbodyweight;//在<body>....</body>之间的单词的权重inttitleweight;//在<title>....</title>之间的单词的权重inturlweight;//在文档的URL中的单词的权重intdescweight;//在<METANAME="Description"Content="...">之间单词的权重intkeywordweight;//在<METANAME="Keywords"Content="...">之间的单词的权重----主要方法有：FindServer();//用来查找该服务器是否存在并可以连接FillDefaultAttribute()//用来针对所有的WWW服务器填写默认的属}；以上的对象中的成员变量是和一个站点相关的参数的设置，我们对所有的站点有一个默认的设置，但是可以对某些站点做一些特殊的设置。这些设置可以在配置文件中设定。----下面是关于文档的结构的主要的数据成员：ClassCNetDocument主要属性有：inturl_id;//该URL的ID号intstatus;//获取该文档时候的状态intsize;//文档的尺寸inttag;//和该文档相关的标签，表示该文档是HTML，TEXT或者是其他类型inthops;//URL跳转的次数char*url;//和该文档相关的URL的名称char*content_type;//该内容的类型char*last_modified;//最近一次的更新时间char*title;//该文档的标题char*last_index_time;//上次索引的时间char*next_index_time;//下次索引的时间char*keywords;//该文档中的关键字char*description;//该文档的描述主要方法有：FillDocInfo(…)//根据数据库，得到该文档相关信息AddHerf(…)//加入网页中存在的新的链接的网址DeleteURL(…)//删除一个存在的网址CanGetThisURL(…)//根据配置决定是否去得到该网页//下面三个方法是根据不同的URL，用不同的协议去获得文档NNTPGet(…)FTPGet(….)HTTPGet(….)ParseHead(…)//如果是HTTP协议得到的话，分析头信息ParseMainBody(…)//对获得的文档的主体进行分析ServerResponseType(….)//得到服务器端的响应消息UpdateURLDB(….)//更新的数据入库}；----事实上，我们在要提取一个网页的时候，都要建立一个CNetDocument对象，然后再对这个网页进行分析的时候，把相关的内容放到这个CNetDocument的成员变量里面。下面是关于页面全文索引的结构的主要数据成员：ClassCIndexer{主要属性有：char*url;//我们要处理的文档相关的URL的名称intmwords;//我们事先设定的一个网页的最大的单词数目intnwords;//实际的得到的单词的数目intswords;//我们已经排序的单词的数目WORD*Word;//所有单词的内容char*buf;//我们为文档所分配的空间主要方法有：InitIndexer(…)//进行初始设置和分配ParseGetFile(…)//对得到的网页进行全文索引AddWord(…)//把网页的可以索引的单词加到Word数组中去InToDB(….)//关于网页全文索引的信息入库}；----进行网页提取前，我们要建立一个CIndexer对象，它主要是用来对网页进行全文的索引。一般来说我们只对两种类型的URL进行全文索引，一个是text/html，另外一个是text/plain。其中WORD的数据结构如下：typedefstructword_struct{intcount;//该单词出现的次数intcode;//该单词的正常的形式，比如单词可能为encouraging,它的正常的形式应该为encourage,这其实是一种对单词的stem。即我们只取单词的主干部分。char*word;//该单词的内容}WORD;----以下的结构是和网页中的一些链接的对象相关的一个数据结构typedefstructhref_struct{char*href;//该链接的名称inthops;//发生的跳转次数intstored;//是否已经存储到数据库中}HREF;----所有需要更新的和新产生的URL都被放到这个结构中，当它的数量超过一定的范围以后，被一次性的存入数据库。----关于URL的一个数据结构如下：typedefstructurl{char*schema;//表示该URL是通过什么协议得到的，比如HTTP，FTP，NNTP等。char*specific;//主机的名称加上路径char*hostinfo;//主机的名称加上相关的协议端口char*hostname;//主机的名称char*path;//在主机的具体的路径char*filename;//文件的名称char*anchor;//相关的anchorintport;//协议相关的端口}URL;----这是针对URL的一些相关的属性的描述的一个数据结构。事实上在数据库中，我们存储的只是对网页的描述和对一些文本和HTML页面的关键词的索引信息。我们并不存储网页的实际的内容。----三、用户查询实现描述----关于对用户提交的查询请求的实现分析：----用户想要查询某一方面的信息一般都是通过提供和该领域相关的几个关键字来进行的。----我们来看一下关于用户查询的相关的数据结构和类：----下面是一个关于单词和它的权值的基本结构：typedefstructword_weight_pair{charword[WORD_LEN];intweight;}word_weight_pair;----下面的类主要是用来对用户的查询进行处理和分析：ClassCUserQuery{charm_UserQuery[MAX_QUERYLEN];//用户的查询表达式CPtrArrayword_weight_col;//是关于结构word_weight_pair的动态数组intm_maxReturnSum;//用户希望返回的最多的网页数intsearch_mode;CObArraym_returnDoc;//是关于CNetDocument对象的一个动态数组NormalizeWord（char*OneWord）;//对单词进行归整化，即Stem.Find(char*odbcName);//进行数据库查找和匹配}；----系统实现的基本的步骤如下：----1.对用户输入的查询表达式进行分析。事实上，我们在前面的Spider搜索过程中对文档的表示是通过关键字形式描述的，每一个文档可以表示为这样的一个集合其中::=<单词或短语名称><单词或短语的权值>----实际上就是采用矢量空间的表示方法来表示的文档。